A194943 Greatest d such that d*n+b is the least prime in the arithmetic progression k*n+b for some 0 < b < n with gcd(b, n) = 1.
1, 2, 1, 3, 1, 4, 2, 4, 1, 6, 1, 7, 3, 2, 2, 6, 2, 10, 2, 4, 3, 10, 3, 10, 3, 6, 2, 10, 2, 18, 4, 6, 5, 6, 4, 11, 5, 5, 3, 14, 2, 10, 5, 8, 6, 20, 3, 12, 5, 8, 11, 12, 3, 6, 4, 7, 5, 12, 2, 24, 9, 6, 5, 6, 3, 15, 5, 8, 3, 18, 4, 24, 8, 8, 6, 10
Offset: 2
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.
Programs
-
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 *) -
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
Formula
a(n) = floor(A085420(n)/n).
Comments