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

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

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.

Formula

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

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 *)

Prog

(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

Crossrefs

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

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

Sequence in context: A043342 A023715 A045143 * A339977 A157075 A369668

Adjacent sequences: A005275 A005276 A005277 * A005279 A005280 A005281

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Jud McCranie, Jan 01 1997

Status

approved