login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A034693 Smallest k such that k*n+1 is prime. 48
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

This is true by Dirichlet's theorem on arithmetic progressions: for any pair (r,s) of integers such that gcd(r,s)=1 there are infinitely many primes in the sequence r + k*s; choose r=1 and s=p. - Joerg Arndt, Mar 20 2016

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

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

REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 127-130.

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

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

S. R. Finch, More about 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.

I. Niven and B. Powell, Primes in Certain Arithmetic Progressions, Amer. Math. Monthly, 83, 1976, pp. 467-489.

Wikipedia, Dirichlet's theorem on arithmetic progressions

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/6-1 = 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

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

MATHEMATICA

a[n_]:=(k=0; While[!PrimeQ[++k*n + 1]]; k); Table[a[n], {n, 100}] (* Jean-Fran├ž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]

-- Reinhard Zumkeller, Feb 14 2013

CROSSREFS

Cf. A010051, A034694, A053989, A071558, A085420, A103689, A194945, A200996.

Sequence in context: A205403 A080825 A229724 * A216506 A072342 A257089

Adjacent sequences:  A034690 A034691 A034692 * A034694 A034695 A034696

KEYWORD

nonn,nice

AUTHOR

Labos Elemer

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 22 10:37 EDT 2017. Contains 290946 sequences.