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.
Programming Praxis 
Sieving is nice, and we can roll calculating the totient sums into the sieving loop:
def perfecttotient(N): a = list(range(N)) for p in range(2,N): if a[p] == p: for q in range(p,N,p): a[q] = a[q]//p*(p-1); a[p] += a[a[p]] if a[p]-1 == p: yield p for n in perfecttotient(10000000): print(n)gets up to 9056583 in 20 seconds or so.
what’s a totient?
@ max, maybe try Google
@max: The totatives of a positive integer n are those positive integers less than n that are coprime to n; that is positive integers m for 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 integer n is the number of totatives of n, 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.
#include <stdio.h> #include <stdint.h> #include <stdlib.h> #include <vector> typedef uint32_t T; int main(int argc, char *argv[]) { T N = 10000; if (argc > 1) N = strtoul(argv[1],0,0); std::vector<T> a(N); for (T i = 0; i < N; i++) a[i] = i; for (T p = 2; p < N; p++) { if (a[p] == p) { for (T q = p; q < N; q += p) { a[q] = a[q]/p*(p-1); } } a[p] += a[a[p]]; if (a[p]-1 == p) printf("%u\n", p); } }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.
import Data.Maybe (mapMaybe) import Math.NumberTheory.ArithmeticFunctions (totient) import System.Environment (getArgs, getProgName) import Text.Read (readMaybe) -- Iterated totient. iterTot :: Int -> Int iterTot = foldr (+) 1 . takeWhile (>1) . iterate totient . totient -- A list of perfect iterated totients. perfIterTots :: Int -> [Int] perfIterTots = eqIdx . map iterTot . enumFromTo 1 where eqIdx = map snd . filter (uncurry (==)) . zip [1..] main :: IO () main = do prog <- getProgName ns <- mapMaybe readMaybe <$> getArgs case ns of [n] -> mapM_ print $ perfIterTots n _ -> putStrLn $ "Usage: " ++ prog ++ " n"Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> typedef unsigned long ulong; void perfect_totients(ulong* array, ulong n) { array[0] = 0; array[1] = 0; for (ulong i = 2; i <= n; ++i) { array[i] = i; } for (ulong i = 2; i <= n; ++i) { if (array[i] == i) { for (ulong j = 1;; ++j) { if (j * i > n) break; array[j * i] *= i - 1; array[j * i] /= i; } } array[i] += array[array[i]]; if (array[i] == i) printf("%lu\n", i); } } int main(int argc, char* argv[]) { if (argc != 2) return EXIT_FAILURE; ulong n = strtoul(argv[1], NULL, 10); ulong* array = malloc((n + 1) * sizeof(array[0])); perfect_totients(array, n); free(array); return EXIT_SUCCESS; }Example: