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

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

Assume the following assertions:

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

$\displaystyle b > 1$

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

$\displaystyle 8c \leq a$

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

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

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

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

The set of possible values for $\displaystyle c$ is $\displaystyle \{1, 2, 3, ..., 123\}$. This example does not pass the test; it fails when $\displaystyle c = 122$ because:
$\displaystyle \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.

2. Originally Posted by Andre
Assume the following assertions:

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

$\displaystyle b > 1$

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

$\displaystyle 8c \leq a$

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

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

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

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

The set of possible values for $\displaystyle c$ is $\displaystyle \{1, 2, 3, ..., 123\}$. This example does not pass the test; it fails when $\displaystyle c = 122$ because:
$\displaystyle \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.

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

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

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

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

Therefore $\displaystyle \log_b{2^{8(c + 1)}} > \log_b{2^{8c}}$.

3. Thank you very much for your helpful response. My confusion arose from the ceiling function in $\displaystyle \lceil\log_b2^{8c}\rceil < \lceil\log_b2^{8(c+1)}\rceil$.

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

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

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

Discovering a solution to the full problem is less important for me now that I know we can easily prove it for all $\displaystyle b < 256$, which is enough for most practical applications in computer science.

4. You should know that, for ANY base $\displaystyle b$, that

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

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

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

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

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

No other assumptions need to be made.

$\displaystyle \log_b{2^{8c}} < \log_b{2^{8c}} + \log_b{2^8}$, thus completing your proof.

5. Your statements are correct, of course, but you are ignoring the ceiling function.

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

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