A359301 Least k such that {1, ..., k} contains an n-element set of positive integers satisfying the Lucier-Sárközy difference set condition.

1, 4, 9, 12, 33, 36, 49, 52, 65, 68, 105, 108, 133, 136, 153, 156, 209, 212, 217, 220, 243, 246, 299, 302, 489, 492

Offset

1,2

Comments

The Lucier-Sárközy difference set condition is that the difference between any two elements of A is never one less than a prime.

By minimality, any such set will contain both 1 and n.

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

Table of n, a(n) for n=1..26.

Ben Green, On Sárközy's theorem for shifted primes, arXiv preprint, arXiv:2206.08001 [math.NT], 2022.

Imre Z. Ruzsa and Tom Sanders, Difference sets and the primes, arXiv:0710.0644 [math.CA], 2007. See also Acta Arithmetica (2008) Vol. 131, No. 3, 281-301.

Jesse Thorner and Asif Zaman, An explicit version of Bombieri's log-free density estimate and Sárközy's theorem for shifted primes, arXiv preprint, arXiv:2208.11123 [math.NT], 2022.

Formula

a(n) <= A174911(n).

Sárközy proved that a(n)/n increases without bound. This was sharpened by others, with Green eventually proving that there is some c > 1 such that a(n) >> n^c. Thorner & Zaman made this effective, proving a(n) >> n^(1 + 1.32/10^18). On GRH, Green has proved that a(n) >> n^c for any c < 12/11.

Example

Minimal sets (not necessarily unique):
a(1) = 1: {1}
a(2) = 4: {1, 4}
a(3) = 9: {1, 4, 9}
a(4) = 12: {1, 4, 9, 12}
a(5) = 33: {1, 4, 9, 12, 33}
a(6) = 36: {1, 4, 9, 12, 33, 36}
a(7) = 49: {1, 4, 12, 15, 35, 38, 49}
a(8) = 52: {1, 4, 15, 18, 35, 38, 49, 52}
a(9) = 65: {1, 4, 9, 12, 33, 36, 57, 60, 65}
a(10) = 68: {1, 4, 9, 12, 33, 36, 57, 60, 65, 68}
a(11) = 105: {1, 4, 12, 25, 36, 49, 57, 60, 68, 81, 105}
a(12) = 108: {1, 4, 25, 28, 49, 52, 57, 60, 81, 84, 105, 108}
a(13) = 133: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133}
a(14) = 136: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136}
a(15) = 153: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153}
a(16) = 156: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156}
a(17) = 209: {1, 18, 27, 32, 35, 52, 91, 108, 111, 116, 125, 142, 145, 159, 192, 206, 209}
a(18) = 212: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212}
a(19) = 217: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217}
a(20) = 220: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217, 220}
a(21) = 243: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217, 220, 243}
a(22) = 246: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217, 220, 243, 246}
a(23) = 299: {1, 27, 35, 38, 46, 72, 91, 111, 122, 125, 136, 145, 156, 159, 170, 190, 209, 235, 243, 246, 254, 280, 299}
a(24) = 302: {1, 4, 57, 60, 65, 68, 91, 94, 141, 144, 155, 158, 175, 178, 189, 192, 209, 212, 265, 268, 273, 276, 299, 302}
From Bert Dobbelaere, Feb 19 2023: (Start)
a(25) = 489: {1, 4, 12, 21, 60, 85, 105, 144, 158, 189, 203, 237, 278, 287, 312, 321, 326, 346, 371, 402, 405, 410, 455, 486, 489}
a(26) = 492: {1, 4, 21, 24, 85, 88, 105, 108, 189, 192, 203, 206, 237, 240, 287, 290, 321, 324, 371, 374, 405, 408, 455, 458, 489, 492}
(End)

Prog

(PARI) try(n, k)=my(v=vectorsmall(k, i, i==1||i==k), t); forprime(p=2, k, v[p]=-1; v[k-p+1]=-1); if(v[1]<0, return(0)); t=test(v, n-2, 2); if(t, Set(vector(k, i, if(t[i]==1, i, 1))), 0)
test(v, n, startAt=1)=if(n==0, return(v)); for(i=startAt, #v, if(v[i], next); my(u=v, t); u[i]=1; forprime(p=2, #v+1-i, my(idx=i+p-1); if(u[idx]==1, v[i]=-1; return(test(v, n, i+1))); u[idx]=-1); t=test(u, n-1, i+1); if(t, return(t)); v[i]=-1; return(test(v, n, i+1))); 0
bd(n)=n--; 3*n+n\2*2+1
A(n, startAt=bd(n))=for(k=startAt, oo, my(t=try(n, k)); if(t, return(t)))
a(n)=A(n)[n]

Crossrefs

Cf. A174911.

Sequence in context: A083351 A055381 A287498 * A174911 A032820 A197615

Adjacent sequences: A359298 A359299 A359300 * A359302 A359303 A359304

Keyword

nonn,more,nice

Author

Charles R Greathouse IV, Dec 24 2022

Extensions

a(25)-a(26) from Bert Dobbelaere, Feb 19 2023

Status

approved