%I #46 May 25 2024 15:58:08
%S 1,1,1,2,1,3,3,2,1,15,12,6,3,5,4,2,1,6,3,11,7,11,25,20,10,5,7,15,12,6,
%T 3,35,18,9,12,6,3,15,10,5,6,3,9,9,15,35,19,27,15,14,7,14,7,20,10,5,27,
%U 29,54,27,31,36,18,9,12,6,3,9,31,23,39,39,40,20,10,5,58,29,15,36,18,9,13
%N a(n) is the smallest k such that k*2^n + 1 is prime.
%C From Ulrich Krug (leuchtfeuer37(AT)gmx.de), Jun 05 2010: (Start)
%C If a(i) = 2 * m then a(i+1) = m.
%C Proof: (I) a(i) = 2*m, 2*m * 2^i + 1 = m*2^(i+1) + 1 prime, so a(i+1) <= m;
%C (II) if a(i+1) = m-d for an integer d > 0, (m-d) * 2^(i+1) + 1 = (2*m-2*d) * 2^i + 1 prime;
%C (2m-2d) < 2m contradiction to a(i) = 2 * m, d = 0.
%C (End)
%C Conjecture: for n > 0, a(n) = k < 2^n, so k*2^n + 1 is a Proth prime A080076. - _Thomas Ordowski_, Apr 13 2019
%H T. D. Noe, <a href="/A035050/b035050.txt">Table of n, a(n) for n = 0..1000</a>
%H Gareth A. Jones and Alexander K. Zvonkin, <a href="https://www.labri.fr/perso/zvonkin/Research/ProjPrimesShort.pdf">Groups of prime degree and the Bateman-Horn conjecture</a>, 2021.
%H <a href="/index/Pri#primes_AP">Index entries for sequences related to primes in arithmetic progressions</a>
%F a(n) << 19^n by Xylouris' improvement to Linnik's theorem. - _Charles R Greathouse IV_, Dec 10 2013
%e a(3)=2 because 1*2^3 + 1 = 9 is composite, 2*2^3 + 1 = 17 is prime.
%e a(99)=219 because 2^99k + 1 is not prime for k=1,2,...,218. The first term which is not a composite number of this arithmetic progression is 2^99*219 + 1.
%t a = {}; Do[k = 0; While[ ! PrimeQ[k 2^n + 1], k++ ]; AppendTo[a, k], {n, 0, 100}]; a (* _Artur Jasinski_ *)
%t Table[Module[{k=1,n2=2^n},While[!PrimeQ[k*n2+1],k++];k],{n,0,90}] (* _Harvey P. Dale_, May 25 2024 *)
%o (PARI) a(n) = {my(k = 1); while (! isprime(2^n*k+1), k++); k;}
%o (Magma) sol:=[];m:=1; for n in [0..82] do k:=0; while not IsPrime(k*2^n+1) do k:=k+1; end while; sol[m]:=k; m:=m+1; end for; sol; // _Marius A. Burtea_, Jun 05 2019
%Y Analogous case is A034693. Special subscripts (n's for a(n)=1) are the exponents of known Fermat primes: A000215. See also Fermat numbers A000051.
%Y Cf. A007522, A057778, A080076, A085427, A087522, A126717, A127575, A127576, A127577, A127578, A127580, A127581, A127586.
%K nonn
%O 0,4
%A _Labos Elemer_