OFFSET
2,2
COMMENTS
a(n) exists due to Linnik's theorem; thus a(n) < c * n^4.2 for some constant c.
Heath-Brown's conjecture on Linnik's theorem implies that a(n) < n.
On the GRH, a(n) << phi(n) * log(n)^2 * phi(n)/n.
Pomerance shows that a(n) > (e^gamma + o(1)) log(n) * phi(n)/n, and Granville & Pomerance conjecture that a(n) >> log(n)^2 * phi(n)/n.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions, Journal of the London Mathematical Society 2:41 (1990), pp. 193-200.
D. R. Heath-Brown, Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proceedings of the London Mathematical Society 3:64 (1992), pp. 265-338.
C. Pomerance, A note on the least prime in an arithmetic progression, Journal of Number Theory 12 (1980), pp. 218-223.
FORMULA
a(n) = floor(A085420(n)/n).
MATHEMATICA
p[b_, d_] := Module[{k = b+d}, While[ !PrimeQ[k], k += d]; (k-b)/d]; a[n_] := Module[{r = p[1, n]}, For[b = 2, b <= n-1, b++, If[GCD[b, n] > 1, Null, r = Max[r, p[b, n]]]]; r]; Table[a[n], {n, 2, 100}] (* Jean-François Alcover, Oct 02 2013, translated from Pari *)
PROG
(PARI) p(b, d)=my(k=d+b); while(!isprime(k), k+=d); (k-b)/d
a(n)=my(r=p(1, n)); for(b=2, n-1, if(gcd(b, n)>1, next); r=max(r, p(b, n))); r
(Python)
from math import gcd
from gmpy2 import is_prime
def p(b, d):
k = d + b
while not is_prime(k):
k += d
return (k-b)//d
def A194943(n):
return max(p(b, n) for b in range(1, n) if gcd(b, n) == 1)
print([A194943(n) for n in range(2, 82)]) # Michael S. Branicky, May 18 2023 after Charles R Greathouse IV
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Charles R Greathouse IV, Sep 05 2011
STATUS
approved