A053989 -id:A053989 - cp's OEIS frontend

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

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

A103689 a(n) is the least k such that either kn - 1 or kn + 1 (or both) is prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1, 4, 2, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 6, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 6, 1, 6, 1, 2, 2, 2, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 2, 4, 1, 2, 1, 2, 1, 2, 1, 6, 2, 2, 1, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 2, 1, 6, 1, 6, 1, 2

Offset: 1

Pierre CAMI, Feb 12 2005

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A002110, A034693, A053989, A103688, A200996, A348347.

a103689 n = min (a053989 n) (a034693 n)
-- Reinhard Zumkeller, Feb 14 2013

f[n_] := Block[{k = 1}, While[ ! PrimeQ[k*n - 1] && ! PrimeQ[k*n + 1], k++ ]; k]; Table[ f[n], {n, 105}] (* Robert G. Wilson v, Feb 12 2005 *)
lk[n_]:=Module[{k=1},While[NoneTrue[k*n+{1,-1},PrimeQ],k++];k]; Array[ lk,120] (* The program uses the NoneTrue function from Mathematica version 10 *) (* Harvey P. Dale, May 01 2016 *)

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

a(n) <= A200996(n). - Reinhard Zumkeller, Feb 14 2013
a(n) = min {A053989(n), A034693(n)}. - Reinhard Zumkeller, Feb 14 2013
a(A002110(n)/3+3) >= ceiling((prime(n+1)-1)/3) for n >= 2. Equality holds for n = 2, 4, 6, 8, 10, 12, 22, 25, 31, 116, 155, 156, 197, ... . - Pontus von Brömssen, Oct 16 2021
a(A002110(n)/3-3) >= ceiling((prime(n+1)-1)/3) for n >= 3. Equality holds for n = 3, 4, 5, 6, 7, 9, 39, 51, 59, 65, 98, 311, ... . - Pontus von Brömssen, Oct 19 2021

Edited, corrected and extended by Robert G. Wilson v, Feb 19 2005

A231819 Least positive k such that k*n^2 - 1 is a prime, or 0 if no such k exists.

Original entry on oeis.org

3, 1, 2, 2, 6, 2, 2, 2, 8, 2, 2, 3, 2, 3, 2, 5, 2, 2, 8, 5, 2, 2, 8, 2, 2, 3, 6, 2, 12, 3, 8, 5, 10, 2, 6, 2, 12, 2, 2, 3, 2, 2, 2, 3, 2, 2, 18, 3, 2, 2, 8, 2, 20, 3, 6, 2, 18, 3, 2, 3, 12, 2, 2, 2, 6, 7, 8, 6, 2, 3, 14, 3, 2, 3, 6, 2, 6, 3, 8, 2, 2, 5, 6, 5, 2

Offset: 1

Alex Ratushnyak, Nov 13 2013

nonn

Cf. A035092 (least k such that k*(n^2)+1 is a prime).
Cf. A175763 (least k such that k*(n^n)+1 is a prime).
Cf. A035093 (least k such that k*n!+1    is a prime).
Cf. A193807 (least k such that n*(k^2)+1 is a prime).
Cf. A231119 (least k such that n*(k^k)+1 is a prime).
Cf. A057217 (least k such that n*k!+1    is a prime).
Cf. A034693 (least k such that n*k +1    is a prime).
Cf. A231818 (least k such that k*(n^n)-1 is a prime).
Cf. A083663 (least k such that k*n!-1    is a prime).
Cf. A231734 (least k such that n*(k^2)-1 is a prime).
Cf. A231735 (least k such that n*(k^k)-1 is a prime).
Cf. A231820 (least k such that n*k!-1    is a prime).
Cf. A053989 (least k such that n*k -1    is a prime).

Table[k = 1; While[! PrimeQ[k*n^2 - 1], k++]; k, {n, 100}] (* T. D. Noe, Nov 18 2013 *)

A083663 Least k such that k*n!-1 is prime.

Original entry on oeis.org

3, 2, 1, 1, 2, 1, 1, 5, 3, 4, 4, 1, 5, 1, 2, 9, 2, 30, 30, 5, 44, 2, 7, 13, 5, 3, 11, 2, 14, 1, 7, 1, 1, 30, 16, 22, 36, 1, 38, 13, 22, 6, 36, 17, 36, 40, 31, 25, 38, 13, 4, 32, 22, 154, 10, 27, 7, 121, 9, 33, 19, 19, 4, 26, 100, 18, 46, 75, 21, 11, 34, 75, 38, 7, 45, 3, 19, 13, 59, 39, 72

