Noncototient

In number theory, a noncototient is a positive integer $n$ that cannot be expressed as the difference between a positive integer $m$ and the number of coprime integers below it. That is, $m - φ (m) = n$ , where $φ$ stands for Euler's totient function, has no solution for $m$ . The cototient of $n$ is defined as $n - φ (n)$ , so a noncototient is a number that is never a cototient.

It is conjectured that all noncototients are even. This follows from a modified form of the slightly stronger version of the Goldbach conjecture: if the even number $n$ can be represented as a sum of two distinct primes $p$ and $q$ , then

${\begin{aligned}pq-\varphi (pq)&=pq-(p-1)(q-1)\\&=p+q-1\\&=n-1.\end{aligned}}$

It is expected that every even number larger than 6 is a sum of two distinct primes, so probably no odd number larger than 5 is a noncototient. The remaining odd numbers are covered by the observations $1 = 2 - φ (2)$ , $3 = 9 - φ (9)$ , and $5 = 25 - φ (25)$ .

For even numbers, it can be shown ${\begin{aligned}2pq-\varphi (2pq)&=2pq-(p-1)(q-1)\\&=pq+p+q-1\\&=(p+1)(q+1)-2\end{aligned}}$

Thus, all even numbers $n$ such that $n + 2$ can be written as $(p + 1)(q + 1)$ with $p, q$ primes are cototients.

The first few noncototients are

10, 26, 34, 50, 52, 58, 86, 100, 116, 122, 130, 134, 146, 154, 170, 172, 186, 202, 206, 218, 222, 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, ... (sequence A005278 in the OEIS)

The cototient of $n$ are

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, ... (sequence A051953 in the OEIS)

Least $k$ such that the cototient of $k$ is $n$ are (start with $n = 0$ , 0 if no such $k$ exists)

1, 2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0, ... (sequence A063507 in the OEIS)

Greatest $k$ such that the cototient of $k$ is $n$ are (start with $n = 0$ , 0 if no such $k$ exists)

1, ∞, 4, 9, 8, 25, 10, 49, 16, 27, 0, 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0, 187, 52, 841, 58, 961, 64, 253, 0, 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0, ... (sequence A063748 in the OEIS)

Number of $k$ s such that $k - φ (k)$ is $n$ are (start with $n = 0$ )

1, ∞, 1, 1, 2, 1, 1, 2, 3, 2, 0, 2, 3, 2, 1, 2, 3, 3, 1, 3, 1, 3, 1, 4, 4, 3, 0, 4, 1, 4, 3, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, ... (sequence A063740 in the OEIS)

Erdős (1913–1996) and Sierpinski (1882–1969) asked whether there exist infinitely many noncototients. This was finally answered in the affirmative by Browkin and Schinzel (1995), who showed every member of the infinite family $2^{k}\cdot 509203$ is an example (See Riesel number). Since then other infinite families, of roughly the same form, have been given by Flammenkamp and Luca (2000).

