Euler Problem 69

I tried this first with a GCD function and found it too slow. In fact it would have taken nearly a month to run. So I looked for a more efficient algorithm. Surprisingly, I found this one in Java (ironic isn’t it?) then translated it to Python.

I must admit, working out Euler Problems is a bit easier with Python. I suppose manipulating lists etc. in a higher level scripting language requires less work. Java was a bit too system-level for this kind of work. So this routine is pretty slick. It runs through the entire set in under 90 seconds. Next.

def totient(n):
    result = float(n)
    i = 2
    while i*i <= n:
        if n % i == 0:
            result -= result/i
        while n % i == 0:
            n /= i
        i += 1
    if n > 1:
        result -= result/n
    return result
print "Crunching Phi's\n"
max_n = 0
max_n_div_phi = float(0)
for n in range(2,1000001):
    phi = totient(n)
    n_div_phi = float(n/phi)
    if n_div_phi > max_n_div_phi:
        max_n = n
        max_n_div_phi = n_div_phi
        print "n:"+str(n)+" phi:"+str(phi)+" n/phi:"+str(n_div_phi)
    if n % 100000 == 0:
        print "Testing "+str(n)+"s"
print "\nAnswer: Value of n with max_n_div_phi is "+str(max_n)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s