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

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

External links Noncototient definition from MathWorld