Results 1 to 5 of 5

Math Help - Testing if a property belongs to all members of a set without trying each one

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    19

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,487
    Thanks
    1391
    Quote Originally Posted by Andre View Post
    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}}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    19
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,487
    Thanks
    1391
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2009
    Posts
    19
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: September 29th 2010, 06:57 PM
  2. I am hope that my question belongs here.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 15th 2010, 12:06 AM
  3. im not sure if this belongs here
    Posted in the Calculus Forum
    Replies: 5
    Last Post: February 9th 2008, 04:47 AM
  4. I think this belongs here??
    Posted in the Algebra Forum
    Replies: 9
    Last Post: May 31st 2007, 06:46 PM
  5. Does line belongs to plane?
    Posted in the Geometry Forum
    Replies: 3
    Last Post: September 15th 2006, 01:51 PM

Search Tags


/mathhelpforum @mathhelpforum