cp's OEIS Frontend

A085420 For each n, let p(n,b) be the smallest prime in the arithmetic progression k*n+b, with k > 0. Then a(n) = max(p(n,b)) with 0 < b < n and gcd(b,n) = 1.

%I A085420 #26 Feb 16 2025 08:32:50
%S A085420 2,3,7,7,19,11,29,23,43,19,71,23,103,53,43,43,103,53,191,59,97,79,233,
%T A085420 73,269,103,173,83,317,79,577,151,227,193,239,157,439,191,233,157,587,
%U A085420 107,467,257,389,307,967,191,613,269,421,601,659,199,353,233,433,317,709
%N A085420 For each n, let p(n,b) be the smallest prime in the arithmetic progression k*n+b, with k > 0. Then a(n) = max(p(n,b)) with 0 < b < n and gcd(b,n) = 1.
%C A085420 Linnik proved that there are n0 and L such that a(n) < n^L for all n > n0. It has been conjectured that a(n) < n^2. The sequence A034694 has the primes p(n,1).
%C A085420 a(n) is also the maximum term in row n of A060940, which defines a(1). A007918(n+1) is the minimum term in row n of A060940. - _Seiichi Manyama_, Apr 02 2018
%D A085420 P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, pp. 277-284.
%H A085420 T. D. Noe, <a href="/A085420/b085420.txt">Table of n, a(n) for n = 1..10000</a> (corrected by Michel Marcus, Jan 19 2019)
%H A085420 A. Granville, <a href="http://www.dms.umontreal.ca/~andrew/PDF/laval.pdf">Least primes in arithmetic progressions</a>, Théorie des nombres / Number Theory (ed. J. M. De Koninck & C. Levesque), (de Gruyter, New York, 1989), 306-321.
%H A085420 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LinniksTheorem.html">Linnik's Theorem</a>
%e A085420 a(5) = 19 because p(5,1) = 11, p(5,2) = 7, p(5,3) = 13 and p(5,4) = 19.
%t A085420 minP[n_, a_] := Module[{k, p}, If[GCD[n, a]>1, p=0, k=1; While[ !PrimeQ[k*n+a], k++ ]; p=k*n+a]; p]; Table[Max[Table[minP[n, i], {i, n-1}]], {n, 2, 100}]
%o A085420 (PARI) p(n,b)=while(!isprime(b+=n),); ba(n)=my(t=p(n,1));for(b=2,n-1,if(gcd(n,b)==1,t=max(t,p(n,b))));t \\ _Charles R Greathouse IV_, Sep 08 2012
%Y A085420 A038026 is a lower bound.
%Y A085420 Cf. A034694.
%K A085420 nonn
%O A085420 1,1
%A A085420 _T. D. Noe_, Jun 29 2003
%E A085420 a(1) defined via A060940 by _Seiichi Manyama_, Apr 02 2018