Noncototient Explained

In number theory, a noncototient is a positive integer that cannot be expressed as the difference between a positive integer and the number of coprime integers below it. That is,, where stands for Euler's totient function, has no solution for . The cototient of is defined as, 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 can be represented as a sum of two distinct primes and, then

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

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,, and .

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

Thus, all even numbers such that can be written as with 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, ...

The cototient of 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, ...

Least such that the cototient of is are (start with, 0 if no such 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, ...

Greatest such that the cototient of is are (start with, 0 if no such 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, ...

Number of s such that is are (start with)

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

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

2k509203

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 from 1-144! !! Numbers such that
1all primes
24
39
46, 8
525
610
715, 49
812, 14, 16
921, 27
10
1135, 121
1218, 20, 22
1333, 169
1426
1539, 55
1624, 28, 32
1765, 77, 289
1834
1951, 91, 361
2038
2145, 57, 85
2230
2395, 119, 143, 529
2436, 40, 44, 46
2569, 125, 133
26
2763, 81, 115, 187
2852
29161, 209, 221, 841
3042, 50, 58
3187, 247, 961
3248, 56, 62, 64
3393, 145, 253
34
3575, 155, 203, 299, 323
3654, 68
37217, 1369
3874
3999, 111, 319, 391
4076
41185, 341, 377, 437, 1681
4282
43123, 259, 403, 1849
4460, 86
45117, 129, 205, 493
4666, 70
47215, 287, 407, 527, 551, 2209
4872, 80, 88, 92, 94
49141, 301, 343, 481, 589
50
51235, 451, 667
52
53329, 473, 533, 629, 713, 2809
5478, 106
55159, 175, 559, 703
5698, 104
57105, 153, 265, 517, 697
58
59371, 611, 731, 779, 851, 899, 3481
6084, 100, 116, 118
61177, 817, 3721
62122
63135, 147, 171, 183, 295, 583, 799, 943
6496, 112, 124, 128
65305, 413, 689, 893, 989, 1073
6690
67427, 1147, 4489
68134
69201, 649, 901, 1081, 1189
70102, 110
71335, 671, 767, 1007, 1247, 1271, 5041
72108, 136, 142
73213, 469, 793, 1333, 5329
74146
75207, 219, 275, 355, 1003, 1219, 1363
76148
77245, 365, 497, 737, 1037, 1121, 1457, 1517
78114
79511, 871, 1159, 1591, 6241
80152, 158
81189, 237, 243, 781, 1357, 1537
82130
83395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889
84164, 166
85165, 249, 325, 553, 949, 1273
86
87415, 1207, 1711, 1927
88120, 172
89581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921
90126, 178
91267, 1027, 1387, 1891
92132, 140
93261, 445, 913, 1633, 2173
94138, 154
95623, 1079, 1343, 1679, 1943, 2183, 2279
96144, 160, 176, 184, 188
971501, 2077, 2257, 9409
98194
99195, 279, 291, 979, 1411, 2059, 2419, 2491
100
101485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201
102202
103303, 679, 2263, 2479, 2623, 10609
104206
105225, 309, 425, 505, 1513, 1909, 2773
106170
107515, 707, 1067, 1691, 2291, 2627, 2747, 2867, 11449
108156, 162, 212, 214
109321, 721, 1261, 2449, 2701, 2881, 11881
110150, 182, 218
111231, 327, 535, 1111, 2047, 2407, 2911, 3127
112196, 208
113545, 749, 1133, 1313, 1649, 2573, 2993, 3053, 3149, 3233, 12769
114226
115339, 475, 763, 1339, 1843, 2923, 3139
116
117297, 333, 565, 1177, 1717, 2581, 3337
118174, 190
119539, 791, 1199, 1391, 1751, 1919, 2231, 2759, 3071, 3239, 3431, 3551, 3599
120168, 200, 232, 236
1211331, 1417, 1957, 3397
122
1231243, 1819, 2323, 3403, 3763
124244
125625, 1469, 1853, 2033, 2369, 2813, 3293, 3569, 3713, 3869, 3953
126186
127255, 2071, 3007, 4087, 16129
128192, 224, 248, 254, 256
129273, 369, 381, 1921, 2461, 2929, 3649, 3901, 4189
130
131635, 2147, 2507, 2987, 3131, 3827, 4187, 4307, 4331, 17161
132180, 242, 262
133393, 637, 889, 3193, 3589, 4453
134
135351, 387, 575, 655, 2599, 3103, 4183, 4399
136268
137917, 1397, 3161, 3317, 3737, 3977, 4661, 4757, 18769
138198, 274
139411, 1651, 3379, 3811, 4171, 4819, 4891, 19321
140204, 220, 278
141285, 417, 685, 1441, 3277, 4141, 4717, 4897
142230, 238
143363, 695, 959, 1703, 2159, 3503, 3959, 4223, 4343, 4559, 5063, 5183
144216, 272, 284

References

External links