A065381 -id:A065381 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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

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.

T. D. Noe, Table of n, a(n) for n = 1..10000
Thomas Bloom, Is the set of odd integers not of the form 2^k+p the union of an infinite arithmetic progression and a set of density 0?, Erdős Problems.
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.
Terence Tao, Erdős problem database, see entry no. 16.
Wikipedia, Romanov's theorem.

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

See also A058517, A350957, A350959, A350960.

a006285 n = a006285_list !! (n-1)
a006285_list = filter ((== 0) . a109925) [1, 3 ..]
-- Reinhard Zumkeller, May 27 2015

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

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

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

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

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

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

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

A078687 Number of x>=0 such that prime(n)-2^x is prime.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 3, 2, 1, 2, 2, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 2, 0, 3, 1, 4, 0, 2, 2, 1, 3, 2, 1, 4, 1, 1, 2, 4, 2, 1, 3, 3, 1, 1, 3, 0, 2, 2, 1, 3, 2, 1, 2, 3, 1, 1, 2, 2, 0, 0, 2, 2, 3, 1, 2, 0, 2, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 3, 0, 1, 3, 2, 1, 1, 3, 1, 4

Offset: 1

Benoit Cloitre, Dec 17 2002

nonn

			prime(17)=59 and only 59-2^3 = 53 is prime hence a(17)=1

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A156695.