Offset: 1

Benoit Cloitre, Jun 14 2003

nonn

Robert Israel, Table of n, a(n) for n = 1..600

Cf. A035093, A053989, A084730.

f:= proc(n) local w,k;
w:= n!;
for k from 1 do
  if isprime(k*w-1) then return k fi
od
end proc:
map(f, [$1..100]); # Robert Israel, Nov 23 2023

lkp[n_]:=Module[{k=1,nf=n!},While[!PrimeQ[k*nf-1],k++];k]; Array[lkp,100] (* Harvey P. Dale, Apr 26 2025 *)

a(n)=if(n<1,0,k=1; while(isprime(k*n!-1)==0,k++); k)

a(n) = A053989(n!) = (A084730(n)+1)/n!. - Robert Israel, Nov 23 2023

A200996 Least upper limit for numbers u and v such that un-1 and vn+1 are both prime, u and v not necessarily distinct.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Feb 14 2013

nonn

A103689(n) <= a(n) <= A071558(n).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Haskell
```
a200996 n = max (a053989 n) (a034693 n)
```

a(n) = max {A053989(n), A034693(n)}.

A224609 Smallest j such that 2jprime(n)^3-1 is prime.

Original entry on oeis.org

2, 1, 2, 7, 2, 7, 8, 6, 8, 5, 1, 3, 11, 1, 9, 3, 5, 1, 3, 15, 7, 3, 8, 8, 12, 2, 15, 3, 10, 2, 3, 12, 12, 1, 6, 6, 9, 3, 5, 2, 5, 1, 5, 10, 57, 1, 21, 1, 15, 9, 2, 3, 1, 5, 5, 3, 15, 6, 7, 5, 25, 6, 12, 11, 6, 5, 1, 9, 2, 19, 5, 9, 27, 1, 3, 11, 3, 15, 2, 6, 21

Offset: 1

Pierre CAMI, Apr 12 2013

nonn

We are searching smallest j such that j*prime(n)*2*p(n)^2-1 is prime, for A224489 it is smallest k such that k*2*prime(n)^2-1 is prime, so here we replace smallest k by smallest j*prime(n).

			1*2*2^3-1= 15 is composite; 2*2*2^3-1= 31 is prime, so a(1)=2 as p(1)=2.
1*2*3^3-1=53 is prime, so a(2)=1 as p(2)=3.
1*2*5^3-1=249 is composite; 2*2*5^3=499 is prime, so a(3)=2 as p(3)=5.

Pierre CAMI, Table of n, a(n) for n = 1..10000

Cf. A224489.

S:=[];
j:=1;
for n in [1..100] do
  while not IsPrime(2*j*NthPrime(n)^3-1) do
       j:=j+1;
  end while;
  Append(~S, j);
  j:=1;
end for;
S; // Bruno Berselli, Apr 18 2013

