## Perfect Totient Numbers

### January 8, 2019

A perfect number is a number for which the sum of its proper divisors is equal to the number; for instance, 28 is a perfect number because it is the sum of its proper divisors 1 + 2 + 4 + 7 + 14 = 28.

A perfect totient number (A082897) is a number for which the sum of its iterated totients is equal to the number. For instance, 327 is a perfect totient number; its iterated totients are φ(327) = 216, φ(216) = 80, …, and the sum of 216 + 80 + … = 327. I love number theory; it’s totally useless, and endlessly fascinating, as you will see if you follow the links on OEIS.

Your task is to compute the perfect totient numbers less than 10,000. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Sieving is nice, and we can roll calculating the totient sums into the sieving loop:

gets up to 9056583 in 20 seconds or so.

what’s a totient?

@ max, maybe try Google

@max: The totatives of a positive integer

nare those positive integers less thannthat are coprime ton; that is positive integersmfor which gcd(m,n) = 1. For instance, the totatives of 30 are 1, 7, 11, 13, 17, 19, 23 and 29. The totient of a positive integernis the number of totatives ofn, so φ(30) = 8.And this similar C++ program gets up to 918330183 in a couple of minutes. After that memory gets a bit tight on my laptop.

One useful place the totient function appears is in Euler’s Theorem: https://en.wikipedia.org/wiki/Euler%27s_theorem, which is fundamental to the correctness of RSA encryption.

Or maybe not, if the comment in that Wikipedia page is to be believed.

A brute force Haskell version.

Here’s a solution in C.

Example: