A034693 - OEIS

%I #115 Apr 10 2026 06:22:06

%S 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,

%T 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,

%U 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

%N Smallest k such that k*n+1 is prime.

%C Conjecture: for every n > 1 there exists a number k < n such that n*k + 1 is a prime. - _Amarnath Murthy_, Apr 17 2001

%C 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

%C Stronger version of the conjecture verified up to 10^9. - _Mauro Fiorentini_, Jul 23 2023

%C 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

%C Conjecture: a(n) = O(log(n)*log(log(n))). - _Thomas Ordowski_, Oct 17 2014

%C 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

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.

%D P. Ribenboim, (1989), The Book of Prime Number Records. Chapter 4, Section IV.B.: The Smallest Prime In Arithmetic Progressions, pp. 217-223.

%H Wesley Stuart Kruis, <a href="/A034693/b034693.txt">Table of n, a(n) for n = 1..20000</a> (first 10000 terms from T. D. Noe)

%H Gunther Cornelissen, David Hokken, and Berend Ringeling, <a href="https://arxiv.org/abs/2507.09303">The asymptotic Mahler measure of Gaussian periods</a>, arXiv:2507.09303 [math.NT], 2025. See p. 1.

%H Steven R. Finch, <a href="http://web.archive.org/web/20010207193039/http://www.mathsoft.com/asolve/constant/linnik/linnik.html">Linnik's Constant</a>.

%H S. Graham, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa39/aa3926.pdf">On Linnik's constant</a>, Acta Arithm., 39, 1981, pp. 163-179.

%H D. R. Heath-Brown, <a href="https://ora.ox.ac.uk/objects/uuid:b63b8b4f-ad21-4de4-a86b-c82fdfc87997">Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression</a>, Proc. London Math. Soc. 64(3) (1992), pp. 265-338.

%H Pengcheng Niu and Junli Zhang, <a href="https://doi.org/10.13140/RG.2.2.16430.11848">On Two Conjectures of A. Murthy</a>, ResearchGate (2024).

%H Ivan Niven and Barry Powell, <a href="https://www.jstor.org/stable/2318341">Primes in Certain Arithmetic Progressions</a>, Amer. Math. Monthly, 83, 1976, pp. 467-469.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions">Dirichlet's theorem on arithmetic progressions</a>.

%F 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

%F a(n) = (A034694(n)-1) / n. - _Joerg Arndt_, Oct 18 2020

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

%p A034693 := proc(n)

%p     for k from 1 do

%p         if isprime(k*n+1) then

%p             return k;

%p         end if;

%p     end do:

%p end proc: # _R. J. Mathar_, Jul 26 2015

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

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

%o (Haskell)

%o a034693 n = head [k | k <- [1..], a010051 (k * n + 1) == 1]

%o -- _Reinhard Zumkeller_, Feb 14 2013

%o (Python)

%o from sympy import isprime

%o def a(n):

%o     k = 1

%o     while not isprime(k*n+1): k += 1

%o     return k

%o print([a(n) for n in range(1, 99)]) # _Michael S. Branicky_, May 05 2022

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

%K nonn,nice

%O 1,3

%A _Labos Elemer_