Sequence A082897: Perfect Totient Numbers

The numbers in this sequence are like the perfect numbers, but adding together the iterates of the totient function instead of adding together the number's factors.

The Euler totient function, Sloane's A0010, counts how many numbers smaller than N are relatively prime to N. For example, if N is 14, the numbers 1, 3, 5, 9, 11 and 13 are relatively prime (notice that 1 counts), so the totient function of 14 is 6. For a prime P we're counting all numbers smaller than P, which is P-1, so the totient function always gives a smaller number except (by definition) when N=1.

So, we can take a number like 243, and compute the Totient function (which gives 162), then compute the totient function of that number, and so on (giving 54, 18, 6, 2 and 1), then add all these numbers together and we get 162 + 54 + 18 + 6 + 2 + 1 = 243. That makes it a "perfect totient number". The powers of 3 are all perfect totient numbers (fairly easy to show; see Wikipedia or Sloane's entry for A82897). These are labeled p3 below.

We also see that some numbers of the form 2^{2^N}-1 (like 15, 255, 65535, and 4292967295) are perfect totient numbers. These are labeled 2n1 below. However, 2^2⁶-1=18446744073709551615 is not a perfect totient number.

If a prime P is of the form P=4×3^N+1 for some integer N, then 3P is a perfect totient number[1]. The primes P of this form are: 5, 13, 37, 109, 2917, 19131877, 57395629, 16210220612075905069, ... (Sloane's A125734, with values of N from A5537), giving the perfect totient numbers 3P: 15, 39, 111, 327, 8751, 57395631, 172186887, 48630661836227715207, ... (not currently in OEIS). These are labeled 43n1 in the list below.

Here is a table of the perfect totient numbers as far as I've been able to compute. Each line gives the index N, the number A_N, and its factorization. After some of the factorizations are markers indicating if the number belongs to one of the two classes identified above: p3 for powers of 3, 2n1 for the 2^N-1 type, and 43n1 for the 3×(4×3^N+1) type:

A₁ = 3 = 3 p3 2n1
A₂ = 9 = 3² p3
A₃ = 15 = 3×5 43n1 2n1
A₄ = 27 = 3³ p3
A₅ = 39 = 3×13 43n1
A₆ = 81 = 3⁴ p3
A₇ = 111 = 3×37 43n1
A₈ = 183 = 3×61
A₉ = 243 = 3⁵ p3
A₁₀ = 255 = 3×5×17 2n1
A₁₁ = 327 = 3×109 43n1
A₁₂ = 363 = 3×11²
A₁₃ = 471 = 3×157
A₁₄ = 729 = 3⁶ p3
A₁₅ = 2187 = 3⁷ p3
A₁₆ = 2199 = 3×733
A₁₇ = 3063 = 3×1021
A₁₈ = 4359 = 3×1453
A₁₉ = 4375 = 5⁴×7
A₂₀ = 5571 = 3²×619
A₂₁ = 6561 = 3⁸ p3
A₂₂ = 8751 = 3×2917 43n1
A₂₃ = 15723 = 3²×1747
A₂₄ = 19683 = 3⁹ p3
A₂₅ = 36759 = 3×12253
A₂₆ = 46791 = 3³×1733
A₂₇ = 59049 = 3¹⁰ p3
A₂₈ = 65535 = 3×5×17×257 2n1
A₂₉ = 140103 = 3³×5189
A₃₀ = 177147 = 3¹¹ p3
A₃₁ = 208191 = 3×29×2393
A₃₂ = 441027 = 3²×49003
A₃₃ = 531441 = 3¹² p3
A₃₄ = 1594323 = 3¹³ p3
A₃₅ = 4190263 = 7×11×54419
A₃₆ = 4782969 = 3¹⁴ p3
A₃₇ = 9056583 = 3³×335429
A₃₈ = 14348907 = 3¹⁵ p3
A₃₉ = 43046721 = 3¹⁶ p3
A₄₀ = 57395631 = 3×19131877 43n1
A₄₁ = 129140163 = 3¹⁷ p3
A₄₂ = 172186887 = 3×57395629 43n1
A₄₃ = 236923383 = 3×1427×55343
A₄₄ = 387420489 = 3¹⁸ p3
A₄₅ = 918330183 = 3³×34012229
A₄₆ = 1162261467 = 3¹⁹ p3
A₄₇ = 3486784401 = 3²⁰ p3
A₄₈ = 3932935775 = 5²×29×5424739
A₄₉ = 4294967295 = 3×5×17×257×65537 2n1
A₅₀ = 4764161215 = 5×11×86621113
A₅₁ = 9158284383 = 3×101²×299261
A₅₂ = 10460353203 = 3²¹ p3
A₅₃ = 10774273279 = 7×11×47×509×5849
A₅₄ = 31381059609 = 3²² p3

[1] T. Venkataraman, "Perfect totient number". The Mathematics Student 43 178 (1975). MR0447089.

Some other sequences are discussed here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2014 May 12.

s.27