cp's OEIS Frontend

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

%I A005278 M4688 #70 Aug 11 2025 08:35:44
%S A005278 10,26,34,50,52,58,86,100,116,122,130,134,146,154,170,172,186,202,206,
%T A005278 218,222,232,244,260,266,268,274,290,292,298,310,326,340,344,346,362,
%U A005278 366,372,386,394,404,412,436,466,470,474,482,490,518,520
%N A005278 Noncototients: numbers k such that x - phi(x) = k has no solution.
%C A005278 Browkin & Schinzel show that this sequence is infinite. - _Labos Elemer_, Dec 21 1999
%C A005278 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
%C A005278 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
%C A005278 From _Amiram Eldar_, Feb 13 2021: (Start)
%C A005278 Sierpiński (1959) asked if this sequence is infinite.
%C A005278 Erdős (1973) asked if this sequence has a positive lower density.
%C A005278 Browkin and Schinzel (1995) proved that 509203*2^k is a term for all k>=1.
%C A005278 Flammenkamp and Luca (2000) proved that 509203 can be replaced with any other term of A263958 (and found 6 more terms of A263958).
%C A005278 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)
%D A005278 Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer, 2004, section B36, pp. 138-142.
%D A005278 Wacław Sierpiński, Number Theory, Part II, PWN Warszawa, 1959 (in Polish).
%D A005278 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005278 Donovan Johnson, <a href="/A005278/b005278.txt">Table of n, a(n) for n = 1..10000</a> (first 963 terms from T. D. Noe)
%H A005278 William D. Banks and Florian Luca, <a href="https://arxiv.org/abs/math/0409231">Noncototients and Nonaliquots</a>, arXiv:math/0409231 [math.NT], 2004.
%H A005278 J. Browkin and A. Schinzel, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm68/cm6817.pdf">On integers not of the form n-phi(n)</a>, Colloq. Math., Vol. 68 (1995), pp. 55-58.
%H A005278 Paul Erdős, <a href="https://users.renyi.hu/~p_erdos/1973-27.pdf">Über die Zahlen der form sigma(n)-n und n-phi(n)</a>, (in German), Elem. Math., Vol. 28 (1973), pp. 83-86; <a href="https://gdz.sub.uni-goettingen.de/id/PPN378850199_0028">alternative link</a>.
%H A005278 Achim Flammenkamp and Florian Luca, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm86/cm8616.pdf">Infinite families of noncototients</a>, Colloq. Math., Vol. 86 (2000), pp. 37-41.
%H A005278 Aleksander Grytczuk and Barbara Medryk, <a href="https://projecteuclid.org/euclid.tkbjm/1496164969">On a result of Flammenkamp-Luca concerning noncototient sequence</a>, Tsukuba Journal of Mathematics, Vol. 29, No. 2 (2005), pp. 533-538.
%H A005278 Gerry Myerson, <a href="http://wcnt.files.wordpress.com/2013/09/wcnt-problems-2012.pdf">Western Number Theory Problems</a>, Dec 17 & 19 2012.
%H A005278 David Ng, <a href="https://timetravel-1.github.io/Website/files/beamer-tutorial.pdf">Introduction to Noncototients</a>, 2017.
%H A005278 Carl Pomerance and Hee-Sung Yang, <a href="http://www.math.dartmouth.edu/~carlp/uupaper3.pdf">On untouchable numbers and related problems</a>, 2012.
%H A005278 Carl Pomerance and Hee-Sung Yang, <a href="https://doi.org/10.1090/S0025-5718-2013-02775-5">Variant of a theorem of Erdős on the sum-of-proper-divisors function</a>, Math. Comp., Vol. 83, No. 288 (2014), pp. 1903-1913; <a href="http://www.math.dartmouth.edu/~carlp/uupaper6.pdf">alternative link</a>.
%H A005278 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Noncototient.html">Noncototient</a>.
%F A005278 { k | A063740(k) = 0 }. - _M. F. Hasler_, Jan 11 2018
%t A005278 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 *)
%o A005278 (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
%Y A005278 Cf. A006093, A126887, A263958. Complement of A051953.
%Y A005278 Cf. A063740 (number of k such that cototient(k) = n).
%K A005278 nonn,nice
%O A005278 1,1
%A A005278 _N. J. A. Sloane_
%E A005278 More terms from _Jud McCranie_, Jan 01 1997