A067760 -id:A067760 - cp's OEIS frontend

A263874 Integers for which the smallest k in A067760 such that n + 2^k is prime increases.

1, 7, 23, 31, 47, 61, 139, 271, 287, 773, 2131, 40291

Offset: 1

Arkadiusz Wesolowski, Oct 28 2015

mersenneforum.org, Five or Bust - The Dual Sierpinski Problem

A263875 gives the record values.

a=1; forstep(n=1, 773, 2, k=1; while(!ispseudoprime(n+2^k), k++); if(k+1>a, print1(n, ", "); a=k+1));

A276495 Odd numbers not of the form p + 2^m with p prime and m >= 0 for which the smallest k in A067760 such that n + 2^k is prime increases.

Original entry on oeis.org

1, 127, 251, 1657, 1777, 1973, 3181, 21893, 31951, 50839, 67607, 138977

Offset: 1

Arkadiusz Wesolowski, Sep 05 2016

There exist de Polignac numbers n such that for all k >= 1 the numbers n + 2^k are composite. It is conjectured that 30666137 is the smallest such number.

a(13) >= 453143.

Cf. A006285, A067760, A263644.

A276496 gives the record values.

lst:=[]; c:=0; for n in [1..31951 by 2] do m:=-1; repeat m+:=1; a:=n-2^m; until a lt 1 or IsPrime(a); if a lt 1 then k:=0; repeat k+:=1; b:=n+2^k; until IsPrime(b); if k gt c then Append(~lst, n); c:=k; end if; end if; end for; lst;

A094076 Smallest k such that prime(n) + 2^k is prime, or -1 if no such prime exists.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 2, 3, 1, 4, 2, 1, 2, 5, 3, 1, 8, 2, 1, 4, 2, 7, 3, 2, 1, 2, 1, 2, 7, 2, 3, 1, 10, 1, 4, 4, 2, 5, 3, 1, 4, 1, 2, 1, 6, 4, 2, 1, 2, 3, 1, 4, 5, 9, 3, 1, 20, 2, 1, 6, 7, 2, 1, 2, 5, 4, 4, 1, 2, 27, 3, 4, 4, 2, 15, 3, 2, 3, 10, 1, 8, 1, 4, 2, 7, 3, 2, 1, 2, 5, 3, 2, 3, 2, 7, 5, 1, 6, 4, 4, 9, 3, 1

Offset: 1

Reinhard Zumkeller, Apr 29 2004

nonn

Conjecture: k > 0 for all n.
For all primes p < 1000 there exists a k such that p + 2^k is prime. However, for p = prime(321) = 2131, p + 2^k is not prime for all k < 30000. The conjecture may be in question. Similarly, I cannot find k such that p + 2^k is prime for p = 7013, 8543, 10711, 14033 for k < 20000. - Cino Hilliard, Jun 27 2005
prime(80869739673507329) = 3367034409844073483, so a(80869739673507329) = -1 since 2^k + 3367034409844073483 is covered by {3, 5, 17, 257, 641, 65537, 6700417}. - Charles R Greathouse IV, Feb 08 2008
k=271129 is a smaller counterexample: gcd(k+2^n,2^24-1)>1 always holds using (1 mod 2, 0 mod 4, 2 mod 8, 6 mod 24, 14 mod 24 and 22 mod 24) as a covering for the n's. k with gcd(k+2^n,2^24-1)>1 always true were first found by Erdos (see refs). - Bruno Mishutka (bruno.mishutka(AT)googlemail.com), Mar 11 2009

			p = 773, k = 995, p + 2^k is prime.
p = 5101, k = 5760, p + 2^k is prime.

A. O. L. Atkin and B. J. Birch, eds., Computers in Number Theory, Academic Press, 1971, page 74.

Jinyuan Wang, Table of n, a(n) for n = 1..7771 (terms 1..3000 from Charles R Greathouse IV).
P. Erdős, On integers of the form 2^k + p and some related problems, Summa Brasil. Math. 2 (1950), pp. 113-123. [From Bruno Mishutka (bruno.mishutka(AT)googlemail.com), Mar 11 2009]
Charles R Greathouse IV, Constructing a covering set for numbers 2^k + p [Cached copy]

