A085420 -id:A085420 - cp's OEIS frontend

A034694 Smallest prime == 1 (mod n).

2, 3, 7, 5, 11, 7, 29, 17, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 41, 43, 23, 47, 73, 101, 53, 109, 29, 59, 31, 311, 97, 67, 103, 71, 37, 149, 191, 79, 41, 83, 43, 173, 89, 181, 47, 283, 97, 197, 101, 103, 53, 107, 109, 331, 113, 229, 59, 709, 61, 367, 311

Offset: 1

Labos Elemer, David W. Wilson, Spring 1998

Thangadurai and Vatwani prove that a(n) <= 2^(phi(n)+1)-1. - T. D. Noe, Oct 12 2011
Conjecture: a(n) < n^2 for n > 1. - Thomas Ordowski, Dec 19 2016
Eric Bach and Jonathan Sorenson show that, assuming GRH, a(n) <= (1 + o(1))*(phi(n)*log(n))^2 for n > 1. See the abstract of their paper in the Links section. - Jianing Song, Nov 10 2019
a(n) is the smallest prime p such that the multiplicative group modulo p has a subgroup of order n. - Joerg Arndt, Oct 18 2020

			If n = 7, the smallest prime in the sequence 8, 15, 22, 29, ... is 29, so a(7) = 29.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.
P. Ribenboim, The Book of Prime Number Records. Chapter 4,IV.B.: The Smallest Prime In Arithmetic Progressions, 1989, pp. 217-223.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Bach and Jonathan Sorenson, Explicit bounds for primes in residue classes, Mathematics of Computation, 65(216) (1996), 1717-1735.
Steven R. Finch, Linnik's Constant
S. Graham, On Linnik's Constant, Acta Arithm. 39, 1981, pp. 163-179.
I. Niven and B. Powell, Primes in Certain Arithmetic Progressions, Amer. Math. Monthly 83(6) (1976), 467-469.
R. Thangadurai and A. Vatwani, The least prime congruent to one modulo n, Amer. Math. Monthly 118(8) (2011), 737-742.

Cf. A034693, A034780, A034782, A034783, A034784, A034785, A034846, A034847, A034848, A034849, A038700, A085420.

Records: A120856, A120857.

a034694 n = until ((== 1) . a010051) (+ n) (n + 1)
-- Reinhard Zumkeller, Dec 17 2013

a[n_] := Block[{k = 1}, If[n == 1, 2, While[Mod[Prime@k, n] != 1, k++ ]; Prime@k]]; Array[a, 64] (* Robert G. Wilson v, Jul 08 2006 *)
With[{prs=Prime[Range[200]]},Flatten[Table[Select[prs,Mod[#-1,n]==0&,1],{n,70}]]] (* Harvey P. Dale, Sep 22 2021 *)

a(n)=if(n<0,0,s=1; while((prime(s)-1)%n>0,s++); prime(s))

a(n) = min{m: m = k*n + 1 with k > 0 and A010051(m) = 1}. - Reinhard Zumkeller, Dec 17 2013

a(n) = n * A034693(n) + 1. - Joerg Arndt, Oct 18 2020

A034693 Smallest k such that k*n+1 is prime.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 10, 2, 2, 1, 2, 3, 4, 2, 4, 1, 2, 1, 10, 3, 2, 3, 2, 1, 4, 5, 2, 1, 2, 1, 4, 2, 4, 1, 6, 2, 4, 2, 2, 1, 2, 2, 6, 2, 4, 1, 12, 1, 6, 5, 2, 3, 2, 1, 4, 2, 2, 1, 8, 1, 4, 2, 2, 3, 6, 1, 4, 3, 2, 1, 2, 4, 12, 2, 4, 1, 2, 2, 6, 3, 4, 3, 2, 1, 4, 2

Offset: 1

Labos Elemer

Conjecture: for every n > 1 there exists a number k < n such that n*k + 1 is a prime. - Amarnath Murthy, Apr 17 2001
A stronger conjecture: for every n there exists a number k < 1 + n^(.75) such that n*k + 1 is a prime. I have verified this up to n = 10^6. Also, the expression 1 + n^(.74) does not work as an upper bound (counterexample: n = 19). - Joseph L. Pe, Jul 16 2002
Stronger version of the conjecture verified up to 10^9. - Mauro Fiorentini, Jul 23 2023
It is known that, for almost all n, a(n) <= n^2. From Heath-Brown's result (1992) obtained with help of the GRH, it follows that a(n) <= (phi(n)*log(n))^2. - Vladimir Shevelev, Apr 30 2012
Conjecture: a(n) = O(log(n)*log(log(n))). - Thomas Ordowski, Oct 17 2014
I conjecture the opposite: a(n) / (log n log log n) is unbounded. See A194945 for records in this sequence. - Charles R Greathouse IV, Mar 21 2016

			If n=7, the smallest prime in the sequence 8, 15, 22, 29, ... is 29, so a(7)=4.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.
P. Ribenboim, (1989), The Book of Prime Number Records. Chapter 4, Section IV.B.: The Smallest Prime In Arithmetic Progressions, pp. 217-223.

T. D. Noe, Table of n, a(n) for n = 1..10000
Gunther Cornelissen, David Hokken, and Berend Ringeling, The asymptotic Mahler measure of Gaussian periods, arXiv:2507.09303 [math.NT], 2025. See p. 1.
Steven R. Finch, Linnik's Constant
D. Graham, On Linnik's Constant, Acta Arithm., 39, 1981, pp. 163-179.
D. R. Heath-Brown, Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. 64(3) (1992), pp. 265-338.
Pengcheng Niu and Junli Zhang, On Two Conjectures of A. Murthy, ResearchGate (2024).
Ivan Niven and Barry Powell, Primes in Certain Arithmetic Progressions, Amer. Math. Monthly, 83, 1976, pp. 467-489.
Wikipedia, Dirichlet's theorem on arithmetic progressions

Cf. A010051, A034694, A053989, A071558, A085420, A103689, A194944 (records), A194945 (positions of records), A200996.

a034693 n = head [k | k <- [1..], a010051 (k * n + 1) == 1]
-- Reinhard Zumkeller, Feb 14 2013

A034693 := proc(n)
    for k from 1 do
        if isprime(k*n+1) then
            return k;
        end if;
    end do:
end proc: # R. J. Mathar, Jul 26 2015

a[n_]:=(k=0; While[!PrimeQ[++k*n + 1]]; k); Table[a[n], {n,100}] (* Jean-François Alcover, Jul 19 2011 *)

a(n)=if(n<0,0,s=1; while(isprime(s*n+1)==0,s++); s)

from sympy import isprime
def a(n):
    k = 1
    while not isprime(k*n+1): k += 1
    return k
print([a(n) for n in range(1, 99)]) # Michael S. Branicky, May 05 2022

It seems that Sum_{k=1..n} a(k) is asymptotic to (zeta(2)-1)*n*log(n) where zeta(2)-1 = Pi^2/6-1 = 0.6449... . - Benoit Cloitre, Aug 11 2002

a(n) = (A034694(n)-1) / n. - Joerg Arndt, Oct 18 2020

A038026 Last position reached by winner of n-th Littlewood Frog Race.

Original entry on oeis.org

2, 3, 7, 5, 19, 7, 29, 17, 19, 19, 43, 13, 103, 29, 31, 41, 103, 19, 191, 41, 67, 43, 137, 73, 149, 103, 109, 83, 317, 31, 311, 97, 181, 103, 191, 71, 439, 191, 233, 89, 379, 67, 463, 113, 181, 137, 967, 97, 613, 149, 197, 181, 607, 109, 331, 233

Offset: 1

Christian G. Bower

nonn

Related to Linnik's theorem; main sequence is A085420. - Charles R Greathouse IV, Apr 16 2010

a(n) is the smallest prime such that some subset of primes <= a(n) is a reduced residue system modulo n. - Vladimir Shevelev, Feb 19 2013

			a(6) = 7 since the primes less than or equal to 7, {2, 3, 5, 7}, reduced modulo 6 are {2, 3, 5, 1}.  This contains the reduced residue system modulo 6, which is {1, 5}, and 7 is clearly the smallest such prime. - _Vladimir Shevelev_, Feb 19 2013

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

This sequence is a lower bound for the related sequence A085420.

Cf. A038025.

a(n)={
my(todo=(1<1,todo=bitnegimply(todo,1<Charles R Greathouse IV, Feb 14 2011

p(n,b)=while(!isprime(b), b+= n); b
a(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

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. - Charles R Greathouse IV, Sep 08 2012

A194943 Greatest d such that dn+b is the least prime in the arithmetic progression kn+b for some 0 < b < n with gcd(b, n) = 1.

Original entry on oeis.org

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

Charles R Greathouse IV, Sep 05 2011

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.

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.

Cf. A085420. Records are in A362850, A362851.

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 *)

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

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

a(n) = floor(A085420(n)/n).

A358240 Consider all invertible residues mod n. For each residue, find the smallest product of three primes (A014612) which is in that residue class mod n. a(n) is the greatest of these.

Original entry on oeis.org

8, 27, 28, 45, 66, 175, 45, 105, 76, 171, 102, 325, 165, 261, 124, 273, 230, 385, 188, 369, 268, 255, 175, 475, 284, 549, 436, 477, 285, 1309, 332, 385, 430, 927, 318, 1127, 442, 639, 610, 657, 595, 1075, 742, 805, 724, 637, 646, 1705, 642, 741, 670, 1005, 885, 1435, 801, 1705, 1105, 873, 1004, 2821, 938, 873, 844

Offset: 1

Charles R Greathouse IV, Jan 18 2023

nonn

			The least product of 3 primes = 1 mod 3 is 28, while the least = 2 mod 3 is 8, so a(2) = 28.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Ramachandran Balasubramanian, Olivier Ramaré, and Priyamvad Srivastav, Product of three primes in large arithmetic progressions, arXiv:2208.04031 [math.NT], 2022.

All terms are in A014612.

Cf. A038026, A085420.

firstTri(m)=my(mod=m.mod); forprime(p=2,, if(mod%p==0, next); forprime(q=2,p, if(mod%q==0, next); forprimestep(r=2,q,m/p/q, return(p*q*r))))
a(n)=my(r=8); for(k=1,n-1, if(gcd(k,n)>1, next); r=max(firstTri(Mod(k,n)),r)); r

A result of Balasubramanian, Ramaré, & Srivastav proves that a(n) < n^e for each e > 9/2 and large enough n depending on e.

Corrected by Charles R Greathouse IV, May 10 2023

A196660 Smallest k>0 such that k*n+(n-1) is prime.

Original entry on oeis.org

2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 3, 1, 7, 2, 1, 1, 3, 2, 1, 2, 1, 1, 5, 1, 5, 3, 1, 2, 5, 1, 1, 3, 3, 1, 3, 1, 1, 2, 5, 1, 3, 1, 5, 2, 1, 2, 5, 3, 1, 2, 1, 1, 3, 1, 1, 2, 1, 2, 5, 2, 7, 6, 3, 1, 5, 1, 5, 3, 1, 1, 3, 4, 13, 5, 1, 1, 3, 2, 1, 2, 7, 1, 3, 1, 5, 2, 1, 2, 15

Offset: 1

Frank M Jackson, Oct 05 2011

nonn

Conjecture: for every n there exists k < n (apart from a(1)) such that k*n+(n-1) is prime. See A034693.

			If n=13, the smallest prime in the sequence 25,38,51,64,77,90,103,... is 103, so a(13)=7.

Eric Weisstein's World of Mathematics, Linnik's Theorem
Wikipedia, Linnik's theorem.

Cf. A034693, A085420.

q[n_]:=(k=0; While[!PrimeQ[++k*n+n-1]]; k); Table[q[n],{n,1,100}]

a(n) = my(k=1); while (!isprime(k*n+(n-1)), k++); k; \\ Michel Marcus, Mar 18 2025

A358242 Consider all invertible residues k mod n. For each such k, find the product of three primes pqr = k (mod n) with the smallest max {p, q, r}. Then a(n) is the largest such p over the considered k.

Original entry on oeis.org

2, 3, 7, 5, 11, 7, 5, 7, 7, 11, 7, 11, 11, 11, 13, 11, 13, 11, 11, 13, 17, 13, 13, 13, 19, 17, 17, 17, 13, 17, 17, 17, 19, 19, 29, 17, 17, 13, 23, 19, 23, 19, 23, 17, 29, 17, 23, 23, 23, 19, 23, 19, 23, 17, 31, 23, 29, 19, 29, 29, 29, 19, 23

Offset: 1

Charles R Greathouse IV, Jan 18 2023

nonn

This is an analog of Linnik's theorem for 3-almost primes. - Charles R Greathouse IV, Jun 30 2024

			From _M. F. Hasler_, Jul 02 2024: (Start)
For n = 1, there is only one residue class in Z/nZ = {Z}, and it is invertible (since 0 = 1 in this case), and p = q = r = 2 satisfies p*q*r = k (mod n) and gives clearly the smallest possible prime to satisfy the conditions, so a(1) = 2.
For n = 2, there is only one invertible residue class in Z/nZ, namely that of k = 1, and none of p, q, r may equal 2 (= 0 in Z/2Z) to yield p*q*r = 1 (mod n), so p = q = r = 3 is the smallest solution to p*q*r = 1 (mod n), whence a(2) = 3.
For n = 3, the two invertible residues (mod n) are k = 1 and k = 2. For p = q = r = 2, we have p*q*r = 8 = 2 (mod 3), but for the residue k = 1, we need a different solution, which therefore can't have as largest prime p = 2 (=> k = 2) nor p = 3 = 0 (mod 3) nor p = 5 = 2 (mod 3), but p = 7 >= q = r = 2 does work, with 4*7 = 28 = 1 (mod 3), so a(3) = 7. (End)

Charles R Greathouse IV, Table of n, a(n) for n = 1..100000
Ramachandran Balasubramanian, Olivier Ramaré, and Priyamvad Srivastav, Product of three primes in large arithmetic progressions, International Journal of Number Theory, Vol. 19, No. 4 (2023), pp. 843-857; arXiv preprint, arXiv:2208.04031 [math.NT], 2022.
Barnabás Szabó, On the existence of products of primes in arithmetic progressions, Bulletin of the London Mathematical Society 56 (3), pp. 1227-1243, 2024.

Cf. A358240, A038026, A085420, A014612.

do(m)=my(mod=m.mod); forprime(p=2,, if(mod%p==0, next); forprime(q=2,p, if(mod%q==0, next); forprimestep(r=2,q,m/p/q, return(p))))
a(n)=my(r=2); for(k=1,n-1, if(gcd(k,n)>1, next); r=max(do(Mod(k,n)),r)); r

a(n)=my(N,s=eulerphi(n)); forprime(p=2,, if(n%p==0, next); forprime(q=2,p, if(n%q==0, next); my(pq=p*q%n); forprime(r=2,q, if(n%r==0, next); my(pqr=pq*r%n); if(bittest(N,pqr)==0, N+=1<Charles R Greathouse IV, Jun 30 2024

Balasubramanian, Ramaré, & Srivastav prove that a(n) < n^e for each e > 3/2 and large enough n depending on e.

Szabó improves this to e > 6/5. - Charles R Greathouse IV, Jun 30 2024

Definition clarified by Charles R Greathouse IV and M. F. Hasler, Jul 02 2024

cp's OEIS Frontend

A034694 Smallest prime == 1 (mod n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A034693 Smallest k such that k*n+1 is prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A038026 Last position reached by winner of n-th Littlewood Frog Race.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A358240 Consider all invertible residues mod n. For each residue, find the smallest product of three primes (A014612) which is in that residue class mod n. a(n) is the greatest of these.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A196660 Smallest k>0 such that k*n+(n-1) is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A358242 Consider all invertible residues k mod n. For each such k, find the product of three primes p*q*r = k (mod n) with the smallest max {p, q, r}. Then a(n) is the largest such p over the considered k.

Views

Author

A194943 Greatest d such that dn+b is the least prime in the arithmetic progression kn+b for some 0 < b < n with gcd(b, n) = 1.

A358242 Consider all invertible residues k mod n. For each such k, find the product of three primes pqr = k (mod n) with the smallest max {p, q, r}. Then a(n) is the largest such p over the considered k.