login
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.
2

%I #32 Dec 12 2021 20:08:37

%S 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,

%T 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,

%U 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

%N 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.

%C a(325) > 2^34 if it exists. - _Michael S. Branicky_, Dec 12 2021

%H Michael S. Branicky, <a href="/A087986/b087986.txt">Table of n, a(n) for n = 1..324</a>

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

%e a(1) = 0 since 1+(2^1)*p = m*q has no solution p,q a consecutive prime pair.

%e a(2*s) = 2 since 1+2^(2*s)*p is divisible by q with {p,q} = {2,3}.

%e a(4*s+3) = 3 since 1+2^(4*s+3)*p is divisible by q with {p,q} = {3,5}.

%e a(12*s+5) = 5 since 1+2^(12*s+5)*p is divisible by q with {p,q} = {5,7}.

%e If n == {1, 7, 9} (mod 12) then larger nontrivial solutions exist.

%e E.g.:

%e n=37: 2^37 = 137438953472;

%e a(37) = 61673 = prime(6206) because 1 + 137438953472*61673 = 8476272577478657 = 61681*137421127697, 61681 = prime(6207).

%e Additional solutions exist for special exponents of 2; e.g., for n == {9, 49} (mod 60), a(n) is usually 29 or occasionally 19.

%t {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}]

%o (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

%o (Python)

%o from sympy import nextprime

%o def a(n):

%o if n == 1: return 0

%o p, q, twon = 2, 3, 2**n

%o while (1 + twon*p)%q: p, q = q, nextprime(q)

%o return p

%o print([a(n) for n in range(1, 94)]) # _Michael S. Branicky_, Dec 11 2021

%Y Cf. A087985.

%K nonn

%O 1,2

%A _Labos Elemer_, Oct 06 2003