A200996 -id:A200996 - 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.

A071558 Smallest k such that nk + 1 and nk - 1 are twin primes.

Original entry on oeis.org

4, 2, 2, 1, 6, 1, 6, 9, 2, 3, 18, 1, 24, 3, 2, 12, 6, 1, 12, 3, 2, 9, 6, 3, 6, 12, 4, 15, 12, 1, 42, 6, 6, 3, 12, 2, 54, 6, 8, 6, 30, 1, 24, 15, 4, 3, 6, 4, 18, 3, 2, 6, 120, 2, 12, 48, 4, 6, 18, 1, 258, 21, 14, 3, 30, 3, 24, 15, 2, 6, 18, 1, 84, 27, 2, 3, 6, 4, 132, 3, 10, 15, 54, 5, 12, 12

Offset: 1

Benoit Cloitre, May 30 2002

Conjecture: a(n) < sqrt(n)*log(n) for all n > 17261. This has been verified for n up to 3*10^7. It implies the inequality a(n) < n for each n > 127. - Zhi-Wei Sun, Jan 07 2013

A200996(n) <= a(n). - Reinhard Zumkeller, Feb 14 2013

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)

Cf. A071256, A001097, A086686, A034693.
Cf. A071407 (k at prime n).
Cf. A220143, A220144 (record values).

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

Table[k=1; While[!And@@PrimeQ[n*k+{1,-1}],k++]; k,{n,86}] (* Jayanta Basu, May 26 2013 *)

a(n) = my(s=1); while(isprime(s*n+1)*isprime(n*s-1)==0, s++); s;

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

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

A071558 Smallest k such that n*k + 1 and n*k - 1 are twin primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

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

A071558 Smallest k such that nk + 1 and nk - 1 are twin primes.

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