# 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

${\displaystyle pq-\varphi (pq)=pq-(p-1)(q-1)=p+q-1=n-1.\,}$

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 ${\displaystyle 1=2-\phi (2),3=9-\phi (9)}$ and ${\displaystyle 5=25-\phi (25)}$.

For even numbers, it can be shown

${\displaystyle 2pq-\varphi (2pq)=2pq-(p-1)(q-1)=pq+p+q-1=(p+1)(q+1)-2}$

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 ${\displaystyle 2^{k}\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).

 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

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