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
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from Jud McCranie, Jan 01 1997
STATUS
approved