## Perfect Totient Numbers

### January 8, 2019

We’ve seen several methods for calculating totients in previous exercises. Here we calculate the totient using Euler’s product formula, factoring *n* using a 2,3,5-wheel; our totient function takes time O(sqrt *n*, and we memoize the result because of all the iterated sub-totients:

(define-memoized (totient n) (let ((wheel (vector 1 2 2 4 2 4 2 4 6 2 6))) (let loop ((n n) (t n) (f 2) (w 0)) (if (< n (* f f)) (if (< 1 n) (- t (/ t n)) t) (if (zero? (modulo n f)) (begin (while (zero? (modulo n f)) (set! n (/ n f))) (loop n (- t (/ t f)) (+ f (vector-ref wheel w)) (if (= w 10) 3 (+ w 1)))) (loop n t (+ f (vector-ref wheel w)) (if (= w 10) 3 (+ w 1))))))))

Now it is easy to compute the iterated totient sum:

(define (iterated-totient-sum n) (let loop ((n n) (s 0)) (if (= n 1) s (let ((t (totient n))) (loop t (+ s t))))))

And here is the requested result:

> (filter (lambda (n) (= (iterated-totient-sum n) n)) (range 1 10000)) (3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571 6561 8751)

You can run the program at https://ideone.com/TzNR0v. A reasonable alternative to the method shown above is to calculate the totients by sieving, as in a previous exercise.

Advertisements

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: