Noncototient
In number theory, 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
[math]\displaystyle{ \begin{align} pq - \varphi(pq) &= pq - (p-1)(q-1) \\ &= p + q - 1 \\ &= n - 1. \end{align} }[/math]
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 1 = 2 – φ(2), 3 = 9 – φ(9), and 5 = 25 – φ(25).
For even numbers, it can be shown [math]\displaystyle{ \begin{align} 2pq - \varphi(2pq) &= 2pq - (p-1)(q-1) \\ &= pq + p + q - 1 \\ &= (p+1)(q+1) - 2 \end{align} }[/math]
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 [math]\displaystyle{ 2^k \cdot 509203 }[/math] is an example (See Riesel number). Since then other infinite families, of roughly the same form, have been given by Flammenkamp and Luca (2000).
References
- 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.
- Flammenkamp, A.; Luca, F. (2000). "Infinite families of noncototients". Colloq. Math. 86 (1): 37–41. doi:10.4064/cm-86-1-37-41.
- Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 138–142. ISBN 978-0-387-20860-2.
External links
| Expand Classes of natural numbers |
|---|
 |  |
