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,1

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.

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 *)

Prog

(Haskell)
import Data.List (group)
a058277 n = a058277_list !! (n-1)
a058277_list = map length $ group a007614_list
-- Reinhard Zumkeller, Nov 22 2015
(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

Crossrefs

The nonzero terms of A014197.

Cf. A000010, A002202, A007614.

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

Sequence in context: A320778 A353948 A334049 * A065852 A303998 A319712

Adjacent sequences: A058274 A058275 A058276 * A058278 A058279 A058280

Keyword

nonn,easy,changed

Author

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

Extensions

More terms from Nick Hobson, Nov 04 2006

Status

approved