|
%I #90 Jul 23 2023 07:14:03
%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 T. D. Noe, <a href="/A034693/b034693.txt">Table of n, a(n) for n = 1..10000</a>
%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 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 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 I. Niven and B. Powell, <a href="http://www.jstor.org/stable/2318341">Primes in Certain Arithmetic Progressions</a>, Amer. Math. Monthly, 83, 1976, pp. 467-489.
%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_
|
