# Testing if a property belongs to all members of a set without trying each one

• Dec 31st 2009, 02:32 PM
Andre
Testing if a property belongs to all members of a set without trying each one
Assume the following assertions:

$a$, $b$ and $c$ are positive integers.

$b > 1$

$b^{\lceil\log_b(2^a)\rceil} \geq 2^a$

$8c \leq a$

Given $a$ and $b$, is there a way to test that $\lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is true for all possible values of $c$, without trying each one?

Example 1:
$a = 32$
$b = 85$

The set of possible values for $c$ is $\{1, 2, 3, 4\}$. $5$ is not valid because $8{\times}5 > 32$. The condition that $\lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is satisfied by all possible values of $c$.

Example 2:
$a = 984$
$b = 268$

The set of possible values for $c$ is $\{1, 2, 3, ..., 123\}$. This example does not pass the test; it fails when $c = 122$ because:
$\lceil\log_{268}(2^{8{\times}122})\rceil = \lceil\log_{268}(2^{8(122+1)})\rceil$

Any help will be greatly appreciated. Thanks!

Andre

P.S. If this is not in the most appropriate thread, please direct me.
• Dec 31st 2009, 07:35 PM
Prove It
Quote:

Originally Posted by Andre
Assume the following assertions:

$a$, $b$ and $c$ are positive integers.

$b > 1$

$b^{\lceil\log_b(2^a)\rceil} \geq 2^a$

$8c \leq a$

Given $a$ and $b$, is there a way to test that $\lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is true for all possible values of $c$, without trying each one?

Example 1:
$a = 32$
$b = 85$

The set of possible values for $c$ is $\{1, 2, 3, 4\}$. $5$ is not valid because $8{\times}5 > 32$. The condition that $\lceil\log_b(2^{8c})\rceil < \lceil\log_b(2^{8(c+1)})\rceil$ is satisfied by all possible values of $c$.

Example 2:
$a = 984$
$b = 268$

The set of possible values for $c$ is $\{1, 2, 3, ..., 123\}$. This example does not pass the test; it fails when $c = 122$ because:
$\lceil\log_{268}(2^{8{\times}122})\rceil = \lceil\log_{268}(2^{8(122+1)})\rceil$

Any help will be greatly appreciated. Thanks!

Andre

P.S. If this is not in the most appropriate thread, please direct me.

Use basic log laws.

$\log_b{2^{8(c + 1)}} = \log_b{2^{8c + 8}}$

$=\log_b{(2^{8c}\cdot 2^8)}$

$=\log_b{2^{8c}} + \log_b{2^8}$.

Since $\log{x} > 0$ for all $x > 1$, this means $\log_b{2^8} > 0$.

Therefore $\log_b{2^{8(c + 1)}} > \log_b{2^{8c}}$.
• Jan 4th 2010, 06:37 PM
Andre
Thank you very much for your helpful response. My confusion arose from the ceiling function in $\lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$.

You've helped me realize the obvious solution for all $b < 256$ because $\lceil\log_b2^{8c}\rceil < \lceil\log_b{2^{8c}} + \log_b{2^8}\rceil$ for all $c$ where $\log_b{2^8} \geq 1$.

Still, the other parts of the problem, namely the declaration that $8c \leq a$, serve to impose a limit on $c$ such that $\lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$ can be satisfied when $b \geq 256$.

I don't yet understand if there is a way to test that $\lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$ can be satisfied given $a$ and $b$, short of trying each member of the set of all possible values for $c$.

Discovering a solution to the full problem is less important for me now that I know we can easily prove it for all $b < 256$, which is enough for most practical applications in computer science.
• Jan 4th 2010, 07:41 PM
Prove It
You should know that, for ANY base $b$, that

$\log_b{x} < 0$ for all $x < 1$

$\log_b{x} = 0$ if $x = 1$

$\log_b{x} > 0$ if $x > 1$.

If you don't believe me, try graphing some.

Since $2^8 > 1$, then $\log_b{2^8} > 0$.

No other assumptions need to be made.

$\log_b{2^{8c}} < \log_b{2^{8c}} + \log_b{2^8}$, thus completing your proof.
• Jan 4th 2010, 08:15 PM
Andre
Your statements are correct, of course, but you are ignoring the ceiling function.

Consider $b = 268$ and $c = 122$:

While $\log_{268}2^{8\times122} < \log_{268}2^{8\times123}$, when you apply the ceiling function you see that $\lceil\log_{268}2^{8\times122}\rceil = \lceil\log_{268}2^{8\times123}\rceil$.