Totient Valence Function

$N_\phi(m)$ is the number of Integers $n$ for which $\phi(n)=m$, also called the Multiplicity of $m$ (Guy 1994). The table below lists values for $\phi(N)\leq 50$.

$\phi(N)$	multiplicity	$N$
1	2	1, 2
2	3	3, 4, 6
4	4	5, 8, 10, 12
6	4	7, 9, 14, 18
8	5	15, 16, 20, 24, 30
10	2	11, 22
12	6	13, 21, 26, 28, 36, 42
16	6	17, 32, 34, 40, 48, 60
18	4	19, 27, 38, 54
20	5	25, 33, 44, 50, 66
22	2	23, 46
24	10	35, 39, 45, 52, 56, 70, 72, 78, 84, 90
28	2	29, 58
30	2	31, 62
32	7	51, 64, 68, 80, 96, 102, 120
36	8	37, 57, 63, 74, 76, 108, 114, 126
40	9	41, 55, 75, 82, 88, 100, 110, 132, 150
42	4	43, 49, 86, 98
44	3	69, 92, 138
46	2	47, 94
48	11	65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210

A table listing the first value of $\phi(N)$ with multiplicities up to 100 follows (Sloane's A014573).

$M$	$\phi$	$M$	$\phi$	$M$	$\phi$	$M$	$\phi$
0	3	26	2560	51	4992	76	21840
2	1	27	384	52	17640	77	9072
3	2	28	288	53	2016	78	38640
4	4	29	1320	54	1152	79	9360
5	8	30	3696	55	6000	80	81216
6	12	31	240	56	12288	81	4032
7	32	32	768	57	4752	82	5280
8	36	33	9000	58	2688	83	4800
9	40	34	432	59	3024	84	4608
10	24	35	7128	60	13680	85	16896
11	48	36	4200	61	9984	86	3456
12	160	37	480	62	1728	87	3840
13	396	38	576	63	1920	88	10800
14	2268	39	1296	64	2400	89	9504
15	704	40	1200	65	7560	90	18000
16	312	41	15936	66	2304	91	23520
17	72	42	3312	67	22848	92	39936
18	336	43	3072	68	8400	93	5040
19	216	44	3240	69	29160	94	26208
20	936	45	864	70	5376	95	27360
21	144	46	3120	71	3360	96	6480
22	624	47	7344	72	1440	97	9216
23	1056	48	3888	73	13248	98	2880
24	1760	49	720	74	11040	99	26496
25	360	50	1680	75	27720	100	34272

It is thought that $N_\phi(m)\geq 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\not=n$ such that $\phi(n)=\phi(m)$ (Ribenboim 1996, pp. 39-40). Any counterexample must have more than 10,000,000 Digits (Schlafly and Wagon 1994, Conway and Guy 1996).

See also Carmichael's Totient Function Conjecture, Totient Function

References

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, p. 155, 1996.

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^{10,000,000}$.'' Math. Comput. 63, 415-419, 1994.

Sloane, N. J. A. Sequence A014573 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.