A071558 -id:A071558 - 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

A053989 Smallest k such that nk-1 is prime.

Original entry on oeis.org

3, 2, 1, 1, 4, 1, 2, 1, 2, 2, 4, 1, 8, 1, 2, 2, 4, 1, 2, 1, 2, 2, 6, 1, 6, 4, 2, 3, 6, 1, 2, 1, 4, 2, 4, 2, 2, 1, 6, 2, 4, 1, 6, 1, 2, 3, 6, 1, 2, 3, 2, 2, 4, 1, 2, 3, 2, 3, 6, 1, 8, 1, 4, 2, 6, 2, 6, 1, 2, 2, 4, 1, 14, 1, 2, 2, 4, 3, 2, 1, 8, 2, 4, 1, 6, 3, 2, 3, 16, 1, 2, 4, 6, 3, 4, 2, 2, 1, 2, 2

Offset: 1

Henry Bottomley, Apr 04 2000

			a(5)=4 because the smallest prime in the sequence 5k-1 (4,9,14,19,24...) is 19 when k=4

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

Cf. A034693, A038700, A071558, A010051, A103689, A200996.

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

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

a(n) = (A038700(n)+1)/n.

A071407 Least k such that kprime(n) + 1 and kprime(n) - 1 are twin primes.

Original entry on oeis.org

2, 2, 6, 6, 18, 24, 6, 12, 6, 12, 42, 54, 30, 24, 6, 120, 18, 258, 24, 18, 84, 132, 54, 48, 114, 42, 6, 6, 48, 24, 144, 30, 6, 12, 12, 78, 24, 36, 30, 54, 132, 18, 90, 36, 66, 18, 42, 30, 120, 30, 36, 42, 18, 18, 54, 84, 60, 12, 210, 12, 6, 60, 150, 102, 6, 210, 30, 24, 6

Offset: 1

Labos Elemer, May 24 2002

Note that 6 divides a(n) for n > 2. - T. D. Noe, Jan 07 2013

			n=4: prime(4)=7, a(4)=6 because 6*prime(4)=42 and {41,43} are primes.

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

Cf. A071256, A071404-A071406, A060256, A060210, A090530, A294731.
Cf. A071558 (k at every integer).
Cf. A220141, A220142 (record values).

a071407 n = head [k | k <- [2,4..], let x = k * a000040 n,
                      a010051' (x - 1) == 1, a010051' (x + 1) == 1]
-- Reinhard Zumkeller, Feb 14 2013

Table[fl=1; Do[s=(Prime[j])*k; If[PrimeQ[s-1]&&PrimeQ[s+1]&&Equal[fl, 1], Print[{j, k}]; fl=0], {k, 1, 2*j^2}], {j, 0, 100}]

From Amiram Eldar, Aug 25 2025: (Start)
a(n) = A090530(n) / prime(n).
a(n) = 6 * A294731(n) for n >= 3. (End)

A071256 Smallest multiple of n sandwiched between twin primes.

Original entry on oeis.org

4, 4, 6, 4, 30, 6, 42, 72, 18, 30, 198, 12, 312, 42, 30, 192, 102, 18, 228, 60, 42, 198, 138, 72, 150, 312, 108, 420, 348, 30, 1302, 192, 198, 102, 420, 72, 1998, 228, 312, 240, 1230, 42, 1032, 660, 180, 138, 282, 192, 882, 150, 102, 312, 6360, 108, 660

Offset: 1

Amarnath Murthy, May 22 2002

Conjecture: lim sup n ->infinity a(n)/n^2 exists = C, where 0Benoit Cloitre, May 23 2002

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

Cf. A071558.

