cp's OEIS Frontend

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.

%I A194943 #37 May 20 2023 13:39:31
%S A194943 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,
%T A194943 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,
%U A194943 5,6,3,15,5,8,3,18,4,24,8,8,6,10
%N 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.
%C A194943 a(n) exists due to Linnik's theorem; thus a(n) < c * n^4.2 for some constant c.
%C A194943 Heath-Brown's conjecture on Linnik's theorem implies that a(n) < n.
%C A194943 On the GRH, a(n) << phi(n) * log(n)^2 * phi(n)/n.
%C A194943 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.
%H A194943 Charles R Greathouse IV, <a href="/A194943/b194943.txt">Table of n, a(n) for n = 2..10000</a>
%H A194943 A. Granville and C. Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/least.pdf">On the least prime in certain arithmetic progressions</a>, Journal of the London Mathematical Society 2:41 (1990), pp. 193-200.
%H A194943 D. R. Heath-Brown, <a href="https://web.archive.org/web/20160317102203/http://eprints.maths.ox.ac.uk/166/1/linnik.pdf">Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression</a>, Proceedings of the London Mathematical Society 3:64 (1992), pp. 265-338.
%H A194943 C. Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/paper24.pdf">A note on the least prime in an arithmetic progression</a>, Journal of Number Theory 12 (1980), pp. 218-223.
%F A194943 a(n) = floor(A085420(n)/n).
%t A194943 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 *)
%o A194943 (PARI) p(b,d)=my(k=d+b);while(!isprime(k),k+=d);(k-b)/d
%o A194943 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
%o A194943 (Python)
%o A194943 from math import gcd
%o A194943 from gmpy2 import is_prime
%o A194943 def p(b, d):
%o A194943     k = d + b
%o A194943     while not is_prime(k):
%o A194943         k += d
%o A194943     return (k-b)//d
%o A194943 def A194943(n):
%o A194943     return max(p(b, n) for b in range(1, n) if gcd(b, n) == 1)
%o A194943 print([A194943(n) for n in range(2, 82)]) # _Michael S. Branicky_, May 18 2023 after _Charles R Greathouse IV_
%Y A194943 Cf. A085420. Records are in A362850, A362851.
%K A194943 nonn,nice
%O A194943 2,2
%A A194943 _Charles R Greathouse IV_, Sep 05 2011