Langbahn Team – Weltmeisterschaft

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

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

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 ks 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 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

Quelle: https://en.wikipedia.org/wiki/Noncototient