f[p_] := Block[{c = exp = 0, lmt = 1 + Floor@ Log2@ p}, While[exp < lmt, If[ PrimeQ[p - 2^exp], c++]; exp++]; c]; Array[ f@ Prime@# &, 105] (* Robert G. Wilson v, Jul 07 2014 *)

a(n)=sum(i=0,floor(log(prime(n))/log(2)),if(isprime(prime(n)-2^i),1,0))

a(A049084(A065381(n)))=0, a(A049084(A065380(n)))=1; A118953(n)<=a(n); a(n)=A109925(A000040(n)). - Reinhard Zumkeller, May 07 2006

A098237 Composite de Polignac numbers (A006285).

Original entry on oeis.org

905, 959, 1199, 1207, 1211, 1243, 1271, 1477, 1529, 1541, 1589, 1649, 1719, 1807, 1829, 1859, 1927, 1969, 1985, 2171, 2231, 2263, 2279, 2429, 2465, 2669, 2983, 2993, 3029, 3149, 3215, 3239, 3341, 3353, 3431, 3505, 3665, 3817, 3845, 3985

Offset: 1

Ralf Stephan, Aug 31 2004

nonn

Odd composites that are not the sum of a prime and a power of two.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A156695.

Cf. A006285, A109925, A065381.

a098237 n = a098237_list !! (n-1)
a098237_list = filter ((== 0) . a109925) a071904_list
-- Reinhard Zumkeller, May 27 2015

A118958 Primes that cannot be written as 2^k + p with p prime < 2^k.

Original entry on oeis.org

2, 3, 5, 17, 31, 41, 47, 53, 59, 73, 79, 89, 97, 103, 109, 113, 127, 137, 149, 163, 167, 173, 179, 191, 193, 197, 223, 227, 233, 239, 251, 257, 271, 277, 281, 283, 307, 311, 313, 331, 337, 347, 349, 367, 373, 379, 389, 397, 401, 409, 421, 431, 433, 439, 443

Offset: 1

Reinhard Zumkeller, May 07 2006

nonn

A118953(A049084(a(n))) = 0; A065381 is a subsequence.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A118957, A091932, A156695.

Cf. A049084, A065381, A118953.

filter:= proc(n) not isprime(n-2^ilog2(n)) end proc:
select(filter, [seq(ithprime(i),i=1..100)]); # Robert Israel, Jan 27 2021

okQ[n_] := !PrimeQ[n-2^(Length[IntegerDigits[n, 2]]-1)];
Select[Prime[Range[100]], okQ] (* Jean-François Alcover, Feb 04 2023 *)

A065380 Primes of the form p + 2^k, p prime and k >= 0.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 257, 263, 269, 271, 277, 281, 283, 293

Offset: 1

Reinhard Zumkeller, Nov 03 2001

nonn

			a(3) = 11 = 3 + 2^3 = 7 + 2^2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A010051, A000079, A065381, A156695.

a065380 n = a065380_list !! (n-1)
a065380_list = filter f a000040_list where
   f p = any ((== 1) . a010051 . (p -)) $ takeWhile (<= p) a000079_list
-- Reinhard Zumkeller, Nov 24 2011

With[{upto=300},Select[Union[Select[Flatten[Outer[Plus,Prime[Range[ PrimePi[upto]]],2^Range[0,Floor[Log[2,upto]]]]],PrimeQ]],#<=upto&]] (* Harvey P. Dale, Feb 28 2012 *)

A078687(A049084(a(n))) > 0; A091932 is a subsequence. - Reinhard Zumkeller, May 07 2006

A188903 a(n) is the least power of 2 such that 2n+1 - a(n) is prime, or 0 if no such prime exists.

Original entry on oeis.org

0, 1, 2, 2, 2, 4, 2, 2, 4, 2, 2, 4, 2, 4, 16, 2, 2, 4, 8, 2, 4, 2, 2, 4, 2, 4, 16, 2, 4, 16, 2, 2, 4, 8, 2, 4, 2, 2, 4, 8, 2, 4, 2, 4, 16, 2, 4, 16, 8, 2, 4, 2, 2, 4, 2, 2, 4, 2, 4, 16, 8, 16, 16, 0, 2, 4, 2, 4, 64, 2, 2, 4, 8, 8, 0, 2, 2, 4, 8, 2, 4, 32, 2, 4, 2, 4, 16, 2, 4, 16, 2, 2, 4, 8, 8, 64, 2, 2, 4, 2, 2, 4, 8, 8, 16, 32, 2, 4, 128, 8, 64, 32, 2, 4, 2, 2, 4, 2, 4, 16, 2, 2, 4, 8, 8, 0, 2

Offset: 0

Michel Lagneau, Apr 13 2011

nonn

The second Polignac's Conjecture states that every odd positive integer is the sum of a prime and a power of two. This conjecture was proved false, and the smallest counterexample is 127 because subtracting powers of 2 from 127 produces the composite numbers 126, 123, 119, 111, 95, and 63.

The sequence A006285 gives the odd numbers for which the conjecture fails. Hence, a(n) = 0 for n = (A006285(k)-1)/2 = {0, 63, 74, 125, 165, 168, 186, ...}.

			a(1) = 1 because 2*1 + 1 = 3 = 1 + 2 ;
a(2) = 2 because 2*2 + 1 = 5 = 2 + 3 ;
a(3) = 2 because 2*3 + 1 = 7 = 2 + 5 ;
a(63) = 0 ; a(74) = 0 ; a(125) = 0, ....

David Wells, Prime Numbers: The Most Mysterious Figures In Math, John Wiley & Sons, 2005, p. 175-176.

Carlos Rivera, Puzzle 219, Polignac numbers, The Prime Puzzles and Problems Connection.

Cf. A065381 (primes not of the form p + 2^k, p prime and k >= 0), A156695.

with(numtheory):for n from 1 to 126 do:x:=2*n+1:id:=0:for k from 0 to 50 while(id=0)
  do: for q from 1 to 100 while(id=0) do: p:=ithprime(q): y:=2^k+p:if y=x then
  id:=1:printf(`%d, `,2^k):else fi:od:od:if id=0 then printf(`%d, `,0):else fi:od:

Table[d = 2*n + 1; k = 1; While[k < d && ! PrimeQ[d - k], k = 2*k]; If[k < d, k, 0], {n, 0, 126}]

def A188903(n):
    return next((2**k for k in (0..floor(log(2*n+1,2))) if is_prime(2*n+1-2**k)), 0)
# D. S. McNeil, Apr 14 2011

A232565 a(n) is the smallest k such that 2^(2^n) - 2^k - 1 is prime, or -1 if no such k exists.

Original entry on oeis.org

0, 1, 2, 4, 2, 8, 18, 76, 32, 151, 692, 592, 154, 580, 27365, 11267

Offset: 1

Charles R Greathouse IV, Nov 26 2013

Crocker showed that 2^(2^n) - 1 - 2^a - 2^b is not prime (with n > 2) if a and b are distinct. This sequence demonstrates that the theorem is sharp in the sense that distinctness is required.

If n > 2, then the (largest) prime P(n) = 2^(2^n)-2^a(n)-1 is a de Polignac number (A065381); i.e., P(n)-2^m is not prime. It seems that if n > 6, then |P(n)-2^m| is composite for every natural m and P(n)*2^m-1 is composite (by the dual Riesel conjecture). So if n > 6, then the prime P(n) may be a Riesel number (A182296). For example, the prime P(7) = 2^(2^7)-(2^18+1) is the first candidate (note that 2^18+1 is the smallest de Polignac number of form 2^k+1). Also, by Crocker's theorem, the smallest number of form 2^(2^n)-2^m-1, namely 2^(2^n-1)-1 is a de Polignac number (A006285) and for n > 6 may be a dual Riesel number (A101036). For example, the double Mersenne prime 2^(2^7-1)-1 probably is a dual Riesel number. It is not known whether these are Riesel numbers with a covering set. - Thomas Ordowski, Jan 24 2024

Roger Crocker, "On the sum of a prime and of two powers of two", Pacific Journal of Mathematics 36:1 (1971), pp. 103-107.

Cf. A156695.

a(n)=my(N=2^2^n-1);for(a=1,2^n-1,if(ispseudoprime(N-2^a), return(a)));0

a(15) from Charles R Greathouse IV, Dec 02 2013
a(16) from Daniel Suteu, Oct 11 2020
Name edited by Thomas Ordowski, Jan 24 2024

A064152 Erdős primes: primes p such that all p-k! for 1 <= k! < p are composite.

Original entry on oeis.org

2, 101, 211, 367, 409, 419, 461, 557, 673, 709, 769, 937, 967, 1009, 1201, 1259, 1709, 1831, 1889, 2141, 2221, 2309, 2351, 2411, 2437, 2539, 2647, 2837, 2879, 3011, 3019, 3041, 3049, 3079, 3163, 3217, 3221, 3359, 3389, 3499, 3593, 3671, 3709, 3833, 3851

Offset: 1

Felice Russo, Sep 13 2001

Numbers of Erdős primes <= 10^j for j = 1,2,3, ... are 1, 1, 13, 95, 901, 7875, 71140, 646242, 5901409, ... For large j the asymptotic law seems to be #E(10^j) ~ (1/8)*(10^j/(j*log(10))). If so the sequence is infinite.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section A2, p. 11.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..7875 from T. D. Noe)

Cf. A000142, A065381.

q[n_] := Module[{k = 1}, While[k! < n && ! PrimeQ[n - k!], k++]; k! >= n]; Select[Prime[Range[550]], q] (* Amiram Eldar, Mar 21 2024 *)

{ n=0; for (m=1, 10^9, p=prime(m); k=f=b=1; while ((f*=k) < p, if (isprime(p-f), b=0; break); k++); if (b, write("b064152.txt", n++, " ", p); if (n==1000, break)) ) } \\ Harry J. Smith, Sep 09 2009

A152073 a(n) = largest prime < prime(n) such that prime(n) - a(n) is a power of 2, where prime(n) is the n-th prime; a(n) = 0 if no such prime exists.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 13, 29, 29, 37, 41, 43, 37, 43, 59, 59, 67, 71, 71, 79, 73, 89, 97, 101, 103, 107, 109, 0, 127, 73, 137, 0, 149, 149, 131, 163, 157, 163, 179, 127, 191, 193, 197, 179, 191, 223, 227, 229, 223, 239, 0, 241, 199, 13, 269, 269, 277, 281, 277, 179

Offset: 2

Leroy Quet, Nov 23 2008

a(n) = 0 for odd primes prime(n) appearing in A065381.

Primes p(n) for which there is no such prime a(n) (in which case a(n)=0) are listed in A065381 = (2,127,149,251,331,337,373,...). - M. F. Hasler, Nov 23 2008

			Looking at the primes less than the 10th prime = 29: 29 - 23 = 6, not a power of 2. 29-19 = 10, not a power of 2. 29-17 = 12, not a power of 2. But 29-13 = 16, a power of 2. Since p = 13 is the largest prime p such that 29 - p = a power of 2, then a(10) = 13.

Ivan Neretin, Table of n, a(n) for n = 2..10000

Cf. A065381, A139758, A152075, A152076, A156695.

Table[Max[0, Select[# - 2^Range[0, Log2@#] &@Prime[n], PrimeQ]], {n, 2, 63}] (* Ivan Neretin, Jun 10 2018 *)

A152073(n)=local( q=n=prime(n)); while( q=precprime(q-1), n-q==1<M. F. Hasler, Nov 23 2008

Edited and extended by M. F. Hasler and Ray Chandler, Nov 23 2008

cp's OEIS Frontend

A255816 Number of primes in A065381 less than 10^n.

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A078687 Number of x>=0 such that prime(n)-2^x is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A098237 Composite de Polignac numbers (A006285).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A118958 Primes that cannot be written as 2^k + p with p prime < 2^k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A065380 Primes of the form p + 2^k, p prime and k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A188903 a(n) is the least power of 2 such that 2n+1 - a(n) is prime, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica