In number theory, a perfect totient number is an integer that is equal to the sum of its iterated totients. That is, one applies the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and adds together the resulting sequence of numbers; if the sum equals n, then n is a perfect totient number.

Examples

For example, there are six positive integers less than 9 and relatively prime to it, so the totient of 9 is 6; there are two numbers less than 6 and relatively prime to it, so the totient of 6 is 2; and there is one number less than 2 and relatively prime to it, so the totient of 2 is 1; and 9 = 6 + 2 + 1, so 9 is a perfect totient number.

The first few perfect totient numbers are

3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, ... (sequence A082897 in the OEIS).

Notation

In symbols, one writes

for the iterated totient function. Then if c is the integer such that

one has that n is a perfect totient number if

Multiples and powers of three

It can be observed that many perfect totient are multiples of 3; in fact, 4375 is the smallest perfect totient number that is not divisible by 3. All powers of 3 are perfect totient numbers, as may be seen by induction using the fact that

Venkataraman (1975) found another family of perfect totient numbers: if p = 4 × 3k + 1 is prime, then 3p is a perfect totient number. The values of k leading to perfect totient numbers in this way are

0, 1, 2, 3, 6, 14, 15, 39, 201, 249, 1005, 1254, 1635, ... (sequence A005537 in the OEIS).

More generally if p is a prime number greater than 3, and 3p is a perfect totient number, then p ≡ 1 (mod 4) (Mohan and Suryanarayana 1982). Not all p of this form lead to perfect totient numbers; for instance, 51 is not a perfect totient number. Iannucci et al. (2003) showed that if 9p is a perfect totient number then p is a prime of one of three specific forms listed in their paper. It is not known whether there are any perfect totient numbers of the form 3kp where p is prime and k > 3.

References

This article incorporates material from Perfect Totient Number on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.