JohnnyQ JohnnyQ - 1 year ago 143
Python Question

Imprecise results of logarithm and power functions in Python

I am trying to complete the following exercise:

I tried multiple variations, but my code breaks down when big numbers are involved (I tried multiple variations with solutions involving log and power functions):


Your task is to check wheter a given integer is a perfect power. If it is a perfect power, return a pair m and k with m^k = n as a proof. Otherwise return Nothing, Nil, null, None or your language's equivalent.

Note: For a perfect power, there might be several pairs. For example 81 = 3^4 = 9^2, so (3,4) and (9,2) are valid solutions. However, the tests take care of this, so if a number is a perfect power, return any pair that proves it.

The exercise uses Python 3.4.3

My code:

import math
def isPP(n):
for i in range(2 +n%2,n,2):
a = math.log(n,i)
if int(a) == round(a, 1):
if pow(i, int(a)) == n:
return [i, int(a)]
return None

How is it possible that I keep getting incorrect answers for bigger numbers? I read that in Python 3, all ints are treated as "long" from Python 2, i.e. they can be very large and still represented accurately. Thus, since i and int(a) are both ints, shouldn't the pow(i, int(a)) == n be assessed correctly? I'm actually baffled.

Answer Source

you are in the right track with logarithm but you are doing the math wrong, also you are skipping number you should not and only testing all the even number or all the odd number without considering that a number can be odd with a even power or vice-versa

check this

>>> math.log(170**3,3)

not even close, the correct method is described here Nth root

which is:

let x be the number to calculate the Nth root, n said root and r the result, then we get

rn = x

take the log in any base from both sides, and solve for r

logb( rn ) = logb( x )

n * logb( r ) = logb( x )

logb( r ) = logb( x ) / n

blogb( r ) = blogb( x ) / n

r = blogb( x ) / n

so for instance with log in base 10 with get

>>> pow(10, math.log10(170**3)/3 )

that is much more closer, and with just rounding it we get the answer

>>> round(169.9999999999999)

therefore the function should be something like this

import math

def isPP(x):
    for n in range(2, 1+round(math.log2(x)) ):
        root   = pow( 10, math.log10(x)/n )
        result = round(root)
        if result**n == x:
            return result,n

the upper limit in range is to avoid testing numbers that will certainly fail


>>> isPP(170**3)
(170, 3)
>>> isPP(6434856)
(186, 3)
>>> isPP(9**2)
(9, 2)
>>> isPP(23**8)
(279841, 2)
>>> isPP(279841)
(529, 2)
>>> isPP(529)
(23, 2)
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download