A006285 Odd numbers not of form p + 2^k (de Polignac numbers).

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1649, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, 1985, 2171, 2203, 2213, 2231, 2263, 2279, 2293, 2377, 2429, 2465, 2503, 2579, 2669

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

Contains both primes (A065381) and composites (A098237). - Jonathan Vos Post, Jun 19 2008

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

Examples

			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
		

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.

Crossrefs

Cf. A133122, A098237, A065381, A156695, A109925, A118954, A232460, A276417, A254248.

See also A058517, A350957, A350959, A350960.

Programs

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

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

PARI

isA006285(n,i=1)={ bittest(n,0) && until( isprime(n-i) || nn } \\ M. F. Hasler, Jun 19 2008, updated Apr 12 2017

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<A006285_list = list(islice(A006285_gen(),30)) # Chai Wah Wu, Nov 29 2023

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

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Apr 13 2000