A309179 Primes to which a record size square needs to be added to reach another prime.

2, 3, 5, 29, 41, 389, 479, 881, 1931, 3461, 3701, 7589, 9749, 26171, 153089, 405701, 1036829, 1354349, 1516829, 2677289, 4790309, 4990961, 34648631, 46214321, 50583209, 98999969, 305094851, 331498961, 362822099, 4373372351, 11037674441, 12239355719, 16085541359

Offset: 1

Author

Bert Dobbelaere, Jul 15 2019

Keywords

• nonn

Comments

a(1) = 2 and r(1) = 1.

For n > 1, a(n) is the smallest prime for which r(n) > r(n-1) exists so that a(n) + r(n)^2 is prime and a(n) + k^2 are composite for 0 < k < r(n).

When omitting the squares in the description, the sequence becomes A002386.

Examples

			a(1) = 2; r(1) = 1.
a(2) = 3; 3 + 1^2 is composite, but 3 + 2^2 is prime, so r(2) = 2.
a(3) = 5; 5 + k^2 is composite for 0 < k < 6, but 5 + 6^2 is prime, so r(3) = 6.
The following are primes: 7 + 2^2, 11 + 6^2, 13 + 2^2, 17 + 6^2, 19 + 2^2, 23 + 6^2.
a(4) = 29; 29 + k^2 is composite for 0 < k < 12, but 29 + 12^2 is prime: r(4) = 12.
		

Crossrefs

Cf. A002386, A020495, A065376, A127356, A129314.

Programs

PARI

f(n) = {k=1; while(!isprime(n+k^2), k++); k;}
lista(NN) = {m=0; forprime(p=1, NN, if(f(p)>m, m=f(p);print1(p,", ")))} \\ Jinyuan Wang, Jul 15 2019

Python

from sympy import isprime, nextprime
n, p, r = 0, 0, 0
while(True):
    p = nextprime(p) ; k = 1
    while not isprime(p + k**2):
        k += 1
    if k > r:
        n += 1 ; r = k
        print("a({}) = {}".format(n,p))

Extensions

a(30)-a(33) from Giovanni Resta, Jul 16 2019