cp's OEIS Frontend

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

%I A034693 #98 Jul 18 2025 10:13:48
%S A034693 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 A034693 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 A034693 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 A034693 Smallest k such that k*n+1 is prime.
%C A034693 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 A034693 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 A034693 Stronger version of the conjecture verified up to 10^9. - _Mauro Fiorentini_, Jul 23 2023
%C A034693 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 A034693 Conjecture: a(n) = O(log(n)*log(log(n))). - _Thomas Ordowski_, Oct 17 2014
%C A034693 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 A034693 Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127-130.
%D A034693 P. Ribenboim, (1989), The Book of Prime Number Records. Chapter 4, Section IV.B.: The Smallest Prime In Arithmetic Progressions, pp. 217-223.
%H A034693 T. D. Noe, <a href="/A034693/b034693.txt">Table of n, a(n) for n = 1..10000</a>
%H A034693 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 A034693 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 A034693 D. 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 A034693 D. R. Heath-Brown, <a href="https://web.archive.org/web/20160317102203/http://eprints.maths.ox.ac.uk/166/1/linnik.pdf">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 A034693 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 A034693 Ivan Niven and Barry Powell, <a href="http://www.jstor.org/stable/2318341">Primes in Certain Arithmetic Progressions</a>, Amer. Math. Monthly, 83, 1976, pp. 467-489.
%H A034693 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions">Dirichlet's theorem on arithmetic progressions</a>
%F A034693 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 A034693 a(n) = (A034694(n)-1) / n. - _Joerg Arndt_, Oct 18 2020
%e A034693 If n=7, the smallest prime in the sequence 8, 15, 22, 29, ... is 29, so a(7)=4.
%p A034693 A034693 := proc(n)
%p A034693     for k from 1 do
%p A034693         if isprime(k*n+1) then
%p A034693             return k;
%p A034693         end if;
%p A034693     end do:
%p A034693 end proc: # _R. J. Mathar_, Jul 26 2015
%t A034693 a[n_]:=(k=0; While[!PrimeQ[++k*n + 1]]; k); Table[a[n], {n,100}] (* _Jean-François Alcover_, Jul 19 2011 *)
%o A034693 (PARI) a(n)=if(n<0,0,s=1; while(isprime(s*n+1)==0,s++); s)
%o A034693 (Haskell)
%o A034693 a034693 n = head [k | k <- [1..], a010051 (k * n + 1) == 1]
%o A034693 -- _Reinhard Zumkeller_, Feb 14 2013
%o A034693 (Python)
%o A034693 from sympy import isprime
%o A034693 def a(n):
%o A034693     k = 1
%o A034693     while not isprime(k*n+1): k += 1
%o A034693     return k
%o A034693 print([a(n) for n in range(1, 99)]) # _Michael S. Branicky_, May 05 2022
%Y A034693 Cf. A010051, A034694, A053989, A071558, A085420, A103689, A194944 (records), A194945 (positions of records), A200996.
%K A034693 nonn,nice
%O A034693 1,3
%A A034693 _Labos Elemer_