A174911 Sequence by greedy construction satisfying Lucier-Sárközy difference set condition.

1, 4, 9, 12, 33, 36, 57, 60, 65, 68, 119, 122, 209, 212, 217, 220, 623, 626, 713, 716, 721, 724, 745, 748, 897, 900, 987, 990, 2561, 2564, 2779, 2782, 3807, 3810, 3891, 3894, 4199, 4202, 4585, 4588, 5339, 5342, 5459, 5462, 5963, 5966, 8643, 8646, 12085, 12088

Offset: 1

Author

Jonathan Vos Post, Apr 01 2010

Keywords

• nonn

Comments

a(1) = 1. a(n) = least positive integer k such that the difference between any two elements of {a(1), ..., a(n-1)} is never one less than a prime.

Examples

			a(1) = 1 by definition.
a(2) cannot be 2 because 2-a(1)=2-1=1 which is 1 less than 2=prime(1). a(2) cannot be 3 because 3-a(1)=3-1=2 which is 1 less than 3=prime(2). a(2) = 4 because the next smallest integer 4 is such that 4-1=3 and 3+1 is not prime.
Next, a(3) cannot be 5 or 6 because as above, an increment of 1 or 2 above the previous value does not work. a(3) cannot be 8 because 8-4=4 and 4+1 is 5 = prime(3). However, a(3)=9 because 9-1=8 (not 1 less than a prime) and 9-4=5 (not 1 less than a prime).
		

References

• J. Lucier. Difference sets and shifted primes. Acta Math. Hungar., 120(1-2):79-102, 2008.
• I. Z. Ruzsa. On measures on intersectivity. Acta Math. Hungar., 43(3-4):335-340, 1984.
• A. Sárközy. On difference sets of sequences of integers. III. Acta Math. Acad. Sci. Hungar., 31(3-4):355-386, 1978.

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..696 (terms 1..274 from Alois P. Heinz)
• Imre Z. Ruzsa, Tom Sanders, Difference sets and the primes, April 1, 2010.

Crossrefs

Cf. A000040, A131849.

Programs

Maple

A174911 := proc(n) option remember ; local wrks,a,i; if n = 1 then 1; elif n = 2 then 4; else for a from procname(n-1)+1 do wrks := true; for i from 1 to n-1 do if isprime(abs(a-procname(i))+1) then wrks := false; break; end if; end do; if wrks then return a; end if; end do: end if: end proc: seq(A174911(n),n=1..80) ; # R. J. Mathar, Apr 15 2010

Mathematica

a[1] = 1; a[n_] := a[n] = For[k = 2, True, k++, If[FreeQ[aa = Array[a, n-1], k] && AllTrue[Abs[k-aa], !PrimeQ[#+1]&], Return[k]]]; Array[a, 50] (* Jean-François Alcover, Nov 07 2017 *)

Python

from gmpy2 import is_prime
from itertools import count, islice
def agen(): # generator of terms
    alst = [1]
    yield 1
    for m in count(2):
        if all(not is_prime(m-ai+1) for ai in alst):
            alst.append(m)
            yield alst[-1]
print(list(islice(agen(), 50))) # Michael S. Branicky, Oct 13 2024

Extensions

More terms from R. J. Mathar, Apr 15 2010