noncototient

{{Short description|Positive integers with specific properties}}

In number theory, a noncototient is a positive integer {{mvar|n}} that cannot be expressed as the difference between a positive integer {{mvar|m}} and the number of coprime integers below it. That is, {{math|1=m − φ(m) = n}}, where {{mvar|φ}} stands for Euler's totient function, has no solution for {{mvar|m}}. The cototient of {{mvar|n}} is defined as {{math|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 {{mvar|n}} can be represented as a sum of two distinct primes {{mvar|p}} and {{mvar|q}}, then

$$\backslash begin\{align\}$$

pq - \varphi(pq) &= pq - (p-1)(q-1) \\

&= p + q - 1 \\

&= n - 1.

\end{align}

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 {{math|1=1 = 2 – φ(2)}}, {{math|1=3 = 9 – φ(9)}}, and {{math|1=5 = 25 – φ(25)}}.

For even numbers, it can be shown

$$\backslash begin\{align\}$$

2pq - \varphi(2pq) &= 2pq - (p-1)(q-1) \\

&= pq + p + q - 1 \\

&= (p+1)(q+1) - 2

\end{align}

Thus, all even numbers {{mvar|n}} such that {{math|n + 2}} can be written as {{math|(p + 1)(q + 1)}} with {{mvar|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, ... {{OEIS|id=A005278}}

The cototient of {{mvar|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, ... {{OEIS|id=A051953}}

Least {{mvar|k}} such that the cototient of {{mvar|k}} is {{mvar|n}} are (start with {{math|1=n = 0}}, 0 if no such {{mvar|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, ... {{OEIS|id=A063507}}

Greatest {{mvar|k}} such that the cototient of {{mvar|k}} is {{mvar|n}} are (start with {{math|1=n = 0}}, 0 if no such {{mvar|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, ... {{OEIS|id=A063748}}

Number of {{mvar|k}}s such that {{math|k − φ(k)}} is {{mvar|n}} are (start with {{math|1=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, ... {{OEIS|id=A063740}}

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\; \backslash 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).

class="wikitable mw-collapsible mw-collapsed" |+ class="nowrap" | Cototients of {{mvar|n}} from 1-144 ! {{mvar|n}} !! Numbers {{mvar|k}} such that {{math|1=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