Cf. A067760, A137715.

sk[n_]:=Module[{p=Prime[n],k=1},While[!PrimeQ[p+2^k],k++];k]; Join[{0}, Array[sk,110,2]] (* Harvey P. Dale, Jul 07 2013 *)

pplus2ton(n,m) = { local(k,s,p,y,flag); s=0; forprime(p=2,n, flag=1; for(k=0,m, y=p+2^k; if(ispseudoprime(y), print1(k, ", "); s++; flag=0; break) ); if(flag, return(p))); print(); print(s); } \\ Cino Hilliard, Jun 27 2005

More terms from Don Reble, May 02 2004
More terms from Cino Hilliard, Jun 27 2005
More terms from Charles R Greathouse IV, Feb 08 2008

A092131 Distance from 2^n to the next prime.

Original entry on oeis.org

0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 17, 27, 3, 1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 15, 29, 3, 11, 3, 11, 15, 17, 25, 53, 31, 9, 7, 23, 15, 27, 15, 29, 7, 59, 15, 5, 21, 69, 55, 21, 21, 5, 159, 3, 81, 9, 69, 131, 33, 15, 135, 29, 13, 131, 9, 3, 33, 29, 25, 11, 15, 29, 37, 33, 15, 11, 7, 23

Offset: 1

Helmut Richter (richter(AT)lrz.de), Mar 30 2004

Essentially the same as A013597. - T. D. Noe, Jul 17 2007
From Jianing Song, May 28 2024: (Start)
Not every odd number is present, as no term can be equal to a Sierpiński number (for example 78557); cf. A076336. See also A067760.
Conjecture: Every odd number which is not a Sierpiński number is a term. In other words, for every odd k which is not a Sierpiński number, there exists some n >= 1 such that 2^n + 1, 2^n + 3, ..., 2^n + (k-2) are all composite while 2^n + k is prime. (End)

			a(13)=17 because 2^13=8192 and the next prime is 8209=8192+17.

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

Cf. A013597.
Equivalent sequence for previous prime: A013603.
Cf. A000079, A007920, A067760, A076336.