Cototients of $n$ from 1-144
$n$	Numbers $k$ such that $k - φ (k) = n$
1	all primes
2	4
3	9
4	6, 8
5	25
6	10
7	15, 49
8	12, 14, 16
9	21, 27
10
11	35, 121
12	18, 20, 22
13	33, 169
14	26
15	39, 55
16	24, 28, 32
17	65, 77, 289
18	34
19	51, 91, 361
20	38
21	45, 57, 85
22	30
23	95, 119, 143, 529
24	36, 40, 44, 46
25	69, 125, 133
26
27	63, 81, 115, 187
28	52
29	161, 209, 221, 841
30	42, 50, 58
31	87, 247, 961
32	48, 56, 62, 64
33	93, 145, 253
34
35	75, 155, 203, 299, 323
36	54, 68
37	217, 1369
38	74
39	99, 111, 319, 391
40	76
41	185, 341, 377, 437, 1681
42	82
43	123, 259, 403, 1849
44	60, 86
45	117, 129, 205, 493
46	66, 70
47	215, 287, 407, 527, 551, 2209
48	72, 80, 88, 92, 94
49	141, 301, 343, 481, 589
50
51	235, 451, 667
52
53	329, 473, 533, 629, 713, 2809
54	78, 106
55	159, 175, 559, 703
56	98, 104
57	105, 153, 265, 517, 697
58
59	371, 611, 731, 779, 851, 899, 3481
60	84, 100, 116, 118
61	177, 817, 3721
62	122
63	135, 147, 171, 183, 295, 583, 799, 943
64	96, 112, 124, 128
65	305, 413, 689, 893, 989, 1073
66	90
67	427, 1147, 4489
68	134
69	201, 649, 901, 1081, 1189
70	102, 110
71	335, 671, 767, 1007, 1247, 1271, 5041
72	108, 136, 142
73	213, 469, 793, 1333, 5329
74	146
75	207, 219, 275, 355, 1003, 1219, 1363
76	148
77	245, 365, 497, 737, 1037, 1121, 1457, 1517
78	114
79	511, 871, 1159, 1591, 6241
80	152, 158
81	189, 237, 243, 781, 1357, 1537
82	130
83	395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889
84	164, 166
85	165, 249, 325, 553, 949, 1273
86
87	415, 1207, 1711, 1927
88	120, 172
89	581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921
90	126, 178
91	267, 1027, 1387, 1891
92	132, 140
93	261, 445, 913, 1633, 2173
94	138, 154
95	623, 1079, 1343, 1679, 1943, 2183, 2279
96	144, 160, 176, 184, 188
97	1501, 2077, 2257, 9409
98	194
99	195, 279, 291, 979, 1411, 2059, 2419, 2491
100
101	485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201
102	202
103	303, 679, 2263, 2479, 2623, 10609
104	206
105	225, 309, 425, 505, 1513, 1909, 2773
106	170
107	515, 707, 1067, 1691, 2291, 2627, 2747, 2867, 11449
108	156, 162, 212, 214
109	321, 721, 1261, 2449, 2701, 2881, 11881
110	150, 182, 218
111	231, 327, 535, 1111, 2047, 2407, 2911, 3127
112	196, 208
113	545, 749, 1133, 1313, 1649, 2573, 2993, 3053, 3149, 3233, 12769
114	226
115	339, 475, 763, 1339, 1843, 2923, 3139
116
117	297, 333, 565, 1177, 1717, 2581, 3337
118	174, 190
119	539, 791, 1199, 1391, 1751, 1919, 2231, 2759, 3071, 3239, 3431, 3551, 3599
120	168, 200, 232, 236
121	1331, 1417, 1957, 3397
122
123	1243, 1819, 2323, 3403, 3763
124	244
125	625, 1469, 1853, 2033, 2369, 2813, 3293, 3569, 3713, 3869, 3953
126	186
127	255, 2071, 3007, 4087, 16129
128	192, 224, 248, 254, 256
129	273, 369, 381, 1921, 2461, 2929, 3649, 3901, 4189
130
131	635, 2147, 2507, 2987, 3131, 3827, 4187, 4307, 4331, 17161
132	180, 242, 262
133	393, 637, 889, 3193, 3589, 4453
134
135	351, 387, 575, 655, 2599, 3103, 4183, 4399
136	268
137	917, 1397, 3161, 3317, 3737, 3977, 4661, 4757, 18769
138	198, 274
139	411, 1651, 3379, 3811, 4171, 4819, 4891, 19321
140	204, 220, 278
141	285, 417, 685, 1441, 3277, 4141, 4717, 4897
142	230, 238
143	363, 695, 959, 1703, 2159, 3503, 3959, 4223, 4343, 4559, 5063, 5183
144	216, 272, 284

References

Browkin, J.; Schinzel, A. (1995). "On integers not of the form n-φ(n)". Colloq. Math. 68 (1): 55–58. doi:10.4064/cm-68-1-55-58. Zbl 0820.11003.
Flammenkamp, A.; Luca, F. (2000). "Infinite families of noncototients". Colloq. Math. 86 (1): 37–41. doi:10.4064/cm-86-1-37-41. Zbl 0965.11003.
Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 138–142. ISBN 978-0-387-20860-2. Zbl 1058.11001.

External links

Noncototient definition from MathWorld