TOPICS
Search

Totient Valence Function


N_phi(m) is the number of integers n for which the totient function phi(n)=m, also called the multiplicity of m (Guy 1994). Erdős (1958) proved that if a multiplicity occurs once, it occurs infinitely often.

The values of N_phi(m) for m=1, 2, ... are 2, 3, 0, 4, 0, 4, 0, 5, 0, 2, 0, 6, ... (OEIS A014197), and the nonzero values are 2, 3, 4, 4, 5, 2, 6, 6, 4, 5, 2, 10, 2, 2, 7, 8, 9, ... (OEIS A058277), which occur for m=1, 2, 4, 6, 8, 10, 12, 16, 18, 20, ... (OEIS A002202). The table below lists values for m<=50.

mN_phi(m)n such that phi(n)=m
121, 2
233, 4, 6
445, 8, 10, 12
647, 9, 14, 18
8515, 16, 20, 24, 30
10211, 22
12613, 21, 26, 28, 36, 42
16617, 32, 34, 40, 48, 60
18419, 27, 38, 54
20525, 33, 44, 50, 66
22223, 46
241035, 39, 45, 52, 56, 70, 72, 78, 84, 90
28229, 58
30231, 62
32751, 64, 68, 80, 96, 102, 120
36837, 57, 63, 74, 76, 108, 114, 126
40941, 55, 75, 82, 88, 100, 110, 132, 150
42443, 49, 86, 98
44369, 92, 138
46247, 94
481165, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210

The smallest m such that phi(n)=m has exactly 2, 3, 4, ... solutions are given by 1, 2, 4, 8, 12, 32, 36, 40, 24, ... (OEIS A007374). Including Carmichael's conjecture that N_phi(m)=1 has no solutions, the smallest n such that phi(n)=m has exactly 0, 1, 2, 3, 4, ... solutions are given by 3, 0, 1, 2, 4, 8, 12, 32, 36, 40, 24, ... (OEIS A014573). A table listing the first value of phi(N) with multiplicities up to 100 follows.

MphiMphiMphiMphi
032625605149927621840
21273845217640779072
32282885320167838640
44291320541152799360
583036965560008081216
612312405612288814032
73232768574752825280
836339000582688834800
94034432593024844608
102435712860136808516896
1148364200619984863456
1216037480621728873840
13396385766319208810800
142268391296642400899504
157044012006575609018000
1631241159366623049123520
177242331267228489239936
18336433072688400935040
1921644324069291609426208
20936458647053769527360
21144463120713360966480
22624477344721440979216
2310564838887313248982880
2417604972074110409926496
25360501680752772010034272

It is thought that N_phi(m)>=2 (i.e., the totient valence function never takes on the value 1), but this has not been proven. This assertion is called Carmichael's totient function conjecture and is equivalent to the statement that for all n, there exists m!=n such that phi(n)=phi(m) (Ribenboim 1996, pp. 39-40). Any counterexample must have more than 10000000 digits (Schlafly and Wagon 1994; erroneously given as 10000 in Conway and Guy 1996).


See also

Carmichael's Totient Function Conjecture, Sierpiński's Conjecture, Totient Function

Explore with Wolfram|Alpha

References

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, p. 155, 1996.Erdős, P. "Some Remarks on Euler's phi-Function." Acta Math. 4, 10-19, 1958.Ford, K. "The Distribution of Totients." Ramanujan J. 2, 67-151, 1998.Ford, K. "The Distribution of Totients, Electron. Res. Announc. Amer. Math. Soc. 4, 27-34, 1998.Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 94, 1994.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, 1996.Schlafly, A. and Wagon, S. "Carmichael's Conjecture on the Euler Function is Valid Below 10^(10000000)." Math. Comput. 63, 415-419, 1994.Sloane, N. J. A. Sequences A002202/M0987, A007374/M1093, A014197, A014573, A058277, and A082695 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Totient Valence Function

Cite this as:

Weisstein, Eric W. "Totient Valence Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TotientValenceFunction.html

Subject classifications