jmax = 10^5 (* sufficient up to 10^5 terms *); a[n_] := For[j = 1, j <= jmax, j++, p = Prime[n]; If[PrimeQ[j*2*p^3 - 1], Return[j]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Apr 18 2013 *)

a(n)=my(P=2*prime(n)^3,j);while(!isprime(j++*P-1),);j \\ Charles R Greathouse IV, Apr 18 2013

a(n) = A053989(2p^3) where p is the n-th prime. - Charles R Greathouse IV, Apr 18 2013

A216568 Smallest k such that prime(n)*k-1 is prime.

Original entry on oeis.org

2, 1, 4, 2, 4, 8, 4, 2, 6, 6, 2, 2, 4, 6, 6, 4, 6, 8, 6, 4, 14, 2, 4, 16, 2, 10, 6, 6, 6, 6, 6, 4, 4, 2, 10, 12, 2, 6, 10, 4, 10, 8, 22, 8, 4, 2, 2, 8, 4, 2, 16, 6, 14, 12, 12, 4, 6, 2, 12, 4, 6, 4, 2, 10, 6, 6, 2, 2, 6, 8, 10, 6, 2, 6, 2, 4, 6, 6, 22

Offset: 1

Alex Ratushnyak, Sep 19 2012

nonn

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A035096, A034693, A053989.

Table[k = 1; While[! PrimeQ[Prime[n]*k - 1], k++]; k, {n, 100}] (* T. D. Noe, Sep 19 2012 *)

A231820 Least positive k such that n*k! - 1 is a prime, or 0 if no such k exists.

Original entry on oeis.org

3, 2, 1, 1, 3, 1, 2, 1, 2, 2, 4, 1, 4, 1, 2, 2, 3, 1, 2, 1, 2, 2, 3, 1, 3, 5, 2, 3, 3, 1, 2, 1, 3, 2, 4, 2, 2, 1, 3, 2, 4, 1, 3, 1, 2, 4, 3, 1, 2, 6, 2, 2, 3, 1, 2, 5, 2, 3, 3, 1, 10, 1, 4, 2, 3, 2, 3, 1, 2, 2, 7, 1, 8, 1, 2, 2, 3, 3, 2, 1, 5, 2, 8, 1, 3, 4, 2, 4, 15, 1

Offset: 1

Alex Ratushnyak, Nov 13 2013

nonn

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A035092 (least k such that k*(n^2)+1 is a prime).
Cf. A175763 (least k such that k*(n^n)+1 is a prime).
Cf. A035093 (least k such that k*n!+1    is a prime).
Cf. A193807 (least k such that n*(k^2)+1 is a prime).
Cf. A231119 (least k such that n*(k^k)+1 is a prime).
Cf. A057217 (least k such that n*k!+1    is a prime).
Cf. A034693 (least k such that n*k +1    is a prime).
Cf. A231819 (least k such that k*(n^2)-1 is a prime).
Cf. A231818 (least k such that k*(n^n)-1 is a prime).
Cf. A083663 (least k such that k*n!-1    is a prime).
Cf. A231734 (least k such that n*(k^2)-1 is a prime).
Cf. A231735 (least k such that n*(k^k)-1 is a prime).
Cf. A053989 (least k such that n*k -1    is a prime).

f:= proc(n) local k;
for k from 1 do if isprime(n*k!-1) then return k fi od
end proc:
map(f, [$1..100]); # Robert Israel, Oct 29 2019

Table[k = 1; While[! PrimeQ[k!*n - 1], k++]; k, {n, 100}] (* T. D. Noe, Nov 18 2013 *)

a(n) = my(k=1); while (!isprime(n*k! - 1), k++); k; \\ Michel Marcus, Oct 29 2019

A261437 Least positive integer k such that kn+1 = prime(p) and k^2n+1 = prime(q) for some pair of primes p and q.

Original entry on oeis.org

2, 1, 286, 1, 7290, 21, 18, 2472, 12, 1, 20460, 20, 20692, 105, 4392, 1, 96816, 1327, 360, 264, 19850, 2734, 1854, 5293, 930, 29526, 98, 622, 9222, 1, 6816, 924, 61614, 70, 53760, 45, 32190, 9687, 5510, 1, 128070, 148, 8772, 23478, 404, 801, 1830, 5, 9912, 7662, 1100, 8211, 1116, 9997, 630, 4965, 936, 1, 87570, 759

Offset: 1

Zhi-Wei Sun, Aug 18 2015

nonn

Conjecture: (i) If n > 0 and r are relatively prime integers, then there are infinitely many positive integers k such that k*n+r = prime(p) for some prime p.
(ii) Let r be 1 or -1. For any integer n > 0, there is a positive integer k such that k*n+r = prime(p) and k^2*n+1 = prime(q) for some primes p and q.
(iii) For any integer n > 0, there is a positive integer k such that n+k = prime(p) and n+k^2 = prime(q) for some primes p and q.
Note that part (i) is a refinement of Dirichlet's theorem on primes in arithmetic progressions. Also, part (ii) implies that a(n) exists for any n > 0.

			a(3) = 286 since 286*3+1 = 859 = prime(149) with 149 prime, and 286^2*3+1 = 245389 = prime(21661) with 21661 prime.

Zhi-Wei Sun, Problems on combinatorial properties of primes, in: M. Kaneko, S. Kanemitsu and J. Liu (eds.), Number Theory: Plowing and Starring through High Wave Forms, Proc. 7th China-Japan Seminar (Fukuoka, Oct. 28 - Nov. 1, 2013), Ser. Number Theory Appl., Vol. 11, World Sci., Singapore, 2015, pp. 169-187.

Zhi-Wei Sun, Table of n, a(n) for n = 1..200
Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641 [math.NT], 2014.

Cf. A000040, A000290, A034693, A053989, A185636, A204065.

PQ[p_]:=PrimeQ[p]&&PrimeQ[PrimePi[p]]
Do[k=0;Label[bb];k=k+1;If[PQ[k*n+1]&&PQ[k^2*n+1],Goto[aa],Goto[bb]];Label[aa];Print[n," ", k];Continue,{n,1,60}]

A266909 Table read by rows: for each k < n and coprime to n, the least x>=0 such that x*n+k is prime.

Original entry on oeis.org

1, 2, 0, 1, 0, 2, 0, 0, 3, 1, 0, 4, 0, 0, 1, 0, 1, 2, 0, 0, 0, 2, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 0, 0, 3, 0, 1, 0, 1, 2, 3, 1, 0, 0, 0, 4, 0, 0, 1, 0, 1, 0, 3, 4, 1, 0, 7, 2, 0, 0, 1, 0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 0, 0, 1, 6, 0, 0, 5, 0, 1, 0, 3, 2, 3, 0, 1, 0, 1, 4, 3, 1, 0, 0, 0, 0, 0, 10, 0

Offset: 1

Robert Israel, Jan 05 2016

By Dirichlet's theorem, such x exists whenever k is coprime to n.
By Linnik's theorem, there exist constants b and c such that T(n,k) <= b n^c for all n and all k < n coprime to n.
T(n,1) = A034693(n).
T(n,n-1) = A053989(n)-1.
T(prime(n),1) = A035096(n).
T(2^n,1) = A035050(n).
A085427(n) = T(2^n,2^n-1) + 1.
A126717(n) = 2*T(2^(n+1),2^n-1) + 1.
A257378(n) = 2*T(n*2^(n+1),n*2^n+1) + 1.
A257379(n) = 2*T(n*2^(n+1),n*2^n-1) + 1.

			The first few rows are
n=2: 1
n=3: 2, 0
n=4: 1, 0
n=5: 2, 0, 0, 3
n=6: 1, 0

Robert Israel, Table of n, a(n) for n = 1..10975 (rows 2 to 190, flattened)
Wikipedia, Dirichlet's theorem on arithmetic progressions.
Wikipedia, Linnik's theorem
Index entries for sequences related to primes in arithmetic progressions

Cf. A034693, A035050, A035096, A053989, A085427, A126717, A257378, A257379.

T:= proc(n,k) local x;
    if igcd(n,k) <> 1 then return NULL fi;
    for x from 0 do if isprime(x*n+k) then return x fi
    od
end proc:
seq(seq(T(n,k),k=1..n-1),n=2..30);

Table[Map[Catch@ Do[x = 0; While[! PrimeQ[x n + #], x++]; Throw@ x, {10^3}] &, Range@ n /. k_ /; GCD[k, n] > 1 -> Nothing], {n, 2, 19}] // Flatten (* Michael De Vlieger, Jan 06 2016 *)

cp's OEIS Frontend

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

A103689 a(n) is the least k such that either k*n - 1 or k*n + 1 (or both) is prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A231819 Least positive k such that k*n^2 - 1 is a prime, or 0 if no such k exists.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A083663 Least k such that k*n!-1 is prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A200996 Least upper limit for numbers u and v such that u*n-1 and v*n+1 are both prime, u and v not necessarily distinct.

Views

Author

Keywords

Comments

Links

Programs

Haskell

Formula

A224609 Smallest j such that 2*j*prime(n)^3-1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A216568 Smallest k such that prime(n)*k-1 is prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A231820 Least positive k such that n*k! - 1 is a prime, or 0 if no such k exists.

Views

Author

A103689 a(n) is the least k such that either kn - 1 or kn + 1 (or both) is prime.

A200996 Least upper limit for numbers u and v such that un-1 and vn+1 are both prime, u and v not necessarily distinct.

A224609 Smallest j such that 2jprime(n)^3-1 is prime.

A261437 Least positive integer k such that kn+1 = prime(p) and k^2n+1 = prime(q) for some pair of primes p and q.