%I #21 Feb 19 2023 18:45:27
%S 1,4,9,12,33,36,49,52,65,68,105,108,133,136,153,156,209,212,217,220,
%T 243,246,299,302,489,492
%N Least k such that {1, ..., k} contains an n-element set of positive integers satisfying the Lucier-Sárközy difference set condition.
%C 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.
%C By minimality, any such set will contain both 1 and n.
%D J. Lucier. Difference sets and shifted primes. Acta Math. Hungar., 120(1-2):79-102, 2008.
%D I. Z. Ruzsa. On measures on intersectivity. Acta Math. Hungar., 43(3-4):335-340, 1984.
%D A. Sárközy, On difference sets of sequences of integers. III. Acta Math. Acad. Sci. Hungar., 31(3-4):355-386, 1978.
%H Ben Green, <a href="https://arxiv.org/abs/2206.08001">On Sárközy's theorem for shifted primes</a>, arXiv preprint, arXiv:2206.08001 [math.NT], 2022.
%H Imre Z. Ruzsa and Tom Sanders, <a href="https://arxiv.org/abs/0710.0644">Difference sets and the primes</a>, arXiv:0710.0644 [math.CA], 2007. See also <a href="https://www.impan.pl/shop/en/publication/transaction/download/product/82894">Acta Arithmetica</a> (2008) Vol. 131, No. 3, 281-301.
%H Jesse Thorner and Asif Zaman, <a href="https://arxiv.org/abs/2208.11123">An explicit version of Bombieri's log-free density estimate and Sárközy's theorem for shifted primes</a>, arXiv preprint, arXiv:2208.11123 [math.NT], 2022.
%F a(n) <= A174911(n).
%F 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.
%e Minimal sets (not necessarily unique):
%e a(1) = 1: {1}
%e a(2) = 4: {1, 4}
%e a(3) = 9: {1, 4, 9}
%e a(4) = 12: {1, 4, 9, 12}
%e a(5) = 33: {1, 4, 9, 12, 33}
%e a(6) = 36: {1, 4, 9, 12, 33, 36}
%e a(7) = 49: {1, 4, 12, 15, 35, 38, 49}
%e a(8) = 52: {1, 4, 15, 18, 35, 38, 49, 52}
%e a(9) = 65: {1, 4, 9, 12, 33, 36, 57, 60, 65}
%e a(10) = 68: {1, 4, 9, 12, 33, 36, 57, 60, 65, 68}
%e a(11) = 105: {1, 4, 12, 25, 36, 49, 57, 60, 68, 81, 105}
%e a(12) = 108: {1, 4, 25, 28, 49, 52, 57, 60, 81, 84, 105, 108}
%e a(13) = 133: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133}
%e a(14) = 136: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136}
%e a(15) = 153: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153}
%e a(16) = 156: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156}
%e a(17) = 209: {1, 18, 27, 32, 35, 52, 91, 108, 111, 116, 125, 142, 145, 159, 192, 206, 209}
%e a(18) = 212: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212}
%e a(19) = 217: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217}
%e a(20) = 220: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217, 220}
%e a(21) = 243: {1, 4, 9, 12, 35, 38, 85, 88, 99, 102, 119, 122, 133, 136, 153, 156, 209, 212, 217, 220, 243}
%e 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}
%e 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}
%e 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}
%e From _Bert Dobbelaere_, Feb 19 2023: (Start)
%e 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}
%e 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}
%e (End)
%o (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)
%o 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
%o bd(n)=n--; 3*n+n\2*2+1
%o A(n,startAt=bd(n))=for(k=startAt,oo,my(t=try(n,k));if(t,return(t)))
%o a(n)=A(n)[n]
%Y Cf. A174911.
%K nonn,more,nice
%O 1,2
%A _Charles R Greathouse IV_, Dec 24 2022
%E a(25)-a(26) from _Bert Dobbelaere_, Feb 19 2023