Innumber theory, anoncototient is apositive integern that cannot be expressed as the difference between a positive integerm and the number ofcoprime integers below it. That is,m −φ(m) =n, whereφ stands forEuler's totient function, has no solution for m. Thecototient ofn is defined asn −φ(n), so anoncototient 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 theGoldbach conjecture: if the even numbern can be represented as a sum of two distinct primesp andq, 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 observations1 = 2 –φ(2),3 = 9 –φ(9), and5 = 25 –φ(25).

For even numbers, it can be shown

Thus, all even numbersn such thatn + 2 can be written as(p + 1)(q + 1) withp, 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, ... (sequenceA005278 in theOEIS)

The cototient ofn 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, ... (sequenceA051953 in theOEIS)

Leastk such that the cototient ofk isn are (start withn = 0, 0 if no suchk 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, ... (sequenceA063507 in theOEIS)

Greatestk such that the cototient ofk isn are (start withn = 0, 0 if no suchk 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, ... (sequenceA063748 in theOEIS)

Number ofks such thatk −φ(k) isn are (start withn = 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, ... (sequenceA063740 in theOEIS)

Erdős (1913–1996) andSierpinski (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 (SeeRiesel number). Since then other infinite families, of roughly the same form, have been given by Flammenkamp and Luca (2000).

• Browkin, J.; Schinzel, A. (1995)."On integers not of the form n-φ(n)".Colloq. Math.68 (1):55–58.doi:10.4064/cm-68-1-55-58.Zbl 0820.11003.
• Flammenkamp, A.; Luca, F. (2000)."Infinite families of noncototients".Colloq. Math.86 (1):37–41.doi:10.4064/cm-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.

• Noncototient definition from MathWorld

• Integer sequences

• Articles with short description
• Short description is different from Wikidata