Table[ s = 2; While[ Mod[s, n] + 2 - Boole[ PrimeQ[s - 1]] - Boole[ PrimeQ[s + 1]] > 0, s++]; s, {n, 1, 55}] (* Jean-François Alcover, Dec 08 2011, after Pari *)
With[{tpm=Mean/@Select[Partition[Prime[Range[1000]],2,1],#[[2]]-#[[1]] == 2&]},Flatten[Table[Select[tpm,Divisible[#,n]&,1],{n,60}]]] (* Harvey P. Dale, Apr 12 2012 *)

a(n) = my(s=2); while(s%n+2-isprime(s-1)-isprime(s+1)>0, s++); s;

a(n) = n*A071558(n). - Michel Marcus, Aug 29 2025

More terms from Benoit Cloitre, May 23 2002

A204065 Least nonnegative integer k with n+k and n+k^2 both prime.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 3, 16, 1, 0, 7, 4, 15, 2, 1, 0, 1, 0, 9, 8, 3, 6, 1, 0, 3, 2, 1, 0, 1, 0, 3, 8, 1, 0, 5, 10, 3, 10, 1, 0, 5, 4, 15, 2, 1, 0, 1, 0, 21, 4, 3, 6, 1, 0, 15, 2, 1, 0, 1, 0, 33, 8, 25, 6, 1, 0, 3, 16, 1, 0, 5, 4, 15, 14, 1, 0, 7, 6, 9, 4, 3, 6, 1, 0, 3, 2, 1

Offset: 1

Zhi-Wei Sun, Jan 09 2013

nonn

Conjecture: For any n > 0 not among 1, 21, 326, 341, 626, we have a(n) < sqrt(n)*log(n). If n > 626 is not equal to 971, then n+k and n+k^2 are both prime for some 0< k < sqrt(n)*log(n). Also, n+k^2 is prime for some 0< k <= sqrt(n) if n > 43181.

Obviously, a(n)=0 iff n is a prime. - M. F. Hasler, Jan 11 2013

			a(8)=3 since 8+3 and 8+3^2 are both prime, but none of 8, 8+1, 8+2 is prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Conjectures involving primes and quadratic forms, arXiv:1211.1588.

Cf. A185636, A071558.

Do[Do[If[PrimeQ[n+k]==True&&PrimeQ[n+k^2]==True,Print[n," ",k];Goto[aa]],{k,0,n}];
Label[aa];Continue,{n,1,100}]

a(n)=my(k=0); while(!isprime(n+k) || !isprime(n+k^2), k++); k \\ - M. F. Hasler, Jan 11 2013

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)}.

A210445 Least positive integer k with k*n practical.

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 4, 1, 2, 2, 6, 1, 6, 2, 2, 1, 12, 1, 12, 1, 2, 3, 12, 1, 4, 3, 2, 1, 12, 1, 16, 1, 2, 6, 4, 1, 18, 6, 2, 1, 20, 1, 20, 2, 2, 6, 24, 1, 4, 2, 4, 2, 24, 1, 4, 1, 4, 6, 24, 1, 24, 8, 2, 1, 4, 1, 30, 3, 4, 2, 30, 1, 30, 9, 2, 3, 4, 1, 36, 1, 2, 10, 36, 1, 4, 10, 4, 1, 36, 1, 4, 3, 6, 12, 4, 1, 42, 2, 2, 1

Offset: 1

Zhi-Wei Sun, Jan 20 2013

Conjecture: a(n) < n for all n>1, and a(n) < n/2 for all n>47.

Large values are obtained for prime n: The corresponding subsequence is a(p(n)) = (1, 2, 4, 4, 6, 6, 12, 12, 12, 12, 16, 18, 20, 20, 24, 24, 24, 24, ...), while for composite indices, a(c(n)) = (1, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 3, 1, 4, 3, 2, 1, 1, 1, 2, ...). - M. F. Hasler, Jan 21 2013

			a(10)=2 since 2*10=20 is practical but 1*10=10 is not.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
G. Melfi, On two conjectures about practical numbers, J. Number Theory 56 (1996) 205-210 [MR96i:11106].
Zhi-Wei Sun, Conjectures involving primes and quadratic forms, arXiv:1211.1588 [math.NT], 2012-2015.

Cf. A005153, A210444, A071558, A208243, A208244, A208246, A208249, A209253, A209254, A209312, A219185, A219312, A219315, A219320.

f[n_]:=f[n]=FactorInteger[n]
Pow[n_, i_]:=Pow[n, i]=Part[Part[f[n], i], 1]^(Part[Part[f[n], i], 2])
Con[n_]:=Con[n]=Sum[If[Part[Part[f[n], s+1], 1]<=DivisorSigma[1, Product[Pow[n, i], {i, 1, s}]]+1, 0, 1], {s, 1, Length[f[n]]-1}]
pr[n_]:=pr[n]=n>0&&(n<3||Mod[n, 2]+Con[n]==0)
Do[Do[If[pr[k*n]==True,Print[n," ",k];Goto[aa]],{k,1,n}];
Print[n," ",counterexample];Label[aa];Continue,{n,1,100}]

A210445(n)={for(k=1,n,is_A005153(k*n)&&return(k))} \\ (Would return 0 if a(n)>n.) - M. F. Hasler, Jan 20 2013

a(n) = 1 iff n is in A005153, therefore a(n) > 1 for all odd n>1. - M. F. Hasler, Jan 21 2013

A210444 a(n) = |{0

Original entry on oeis.org

0, 0, 1, 2, 0, 4, 1, 0, 2, 2, 0, 4, 0, 1, 4, 2, 0, 6, 1, 3, 2, 2, 0, 5, 2, 1, 3, 1, 2, 11, 0, 1, 4, 1, 2, 6, 0, 2, 4, 3, 1, 9, 2, 3, 4, 2, 0, 7, 1, 4, 4, 5, 0, 8, 4, 1, 3, 3, 0, 15, 0, 3, 4, 4, 4, 13, 2, 4, 2, 5, 2, 10, 0, 2, 11, 2, 3, 12, 0, 6, 6, 2, 2, 13, 3, 5, 7, 5, 1, 16, 4, 4, 6, 3, 2, 11, 0, 8, 6, 7

Offset: 1

Zhi-Wei Sun, Jan 20 2013

nonn

Conjecture: a(n)>0 for all n>911.

This implies that for each n=2,3,4,... there is a positive integer k

The conjecture has been verified for n up to 10^6.

			a(7) = 1 since 6*7 = 42 is practical, and 41 and 43 are twin primes.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
G. Melfi, On two conjectures about practical numbers, J. Number Theory 56 (1996) 205-210 [MR96i:11106].
Zhi-Wei Sun, Conjectures involving primes and quadratic forms, arXiv:1211.1588 [math.NT], 2012-2017.

Cf. A005153, A071558, A208243, A208244, A208246, A208249, A209236, A209253, A209254, A209312, A219185, A219312, A219315, A219320.

f[n_]:=f[n]=FactorInteger[n]
Pow[n_, i_]:=Pow[n, i]=Part[Part[f[n], i], 1]^(Part[Part[f[n], i], 2])
Con[n_]:=Con[n]=Sum[If[Part[Part[f[n], s+1], 1]<=DivisorSigma[1, Product[Pow[n, i], {i, 1, s}]]+1, 0, 1], {s, 1, Length[f[n]]-1}]
pr[n_]:=pr[n]=n>0&&(n<3||Mod[n, 2]+Con[n]==0)
a[n_]:=a[n]=Sum[If[PrimeQ[k*n-1]==True&&PrimeQ[k*n+1]==True&&pr[k*n]==True,1,0],{k,1,n-1}]
Do[Print[n," ",a[n]],{n,1,100}]

A210452 Number of integers k

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Jan 20 2013

nonn

Conjecture: a(n)>0 for all n>4.
This implies the twin prime conjecture since k*p is not practical for any prime p>sigma(k)+1.
Zhi-Wei Sun also made the following conjectures:
(1) For each integer n>197, there is a practical number k(2) For every n=9,10,... there is a practical number k(3) For any integer n>26863, the interval [1,n] contains five consecutive integers m-2, m-1, m, m+1, m+2 with m-1 and m+1 both prime, and m-2, m, m+2, m*n all practical.

			a(11)=1 since 5 and 7 are twin primes, and 6 and 6*11 are both practical.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
G. Melfi, On two conjectures about practical numbers, J. Number Theory 56 (1996) 205-210 [MR96i:11106].
Zhi-Wei Sun, Conjectures involving primes and quadratic forms, arXiv:1211.1588 [math.NT], 2012-2017.
Zhi-Wei Sun, Sandwiches with primes and practical numbers, a message to Number Theory List, Jan. 13, 2013.

Cf. A005153, A210444, A210445, A071558, A208243, A208244, A208246, A208249, A219185, A209253, A209254, A219312, A219315, A219320.

f[n_]:=f[n]=FactorInteger[n]
Pow[n_, i_]:=Pow[n, i]=Part[Part[f[n], i], 1]^(Part[Part[f[n], i], 2])
Con[n_]:=Con[n]=Sum[If[Part[Part[f[n], s+1], 1]<=DivisorSigma[1, Product[Pow[n, i], {i, 1, s}]]+1, 0, 1], {s, 1, Length[f[n]]-1}]
pr[n_]:=pr[n]=n>0&&(n<3||Mod[n, 2]+Con[n]==0)
a[n_]:=a[n]=Sum[If[PrimeQ[k-1]==True&&PrimeQ[k+1]==True&&pr[k]==True&&pr[k*n]==True,1,0],{k,1,n-1}]
Do[Print[n," ",a[n]],{n,1,100}]

A220143 Numbers n that yield a new record for k such that nk+1 and nk-1 are twin primes.

Original entry on oeis.org

1, 5, 8, 11, 13, 31, 37, 53, 61, 433, 1957, 2047, 2603, 4079, 9967, 10789, 76943, 81439, 121763, 206867, 233969, 276349, 495931, 626939, 2055943, 3144937, 3585509, 3810949, 6274823, 8407129, 9299471, 19279903, 35531621, 36426301, 38235389, 71701529, 76384717, 98566373

Offset: 1

T. D. Noe, Jan 08 2013

nonn

These are numbers at which A071558 reaches a new record. The corresponding values of k are in A220144. Note that these numbers are not all primes.

Cf. A071558, A220144.

t = {{1, 4}}; Do[k = 1; While[! (PrimeQ[k*n - 1] && PrimeQ[k*n + 1]), k++]; If[k > t[[-1, 2]], AppendTo[t, {n, k}]], {n, 2, 100000}]; Transpose[t][[1]]

More terms from Amiram Eldar, Dec 30 2019

Showing 1-10 of 15 results. Next

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

A053989 Smallest k such that nk-1 is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

PARI

Formula

A071407 Least k such that k*prime(n) + 1 and k*prime(n) - 1 are twin primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A071256 Smallest multiple of n sandwiched between twin primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A204065 Least nonnegative integer k with n+k and n+k^2 both prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A210445 Least positive integer k with k*n practical.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A071407 Least k such that kprime(n) + 1 and kprime(n) - 1 are twin primes.

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.

A220143 Numbers n that yield a new record for k such that nk+1 and nk-1 are twin primes.