

A034693


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


51



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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 HeathBrown's result (1992) obtained with help of the GRH, it follows that a(n) <= (phi(n)*log(n))^2.  Vladimir Shevelev, Apr 30 2012


REFERENCES

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 2.12, pp. 127130.
P. Ribenboim, (1989), The Book of Prime Number Records. Chapter 4, Section IV.B.: The Smallest Prime In Arithmetic Progressions, pp. 217223.


LINKS



FORMULA

It seems that Sum_{k=1..n} a(k) is asymptotic to (zeta(2)1)*n*log(n) where zeta(2)1 = Pi^2/61 = 0.6449... .  Benoit Cloitre, Aug 11 2002


EXAMPLE

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


MAPLE

for k from 1 do
if isprime(k*n+1) then
return k;
end if;
end do:


MATHEMATICA

a[n_]:=(k=0; While[!PrimeQ[++k*n + 1]]; k); Table[a[n], {n, 100}] (* JeanFrançois Alcover, Jul 19 2011 *)


PROG

(PARI) a(n)=if(n<0, 0, s=1; while(isprime(s*n+1)==0, s++); s)
(Haskell)
a034693 n = head [k  k < [1..], a010051 (k * n + 1) == 1]
(Python)
from sympy import isprime
def a(n):
k = 1
while not isprime(k*n+1): k += 1
return k


CROSSREFS



KEYWORD

nonn,nice


AUTHOR



STATUS

approved



