A005278 Noncototients: numbers k such that x - phi(x) = k has no solution.

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, 518, 520

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Browkin & Schinzel show that this sequence is infinite. - Labos Elemer, Dec 21 1999

If the strong Goldbach conjecture (every even number > 6 is the sum of at least 2 distinct primes p and q) is true, the sequence contains only even values, since p*q - phi(p*q) = p+q-1 and then every odd number can be expressed as x-phi(x). - Benoit Cloitre, Mar 03 2002

Browkin & Schinzel and Hee-sung Yang (Myerson link, problem 012.17d) ask if this sequence has a positive lower density. - Charles R Greathouse IV, Nov 04 2013

From Amiram Eldar, Feb 13 2021: (Start)

Sierpiński (1959) asked if this sequence is infinite.

Erdős (1973) asked if this sequence has a positive lower density.

Browkin and Schinzel (1995) proved that 509203*2^k is a term for all k>=1.

Flammenkamp and Luca (2000) proved that 509203 can be replaced with any other term of A263958 (and found 6 more terms of A263958).

Banks and Luca (2004) proved that the relative density of primes p within the sequence of primes such that 2*p is noncototient is 1. (End)

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer, 2004, section B36, pp. 138-142.
• Wacław Sierpiński, Number Theory, Part II, PWN Warszawa, 1959 (in Polish).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Donovan Johnson, Table of n, a(n) for n = 1..10000 (first 963 terms from T. D. Noe)
• William D. Banks and Florian Luca, Noncototients and Nonaliquots, arXiv:math/0409231 [math.NT], 2004.
• J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., Vol. 68 (1995), pp. 55-58.
• Paul Erdős, Über die Zahlen der form sigma(n)-n und n-phi(n), (in German), Elem. Math., Vol. 28 (1973), pp. 83-86; alternative link.
• Achim Flammenkamp and Florian Luca, Infinite families of noncototients, Colloq. Math., Vol. 86 (2000), pp. 37-41.
• Aleksander Grytczuk and Barbara Medryk, On a result of Flammenkamp-Luca concerning noncototient sequence, Tsukuba Journal of Mathematics, Vol. 29, No. 2 (2005), pp. 533-538.
• Gerry Myerson, Western Number Theory Problems, Dec 17 & 19 2012.
• David Ng, Introduction to Noncototients, 2017.
• Carl Pomerance and Hee-Sung Yang, On untouchable numbers and related problems, 2012.
• Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp., Vol. 83, No. 288 (2014), pp. 1903-1913; alternative link.
• Eric Weisstein's World of Mathematics, Noncototient.

Crossrefs

Cf. A006093, A126887, A263958. Complement of A051953.

Cf. A063740 (number of k such that cototient(k) = n).

Programs

Mathematica

nmax = 520; cototientQ[n_?EvenQ] := (x = n; While[test = x - EulerPhi[x] == n ; Not[test || x > 2*nmax], x++]; test); cototientQ[n_?OddQ] = True; Select[Range[nmax], !cototientQ[#]&] (* Jean-François Alcover, Jul 20 2011 *)

PARI

lista(nn)=v = vecsort(vector(nn^2, n, n - eulerphi(n)), ,8); for (n=1, nn, if (! vecsearch(v, n), print1(n, ", "))); \\ Michel Marcus, Oct 03 2016

Formula

{ k | A063740(k) = 0 }. - M. F. Hasler, Jan 11 2018

Extensions

More terms from Jud McCranie, Jan 01 1997