Noncototient

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

nnumbers k such that k-φ(k) = nnnumbers k such that k-φ(k) = nnnumbers k such that k-φ(k) = nnnumbers k such that k-φ(k) = n
1all primes37217, 136973213, 469, 793, 1333, 5329109321, 721, 1261, 2449, 2701, 2881, 11881
24387474146110150, 182, 218
393999, 111, 319, 39175207, 219, 275, 355, 1003, 1219, 1363111231, 327, 535, 1111, 2047, 2407, 2911, 3127
46, 8407676148112196, 208
52541185, 341, 377, 437, 168177245, 365, 497, 737, 1037, 1121, 1457, 1517113545, 749, 1133, 1313, 1649, 2573, 2993, 3053, 3149, 3233, 12769
610428278114114226
715, 4943123, 259, 403, 184979511, 871, 1159, 1591, 6241115339, 475, 763, 1339, 1843, 2923, 3139
812, 14, 164460, 8680152, 158116
921, 2745117, 129, 205, 49381189, 237, 243, 781, 1357, 1537117297, 333, 565, 1177, 1717, 2581, 3337
104666, 7082130118174, 190
1135, 12147215, 287, 407, 527, 551, 220983395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889119539, 791, 1199, 1391, 1751, 1919, 2231, 2759, 3071, 3239, 3431, 3551, 3599
1218, 20, 224872, 80, 88, 92, 9484164, 166120168, 200, 232, 236
1333, 16949141, 301, 343, 481, 58985165, 249, 325, 553, 949, 12731211331, 1417, 1957, 3397
14265086122
1539, 5551235, 451, 66787415, 1207, 1711, 19271231243, 1819, 2323, 3403, 3763
1624, 28, 325288120, 172124244
1765, 77, 28953329, 473, 533, 629, 713, 280989581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921125625, 1469, 1853, 2033, 2369, 2813, 3293, 3569, 3713, 3869, 3953
18345478, 10690126, 178126186
1951, 91, 36155159, 175, 559, 70391267, 1027, 1387, 1891127255, 2071, 3007, 4087, 16129
20385698, 10492132, 140128192, 224, 248, 254, 256
2145, 57, 8557105, 153, 265, 517, 69793261, 445, 913, 1633, 2173129273, 369, 381, 1921, 2461, 2929, 3649, 3901, 4189
22305894138, 154130
2395, 119, 143, 52959371, 611, 731, 779, 851, 899, 348195623, 1079, 1343, 1679, 1943, 2183, 2279131635, 2147, 2507, 2987, 3131, 3827, 4187, 4307, 4331, 17161
2436, 40, 44, 466084, 100, 116, 11896144, 160, 176, 184, 188132180, 242, 262
2569, 125, 13361177, 817, 3721971501, 2077, 2257, 9409133393, 637, 889, 3193, 3589, 4453
266212298194134
2763, 81, 115, 18763135, 147, 171, 183, 295, 583, 799, 94399195, 279, 291, 979, 1411, 2059, 2419, 2491135351, 387, 575, 655, 2599, 3103, 4183, 4399
28526496, 112, 124, 128100136268
29161, 209, 221, 84165305, 413, 689, 893, 989, 1073101485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201137917, 1397, 3161, 3317, 3737, 3977, 4661, 4757, 18769
3042, 50, 586690102202138198, 274
3187, 247, 96167427, 1147, 4489103303, 679, 2263, 2479, 2623, 10609139411, 1651, 3379, 3811, 4171, 4819, 4891, 19321
3248, 56, 62, 6468134104206140204, 220, 278
3393, 145, 25369201, 649, 901, 1081, 1189105225, 309, 425, 505, 1513, 1909, 2773141285, 417, 685, 1441, 3277, 4141, 4717, 4897
3470102, 110106170142230, 238
3575, 155, 203, 299, 32371335, 671, 767, 1007, 1247, 1271, 5041107515, 707, 1067, 1691, 2291, 2627, 2747, 2867, 11449143363, 695, 959, 1703, 2159, 3503, 3959, 4223, 4343, 4559, 5063, 5183
3654, 6872108, 136, 142108156, 162, 212, 214144216, 272, 284

References

  • Browkin, J.; Schinzel, A. (1995). "On integers not of the form n-φ(n)". Colloq. Math. 68 (1): 55–58. Zbl 0820.11003.
  • Flammenkamp, A.; Luca, F. (2000). "Infinite families of noncototients". Colloq. Math. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.