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

Pages: 1 2

### 9 Responses to “Perfect Totient Numbers”

1. matthew said

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.

2. max said

what’s a totient?

3. Paul said

@ max, maybe try Google

4. programmingpraxis said

@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.

5. matthew said

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,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);
}
}
```
6. matthew said

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.

7. matthew said

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

8. Globules said

A brute force Haskell version.

```import Data.Maybe (mapMaybe)
import Math.NumberTheory.ArithmeticFunctions (totient)
import System.Environment (getArgs, getProgName)

-- 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"
```
```\$ ./perfecttotient 9999 | fmt
1 3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063
4359 4375 5571 6561 8751
```
9. Daniel said

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;
array = 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, NULL, 10);
ulong* array = malloc((n + 1) * sizeof(array));
perfect_totients(array, n);
free(array);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out 10000
3
9
15
27
39
81
111
183
243
255
327
363
471
729
2187
2199
3063
4359
4375
5571
6561
8751
```