OFFSET
1,2
COMMENTS
Crocker shows that this sequence is infinite; in particular, 2^2^n - 5 is in this sequence for each n > 2. - Charles R Greathouse IV, Sep 01 2015
Problem: what is the asymptotic density of de Polignac numbers? Based on the data in A254248, it seems this sequence may have an asymptotic density d > 0.05. Conjecture (cf. Pomerance 2013): the density d(n) of de Polignac numbers <= n is d(n) ~ (1 - 2/log(n))^(log(n)/log(2)), so the asymptotic density d = exp(-2/log(2)) = 0.055833... = 0.111666.../2. - Thomas Ordowski, Jan 30 2021
From Amiram Eldar, Feb 03 2021: (Start)
Romanov (or Romanoff) proved in 1934 that the complementary sequence has a positive lower asymptotic density, and the assumed asymptotic density was later named Romanov's constant (Pintz, 2006).
The lower asymptotic density of this sequence is positive (Van Der Corput, 1950; Erdős, 1950), and larger than 0.00905 (Habsieger and Roblot, 2006).
The upper asymptotic density of this sequence is smaller than 0.392352 (Elsholtz and Schlage-Puchta, 2018).
Previous bounds on the upper asymptotic density were given by Chen and Sun (2006), Pintz (2006), Habsieger and Roblot (2006), Lü (2007) and Habsieger and Sivak-Fischler (2010).
Romani (1983) conjectured that the asymptotic density of this sequence is 0.066... (End)
Chen, Dai, & Li show that the lower asymptotic density of this sequence is larger than 0.00965, improving on Habsieger & Roblot. - Charles R Greathouse IV, Jul 08 2024
REFERENCES
Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See p. 226.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section F13.
Clifford A. Pickover, A Passion for Mathematics, John Wiley & Sons, Inc., NJ, 2005, pp. 62 & 300.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. G. Van Der Corput, On de Polignac's conjecture, Simon Stevin, Vol. 27 (1950), pp. 99-105.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, see #127.
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
Yuda Chen, Xiangjun Dai, and Huixi Li, Some results on a conjecture of de Polignac about numbers of the form p + 2^k, arXiv preprint (2024). arXiv:2402.06644 [math.NT]
Yong-Gao Chen and Xue-Gong Sun, On Romanoff's constant, Journal of Number Theory, Vol. 106, No. 2 (2004), pp. 275-284.
Roger Crocker, A theorem concerning prime numbers, Mathematics Magazine, Vol. 34, No. 6 (1961), pp. 316-344.
Yuchen Ding, On a problem of Romanoff type, arXiv:2201.12783 [math.NT], 2022.
Christian Elsholtz and Jan-Christoph Schlage-Puchta, On Romanov's constant, Mathematische Zeitschrift, Vol. 288 (2018), pp. 713-724; alternative link.
Paul Erdős, On integers of the form 2^k + p and some related problems, Summa Brasil. Math., Vol. 2 (1950), p. 113-125.
Laurent Habsieger and Xavier-François Roblot, On integers of the form p+2^k, Acta Arithmetica, Vol. 122, No. 1 (2006), pp. 45-50.
Laurent Habsieger and Jimena Sivak-Fischler, An effective version of the Bombieri-Vinogradov theorem, and applications to Chen's theorem and to sums of primes and powers of two, Archiv der Mathematik, Vol. 95, No. 6 (2010), pp. 557-566.
Guang-Shi Lü, On Romanoff's constant and its generalized problem, Chinese Advances in Mathematics, Vol. 36, No. 1 (2007), pp. 94-100.
János Pintz, A note on Romanov's constant, Acta Mathematica Hungarica, Vol. 112, No. 1-2 (2006), pp. 1-14.
Paul Pollack, Not Always Buried Deep: A Second Course in Elementary Number Theory, AMS, 2009, p. 201, exercise 34.
Carl Pomerance, Erdős, van der Corput, and the birth of covering congruences, Joint Mathematics Meetings, Special Session on Covering Congruences, San Diego, CA, January, 2013.
F. Romani, Computations concerning primes and powers of two, Calcolo, Vol. 20 (1983), pp. 319-336.
Nikolai Pavlovich Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann., Vol. 109 (1934), pp. 668-678.
Wikipedia, Romanov's theorem.
FORMULA
A109925(a(n)) = 0. - Reinhard Zumkeller, May 27 2015
Conjecture: a(n) ~ n*exp(2/log(2)) = n*17.91... - Thomas Ordowski, Feb 02 2021
EXAMPLE
127 is in the sequence since 127 - 2^0 = 126, 127 - 2^1 = 125, 127 - 2^2 = 123, 127 - 2^3 = 119, 127 - 2^4 = 111, 127 - 2^5 = 95, and 127 - 2^6 = 63 are all composite. - Michael B. Porter, Aug 29 2016
MAPLE
N:= 10000: # to get all terms <= N
P:= select(isprime, {2, seq(i, i=3..N, 2)}):
T:= {seq(2^i, i=0..ilog2(N))}:
R:= {seq(i, i=1..N, 2)} minus {seq(seq(p+t, p=P), t=T)}:
sort(convert(R, list)); # Robert Israel, Sep 23 2016
MATHEMATICA
Do[ i = 0; l = Ceiling[ N[ Log[ 2, n ] ] ]; While[ ! PrimeQ[ n - 2^i ] && i < l, i++ ]; If[ i == l, Print[ n ] ], {n, 1, 2000, 2} ]
Join[{1}, Select[Range[5, 1999, 2], !MemberQ[PrimeQ[#-2^Range[Floor[ Log[ 2, #]]]], True]&]] (* Harvey P. Dale, Jul 22 2011 *)
PROG
(PARI) isA006285(n, i=1)={ bittest(n, 0) && until( isprime(n-i) || n<i<<=1, ); i>n } \\ M. F. Hasler, Jun 19 2008, updated Apr 12 2017
(Haskell)
a006285 n = a006285_list !! (n-1)
a006285_list = filter ((== 0) . a109925) [1, 3 ..]
-- Reinhard Zumkeller, May 27 2015
(Magma) lst:=[]; for n in [1..1973 by 2] do x:=-1; repeat x+:=1; a:=n-2^x; until a lt 1 or IsPrime(a); if a lt 1 then Append(~lst, n); end if; end for; lst; // Arkadiusz Wesolowski, Aug 29 2016
(Python)
from itertools import count, islice
from sympy import isprime
def A006285_gen(startvalue=1): # generator of terms
return filter(lambda n: not any(isprime(n-(1<<i)) for i in range(n.bit_length()-1, -1, -1)), count(max(startvalue+(startvalue&1^1), 1), 2))
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Apr 13 2000
STATUS
approved