Join[{0},NextPrime[#]-#&/@(2^Range[2,80])] (* Harvey P. Dale, Jun 06 2012 *)

for(i=1,100,x=2^i;print1(nextprime(x)-x,","))

a(n) = nextprime(2^n) - 2^n.

a(n) = A007920(A000079(n)). - Michel Marcus, Oct 19 2022

A033875 Skipping from prime to prime by least powers of 2.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 47, 79, 83, 211, 227, 229, 233, 241, 257, 769, 773

Offset: 1

David W. Wilson

nonn

Is this sequence infinite? - Charles R Greathouse IV, Jan 24 2017

			2 + 2^0 = 3,
3 + 2^1 = 5,
a(22) = a(21) + 2^955,
a(23) = a(22) + 2^468.

Zak Seidov, Table of n, a(n) for n = 1..23

Cf. A059661, A067760, A139803 (corresponding powers of 2).

NestList[(k = 0; While[! PrimeQ[q = # + 2^k], k++]; q) &, 2, 20] (* Zak Seidov, Jan 24 2017 *)

a(1) = 2, a(n+1) = a(n) + 2^k; a(n+1) prime, k minimal.

a(n) = a(n-1) + 2^A067760((a(n-1)-1)/2) for n >= 3. - Pontus von Brömssen, Jan 08 2023

A361902 Least k such that n+A000045(k) is prime, or -1 if no such k exists.

Original entry on oeis.org

3, 1, 0, 0, 1, 0, 1, 0, 4, 3, 1, 0, 1, 0, 4, 3, 1, 0, 1, 0, 4, 3, 1, 0, 5, 9, 4, 3, 1, 0, 1, 0, 5, 6, 4, 3, 1, 0, 4, 3, 1, 0, 1, 0, 4, 3, 1, 0, 5, 9, 4, 3, 1, 0, 5, 9, 4, 3, 1, 0, 1, 0, 5, 6, 4, 3, 1, 0, 4, 3, 1, 0, 1, 0, 5, 6, 4, 3, 1, 0, 4, 3, 1, 0, 5, 12, 4

Offset: 0

Pontus von Brömssen, Mar 28 2023

sign

Suggested by A361509.
2 does not appear because A000045(1) = A000045(2).
When n >= 3 and a(n) != -1, a(n) is divisible by 3 if and only if n is odd, because A000045(k) is even if and only if k is divisible by 3.
The least n for which a(n) = -1 is one of 7123, 11009, and 14475. When n is 7123 or 11009, either a(n) > 60000 or a(n) = -1.

			The first Fibonacci number F such that 25+F is prime is F = 34 = A000045(9), so a(25) = 9.

Pontus von Brömssen, Table of n, a(n) for n = 0..7122
Robert Gerbicz, Re: Add a Fibonacci number to get a prime, SeqFan mailing list, March 28, 2023.

Cf. A000045, A067760, A322004 (negative n), A361509, A361510, A361997 (records), A361998 (indices of records), A361999 (first occurrences).

a[n_] := Module[{k = 0}, While[! PrimeQ[n + Fibonacci[k]], k++]; k]; Array[a, 100, 0] (* Amiram Eldar, Mar 30 2023 *)

a(n) = my(k=0); while (!isprime(n+fibonacci(k)), k++); k; \\ Michel Marcus, Mar 30 2023

from sympy import isprime,fibonacci
from itertools import count
def A361902(n):
    # Note: the function hangs if a(n) = -1.
    return next(k for k in count() if isprime(n+fibonacci(k)))

a(n) = 0 if and only if n is prime.

a(n) = -1 if n == 14475 (mod m), where m = 2*3*5*7*11*23*31 = 1647030 (see Gerbicz link).

A260350 Define g(k) = min(n: n >= 0, 2^n + k prime). Then a(n) = min(odd k: g(k) = n).

Original entry on oeis.org

1, 3, 7, 23, 31, 47, 199, 83, 61, 257, 139, 953, 991, 647, 1735, 383, 511, 1337, 1069, 713, 271, 1937, 3223, 5213, 751, 8477, 4339, 353, 1501, 287, 829, 1553, 2371, 1811, 11185, 3023, 7381, 7937, 6439, 1433, 13975, 2897, 4183

Offset: 0

Hugo van der Sanden, Jul 23 2015

nonn

Previous name: a(n) = min(k : A067760((k-1)/2)) = n.
a(n) is the first odd number k for which 2^m + k is the first prime value, as m ranges from 0 to n, or 0 if no such k exists. Thus it is the first k for which A067760((k-1)/2) = n, and therefore also the first k for which you need to test primality of exactly n values to show that it is not a dual Sierpiński number.
In the name, g(n) = A067760(n) except for n=1. - Michel Marcus, Apr 07 2018

			2^i + 7 is composite for i < 2 (with values 8, 9) but prime for i = 2 (11); the smaller odd numbers 1, 3 and 5 each yield a prime for smaller i, so a(2) = 7.

Hugo van der Sanden, Table of n, a(n) for n = 0..1087

Cf. A067760, A076336, A260349.

g(k) = {my(j=0); while (!isprime(2^j+k), j++); j;}
a(n) = {my(k = 1); while(g(k) != n, k+=2); k;} \\ Michel Marcus, Apr 07 2018

For n>=2, a(n) = (min(k : A067760((k-1)/2)) = n). - Michel Marcus, Apr 07 2018

New name from Hugo van der Sanden and Michel Marcus, Apr 07 2018

A133831 Least positive number k != n such that the binary trinomial 1 + 2^n + 2^k is prime, or 0 if there is no such k.

Original entry on oeis.org

2, 1, 1, 1, 2, 1, 1, 9, 3, 3, 2, 1, 4, 5, 1, 1, 11, 1, 6, 5, 4, 7, 3, 9, 27, 17, 15, 1, 15, 1, 6, 458465, 4, 9, 14, 13, 3, 11, 25, 57, 6, 7, 46, 17, 7, 15, 2, 1009, 30, 23, 6, 21, 2, 33, 1, 1265, 3, 69, 14, 5, 6, 21, 19, 2241, 30, 3, 1, 5, 34, 19, 26, 17, 19, 17, 5, 33, 15, 23, 27

Offset: 1

T. D. Noe, Sep 26 2007

nonn

Does such k exist (so that a(n) is nonzero) for all n? These binary trinomials can also be written as f*2^n+1, where f=2^m+1 for some m, which is reminiscent of the Sierpinski problem (see A076336). Hence if there are no Sierpinski numbers of the form 2^m+1, then a(n) is nonzero for all n.

The PFGW program was used to find a(32), which produces a 138012-digit probable prime. If a(256) is nonzero, it is greater than 10^6.

T. D. Noe, Table of n, a(n) for n = 1..255
Henri Lifchitz and Renaud Lifchitz (Editors), Search for 2^n+2^m+1, PRP Top Records.

Cf. A057732, A059242, A057196, A057200, A081091 (various forms of prime binary trinomials).
Closely related problems: A040076 (see also A076336), A067760, A133830 (k < n), A133832 (k > n).
Cf. A095056.

mx=4000; Table[s=1+2^n; k=1; While[k==n || (k

Edited by Peter Munn, Sep 29 2024

A263875 a(n) = least positive k such that A263874(n) + 2^k is prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 10, 20, 29, 955, 4583176, 9092392

Offset: 1

Arkadiusz Wesolowski, Oct 28 2015

A263874 gives where the records occur.

mersenneforum.org, Five or Bust - The Dual Sierpinski Problem

Cf. A067760, A263874.

a=1; forstep(n=1, 773, 2, k=1; while(!ispseudoprime(n+2^k), k++); if(k+1>a, print1(k, ", "); a=k+1));

A123252 a(n) = smallest prime of the form 2^k + 2n - 1, k = 0, 1, ..., or 0 if there is none.

Original entry on oeis.org

3, 5, 7, 11, 11, 13, 17, 17, 19, 23, 23, 31, 29, 29, 31, 47, 37, 37, 41, 41, 43, 47, 47, 79, 53, 53, 61, 59, 59, 61, 317, 67, 67, 71, 71, 73, 89, 79, 79, 83, 83, 211, 89, 89, 97, 107, 97, 97, 101, 101, 103, 107, 107, 109, 113, 113, 241, 131, 149, 127, 137, 127, 127, 131

Offset: 1

Cino Hilliard, Oct 08 2006

nonn

If n == 0 (mod 3) then the exponent k must be odd, if n>1 and n == 1 (mod 3) then k must be even and if n == 2 (mod 3) then k can be either.

Records: 3, 5, 7, 11, 13, 17, 19, 23, 31, 47, 79, 317, 1163, 1048847, 536871199, 2^955 + 773, ..., . - Robert G. Wilson v

			For n = 4, p = 2 -> 2^2+(2*4-1) = 11, the fourth entry because 2^1+(2*4-1) which equals 9 is not a prime.

Cf. A067760.

f[n_] := Block[{p = 1}, While[ !PrimeQ[2^p + 2n - 1], p++ ]; 2^p + 2n - 1]; Array[f, 64] (* Robert G. Wilson v *)

g2(n) = forstep(k=1,n,2,for(p=1,n,y=k+2^p;if(isprime(y),print1(y",");break)))

a(n) = 2^A067760(n-1) + 2n-1 if A067760(n-1) > 0, 0 if A067760(n-1) = 0. - Robert Israel, Jan 14 2017

Edited and extended by Robert G. Wilson v, Nov 11 2006

Name edited by Robert Israel, Jan 14 2017

cp's OEIS Frontend

A263874 Integers for which the smallest k in A067760 such that n + 2^k is prime increases.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A276495 Odd numbers not of the form p + 2^m with p prime and m >= 0 for which the smallest k in A067760 such that n + 2^k is prime increases.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

A094076 Smallest k such that prime(n) + 2^k is prime, or -1 if no such prime exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A092131 Distance from 2^n to the next prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A033875 Skipping from prime to prime by least powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A361902 Least k such that n+A000045(k) is prime, or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A260350 Define g(k) = min(n: n >= 0, 2^n + k prime). Then a(n) = min(odd k: g(k) = n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A133831 Least positive number k != n such that the binary trinomial 1 + 2^n + 2^k is prime, or 0 if there is no such k.

Views