Noncototient

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

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

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

References[edit]

External links[edit]