login
Numbers k such that 2^k + 3 is prime.
43

%I #96 Dec 01 2023 15:48:15

%S 1,2,3,4,6,7,12,15,16,18,28,30,55,67,84,228,390,784,1110,1704,2008,

%T 2139,2191,2367,2370,4002,4060,4062,4552,5547,8739,17187,17220,17934,

%U 20724,22732,25927,31854,33028,35754,38244,39796,40347,55456,58312,122550,205962,235326,363120,479844,685578,742452,1213815,1434400,1594947,1875552,1940812,2205444

%N Numbers k such that 2^k + 3 is prime.

%C Some of the larger entries may only correspond to probable primes.

%C A number k is in this sequence iff A062709(k) is in A057733; this is the case iff A257273(k) is in A125246. - _M. F. Hasler_, Apr 27 2015

%D Mike Oakes, posting to primenumbers(AT)yahoogroups.com on Jul 08 2001

%H Keith Conrad, <a href="https://kconrad.math.uconn.edu/blurbs/ugradnumthy/squaresandinfmanyprimes.pdf">Square patterns and infinitude of primes</a>, University of Connecticut, 2019.

%H Henri Lifchitz and Renaud Lifchitz (Editors), <a href="http://www.primenumbers.net/prptop/searchform.php?form=2%5En%2B3">Search for 2^n+3</a>, PRP Top Records.

%F Here is an LLT-like algorithm, using a cycle of the digraph x^2-2 modulo N, that finds terms of this sequence generating a PRP (PRobable Prime) of A057733 numbers: N=2^k+3; S0=(N-5)/2; s(0)=S0; s(i+1)=s(i)^2-2 modulo N; if s(k-1) == S0 then N is prime. - _Tony Reix_, Aug 27 2015

%e For k = 6, 2^6 + 3 = 67 is prime.

%e For k = 28, 2^28 + 3 = 268435459 is prime.

%t Select[Range[10000], PrimeQ[2^# + 3] &] (* _Vincenzo Librandi_, Apr 27 2015 *)

%o (PARI) for(n=1, 2200, if(isprime(2^n+3), print1(n, ", ")));

%o (PARI) for (n=1, 2, if (isprime(2^n+3), print1(n, ", "))); for(n=3, 100000, N=2^n+3 ; S=(N-5)/2 ; x=S ; for(j=1, n-1, x=Mod(x^2-2, N)) ; if(x==S , print1(n, ", "))) \\ produces terms corresponding to probable primes, see formula; _Tony Reix_, Aug 27 2015

%o (Magma) [n: n in [0..1000] | IsPrime(2^n+3)]; // _Vincenzo Librandi_, Apr 27 2015

%Y Cf. A050414, A057733, A062709, A094076, A125246, A257273.

%Y Cf. A019434 (primes 2^k+1), this sequence (2^k+3), A059242 (2^k+5), A057195 (2^k+7), A057196(2^k+9), A102633 (2^k+11), A102634 (2^k+13), A057197 (2^k+15), A057200 (2^k+17), A057221 (2^k+19), A057201 (2^k+21), A057203 (2^k+23).

%K nice,nonn

%O 1,2

%A _G. L. Honaker, Jr._, Oct 29 2000

%E More terms from _Jason Earls_, Jul 18 2001 and _Mike Oakes_, Jul 28 2001

%E a(47)-a(50) from _Donovan Johnson_ 2006, verified by _Paul Bourdelais_, Mar 22 2012

%E a(51) is a probable prime based on trial factoring to 1E9 and PRP testing base 3,5,7 (PFGW v3.3.1). Discovered by _Paul Bourdelais_, Apr 09 2012

%E a(52)-a(54) from _Paul Bourdelais_, Jun 18 2019

%E a(55) from _Paul Bourdelais_, Jul 16 2019

%E a(56) from _Paul Bourdelais_, Apr 22 2020

%E a(57) from _Paul Bourdelais_, Jun 12 2020

%E a(58) from _Paul Bourdelais_, Aug 04 2020