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
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
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