Project Euler 516 - 5-smooth totients

Official link: https://projecteuler.net/problem=516

Note: My code takes around ~160s, ~40s with pypy

Thought Process

First step is to search for some properties of Euler's Totient Function if you don't know them already, after that it is not difficult to prove the possible factors of n

Knowing this, all we need to do is:

Generate all the possible hamming numbers (3429 of them including 1)
Go through them add 1 and check if that number is prime (546 of them)
Multiply all of the primes together to get all the other possible numbers which would result in φ(n) being a hamming number (Make sure not to multiply the same prime factors twice, that will no longer result in φ(n) being a hamming number because of the above proof)
With all of your new factors, multiply them with your hamming numbers, and now you have all the possible n. This is because of the multiplicative property of φ(n) which is φ(x*y) = φ(x)*φ(y) if gcd(x,y)=1

Interactive Code

Enter an integer < 10^10, because unfortunately my code is a little too slow, 10^10 takes ~ 7 seconds

S(10^11) = 3340605175, for those who need the test case!

Code will output S(yourinput) mod 2^32

Page updated

Google Sites

Report abuse