A058277 Number of values of k such that phi(k) = n, where n runs through the values (A002202) taken by phi.

2, 3, 4, 4, 5, 2, 6, 6, 4, 5, 2, 10, 2, 2, 7, 8, 9, 4, 3, 2, 11, 2, 2, 3, 2, 9, 8, 2, 2, 17, 2, 10, 2, 6, 6, 3, 17, 4, 2, 3, 2, 9, 2, 6, 3, 17, 2, 9, 2, 7, 2, 2, 3, 21, 2, 2, 7, 12, 4, 3, 2, 12, 2, 8, 2, 10, 4, 2, 21, 2, 2, 8, 3, 4, 2, 3, 19, 5, 2, 8, 2, 2, 6, 2, 31, 2, 9, 10

Offset: 1

Author

Claude Lenormand (claude.lenormand(AT)free.fr), Jan 05 2001

Keywords

• nonn
• easy

Comments

Carmichael (1922) conjectured that the number 1 never appears in this sequence. Sierpiński conjectured and Ford (1998) proved that all integers greater than 1 occur in the sequence. Erdős (1958) proved that if s >= 1 appears in the sequence then it appears infinitely often. - Nick Hobson, Nov 04 2006

A002202(n) occurs a(n) times in A007614. - Reinhard Zumkeller, Nov 22 2015

References

• Édouard Lucas, Théorie des Nombres, Blanchard 1958.

Links

• T. D. Noe, Table of n, a(n) for n=1..10000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
• R. D. Carmichael, Note on Euler's totient function, Bull. Amer. Math. Soc. 28 (1922), pp. 109-110.
• Paul Erdős, Some remarks on Euler's totient function, Acta Arith. 4 (1958), pp. 10-19.
• M. Farrokhi D. G., Gap function to compute the inverse of Euler's totient function.
• Kevin Ford, The distribution of totients, Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 27-34.
• Nick Hobson, Solution to puzzle 152: Totient valence.
• Eric Weisstein's World of Mathematics, Totient Valence Function.

Crossrefs

The nonzero terms of A014197.

Cf. A000010, A002202, A007614.

Cf. A006511 (largest k for which A000010(k) = A002202(n)).

Programs

Haskell

import Data.List (group)
a058277 n = a058277_list !! (n-1)
a058277_list = map length $ group a007614_list
-- Reinhard Zumkeller, Nov 22 2015

Mathematica

max = 300; inversePhi[?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m * Times @@ (p/(p-1)); n = m; nn = Reap[While[n <= nmax, If[EulerPhi[n] == m, Sow[n]]; n++]] // Last; If[nn == {}, {}, First[nn] ] ]; Reap[For[n = 1, n <= max, n = If[n == 1, 2, n+2], nn = inversePhi[n] ; If[nn != {} , Sow[nn // Length] ] ] ] // Last // First (* Jean-François Alcover, Nov 21 2013 *)

PARI

lista(nmax) = {my(m); for(n = 1, nmax, m = invphiNum(n); if(m > 0, print1(m, ", ")));} \\ Amiram Eldar, Nov 15 2024 using Max Alekseyev's invphi.gp

Extensions

More terms from Nick Hobson, Nov 04 2006