A087986 a(n) is the smallest prime p such that 1 + 2^n*p is divisible by the following prime, or 0 if no such prime exists.

0, 2, 3, 2, 5, 2, 3, 2, 19, 2, 3, 2, 41, 2, 3, 2, 5, 2, 3, 2, 43, 2, 3, 2, 1217, 2, 3, 2, 5, 2, 3, 2, 67, 2, 3, 2, 61673, 2, 3, 2, 5, 2, 3, 2, 31, 2, 3, 2, 29, 2, 3, 2, 5, 2, 3, 2, 2087, 2, 3, 2, 691, 2, 3, 2, 5, 2, 3, 2, 29, 2, 3, 2, 449, 2, 3, 2, 5, 2, 3, 2, 31, 2, 3, 2, 229, 2, 3, 2, 5, 2, 3, 2, 89

Offset

1,2

Comments

a(325) > 2^34 if it exists. - Michael S. Branicky, Dec 12 2021

Links

Michael S. Branicky, Table of n, a(n) for n = 1..324

Formula

a(n) = A087985(2^n).

Example

a(1) = 0 since 1+(2^1)*p = m*q has no solution p,q a consecutive prime pair.
a(2*s) = 2 since 1+2^(2*s)*p is divisible by q with {p,q} = {2,3}.
a(4*s+3) = 3 since 1+2^(4*s+3)*p is divisible by q with {p,q} = {3,5}.
a(12*s+5) = 5 since 1+2^(12*s+5)*p is divisible by q with {p,q} = {5,7}.
If n == {1, 7, 9} (mod 12) then larger nontrivial solutions exist.
E.g.:
n=37: 2^37 = 137438953472;
a(37) = 61673 = prime(6206) because 1 + 137438953472*61673 = 8476272577478657 = 61681*137421127697, 61681 = prime(6207).
Additional solutions exist for special exponents of 2; e.g., for n == {9, 49} (mod 60), a(n) is usually 29 or occasionally 19.

Mathematica

{k=0, nu=0; sq={}}; Table[Print[{n-1, Min[Prime[sq]]}]; nu=0; sq={}; Do[s=Mod[(2^n)*Prime[x]+1, Prime[x+1]]; If[Equal[s, 0], nu=nu+1; sq=Append[sq, n]], {x, 1, 10000000}], {n, 1, 257}]

Prog

(PARI) a(n)={my(m=2^n); if(n==1, 0, forprime(p=2, oo, if((1 + m*p) % nextprime(p+1)==0, return(p))))} \\ Andrew Howroyd, Dec 11 2021
(Python)
from sympy import nextprime
def a(n):
    if n == 1: return 0
    p, q, twon = 2, 3, 2**n
    while (1 + twon*p)%q: p, q = q, nextprime(q)
    return p
print([a(n) for n in range(1, 94)]) # Michael S. Branicky, Dec 11 2021

Crossrefs

Cf. A087985.

Sequence in context: A265111 A101876 A260218 * A129088 A086418 A100761

Adjacent sequences: A087983 A087984 A087985 * A087987 A087988 A087989

Keyword

nonn

Author

Labos Elemer, Oct 06 2003

Status

approved