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

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

For even numbers, it can be shown
:$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, ...

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

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

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

Number of ''k''s 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, ...

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

References

*
*
*

External links

Noncototient definition from MathWorld

{{Classes of natural numbers

Integer sequences