cp's OEIS Frontend

A035096 a(n) is the smallest k such that prime(n)*k+1 is prime.

%I A035096 #45 Mar 19 2025 08:27:15
%S A035096 1,2,2,4,2,4,6,10,2,2,10,4,2,4,6,2,12,6,4,8,4,4,2,2,4,6,6,6,10,2,4,2,
%T A035096 6,4,8,6,10,4,14,2,2,6,2,4,18,4,10,12,24,12,2,2,6,2,6,6,8,6,4,2,6,2,4,
%U A035096 6,6,26,6,10,6,10,14,2,6,4,12,12,24,6,8,4,2,10,2,4,10,2,8,30
%N A035096 a(n) is the smallest k such that prime(n)*k+1 is prime.
%C A035096 These arithmetic progressions have prime differences. Note that both the terms of generated by this k values and the differences are primes as well.
%C A035096 This is one possible generalization of "the least prime problem in special arithmetic progressions" when n in the nk+1 form is replaced by n-th prime number.
%C A035096 Note that Dirichlet's theorem on primes in arithmetic progressions implies that a(n) always exists. - _Max Alekseyev_, Jul 11 2008
%C A035096 If a(n)=2, prime(n) is a Sophie Germain prime (A005384). Among the first 10^6 terms, the largest is a(330408) = 234. - _Zak Seidov_, Jan 28 2012
%H A035096 T. D. Noe, <a href="/A035096/b035096.txt">Table of n, a(n) for n = 1..10000</a>
%H A035096 Eric Weisstein's World of Math, <a href="https://mathworld.wolfram.com/DirichletsTheorem.html">Dirichlet's theorem</a>.
%H A035096 <a href="/index/Pri#primes_AP">Index entries for sequences related to primes in arithmetic progressions</a>.
%F A035096 a(n) = (A035095(n)-1)/A000040(n). - _Zak Seidov_, Dec 27 2013
%e A035096 a(15)=6 because the 15th prime is 47, and the smallest k such that 47k+1 is prime is k=6, for which 47k+1=283.
%t A035096 Reap[Sow[1]; Do[p = Prime[n]; k = 2; While[! PrimeQ[k*p + 1], k = k + 2]; Sow[k], {n, 2, 10^4}]][[2, 1]] (* _Zak Seidov_, Jan 28 2012 *)
%t A035096 f[n_] := Block[{p = Prime@ n}, q = 1 + 2p; While[ !PrimeQ@ q, q += 2p]; (q - 1)/p]; f[1] = 1; Array[f, 88] (* _Robert G. Wilson v_, Dec 27 2014 *)
%o A035096 (Magma)
%o A035096 S:=[];
%o A035096 k:=1;
%o A035096 for n in [1..90] do
%o A035096   while not IsPrime(k*NthPrime(n)+1) do
%o A035096        k:=k+1;
%o A035096   end while;
%o A035096   Append(~S, k);
%o A035096   k:=1;
%o A035096 end for;
%o A035096 S; // _Bruno Berselli_, Apr 18 2013
%o A035096 (PARI) a(n) = if(n == 1, 1, my(t = 2*prime(n), m = t + 1); while(!isprime(m), m += t); 2*(m - 1)/t); \\ _Amiram Eldar_, Mar 19 2025
%Y A035096 Smallest k such that k*n+1 is prime is A034693.
%Y A035096 Sophie Germain primes are in A005384.
%Y A035096 Cf. A000040, A035095. - _Zak Seidov_, Dec 27 2013
%Y A035096 Cf. A117673.
%K A035096 nonn
%O A035096 1,2
%A A035096 _Labos Elemer_