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.
#Euler69 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)