Results 1 to 7 of 7

Math Help - An exponential proof and an algorithm

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    7

    An exponential proof and an algorithm

    Hey guys i'm looking to prove that if N = a^b then we are sure that either b \leq \log(N) either N = 1 is true, where a,b,N are all positive integers.
    And using that (i suppose, but not necessarily), to create an algorithm that given an integer can verify whether it's a power (i mean it can be written in the N = a^b form).

    What i've done is N = a^b \Rightarrow \log(N) = b\log(a)\Rightarrow  b = \frac{\log(N)}{\log(a)} \leq \log(N) Provided that a!=1
    Then used b \leq \log(N) as a fact to prove that when N=1 if b \leq \log(N) also applies then b\leq0 which is impossible since we know b>0

    Is that correct?
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Barbas View Post
    Hey guys i'm looking to prove that if N = a^b then we are sure that either b \leq \log(N) either N = 1 is true, where a,b,N are all positive integers.
    And using that (i suppose, but not necessarily), to create an algorithm that given an integer can verify whether it's a power (i mean it can be written in the N = a^b form).

    What i've done is N = a^b \Rightarrow \log(N) = b\log(a)\Rightarrow  b = \frac{\log(N)}{\log(a)} \leq \log(N) Provided that a!=1
    Then used b \leq \log(N) as a fact to prove that when N=1 if b \leq \log(N) also applies then b\leq0 which is impossible since we know b>0

    Is that correct?
    Thanks!
    are you sure you stated the problem correctly?

    for consider N = a = 1/2 and b = 1. Then they are all positive integers and N = a^b holds, while neither b \le \log N nor N = 1 is true
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    7
    Quote Originally Posted by Jhevon View Post
    are you sure you stated the problem correctly?

    for consider N = a = 1/2 and b = 1. Then they are all positive integers and N = a^b holds, while neither b \le \log N nor N = 1 is true
    If i'm not mistaken 1/2 is not an integer
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Barbas View Post
    If i'm not mistaken 1/2 is not an integer
    haha, yes, of course, you're right. don't know what i was thinking...well, yes i do, i was thinking of the log graph which is defined for non-integers.

    in that case, consider N = a = 2 and b = 1.

    then surely they are all positive integers now. wait, let me double check...yeah, positive integers. moreover, N = a^b holds. however, \log N \approx 0.301, and so b \le \log N is false, and so is the statement N = 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2008
    Posts
    7
    Sorry it took so long for me to get back with the events here in Greece. I don't know the professor is usually vague with his problems, maybe he meant a log of base 2?
    Would the argument hold then?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Barbas View Post
    Hey guys i'm looking to prove that if N = a^b then we are sure that either b \leq \log(N) either N = 1 is true, where a,b,N are all positive integers.
    And using that (i suppose, but not necessarily), to create an algorithm that given an integer can verify whether it's a power (i mean it can be written in the N = a^b form).

    What i've done is N = a^b \Rightarrow \log(N) = b\log(a)\Rightarrow b = \frac{\log(N)}{\log(a)} \leq \log(N) Provided that a!=1
    Then used b \leq \log(N) as a fact to prove that when N=1 if b \leq \log(N) also applies then b\leq0 which is impossible since we know b>0

    Is that correct?
    Thanks!
    For practical purposes this is incomprehensible.

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2008
    Posts
    7
    Yeah i guess, but it's the best i could do so far
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 11th 2010, 04:16 AM
  2. Big-Oh algorithm Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 12th 2010, 11:20 PM
  3. Proof Shuttle Sort is a quadratic order algorithm.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 11th 2010, 12:50 PM
  4. Euclidean algorithm proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 28th 2009, 07:03 PM
  5. Shuffling algorithm proof, please help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 14th 2008, 04:21 PM

Search Tags


/mathhelpforum @mathhelpforum