cp's OEIS Frontend

A210570 Consider all sequences of n distinct positive integers for which no two different elements have a difference which is a square. This sequence gives the smallest maximal integer in such sequences.

%I A210570 #88 Nov 28 2024 21:28:11
%S A210570 1,3,6,8,11,13,16,18,21,23,35,38,43,48,53,58,66,68,71,73,81,86,92,97,
%T A210570 102,107,112,118,120,125,131,133,138,144,146,151,157,159,164,189,199,
%U A210570 203,206,208,219,223,236,242,248,253,258,263,266,269,283,285,288,293,311,314,323,328,331,334,343,346
%N A210570 Consider all sequences of n distinct positive integers for which no two different elements have a difference which is a square. This sequence gives the smallest maximal integer in such sequences.
%C A210570 László Lovász conjectured, and Hillel Furstenberg and András Sárközy (1978) independently showed that a(n) is superlinear. Erdős conjectured that a(n) >> n^2/log^k n for some k. Sárközy proved that a(n) = o(n^2/log^k n) for all k, but still conjectured that a(n) >> n^(2-e) for all e > 0. Ruzsa showed that in fact a(n) << n^1.365.
%C A210570 a(n) is the least m such that A100719(m) = n. - _Glen Whitney_, Aug 30 2015
%D A210570 András Sárközy, On difference sets of sequences of integers, II., Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica 21 (1978), pp. 45-53.
%H A210570 Fausto A. C. Cariboni, <a href="/A210570/b210570.txt">Table of n, a(n) for n = 1..74</a>
%H A210570 Fausto A. C. Cariboni, <a href="/A210570/a210570.txt">Sets that yield a(n) for n = 2..74</a>, Feb 03 2019
%H A210570 Hillel Furstenberg, <a href="http://dx.doi.org/10.1007/BF02813304">Ergodic behaviour of diagonal measures and a theorem of Szemeredi on arithmetic progressions</a>, J. Analyse Math. 31 (1977), pp. 204-256.
%H A210570 Ben Green and Mehtaab Sawhney, <a href="https://arxiv.org/abs/2411.17448">Improved bounds for the Furstenberg-Sárközy theorem</a>, arXiv preprint arXiv:2411.17448 [math.NT], 2024.
%H A210570 Janos Pintz, W. L. Steiger and Endre Szemerédi, <a href="http://www.cs.umd.edu/~gasarch/TOPICS/vdw/pss.pdf">On sets of natural numbers whose difference set contains no squares</a>, J. London Math. Soc. 37:2 (1988), pp. 219-231.
%H A210570 I. Z. Ruzsa, <a href="http://www.cs.umd.edu/~gasarch/TOPICS/vdw/sqdiff-ruzsa.pdf">Difference sets without squares</a>, Periodica Mathematica Hungarica 15:3 (1984), pp. 205-209.
%H A210570 András Sárközy, <a href="http://www.cs.umd.edu/~gasarch/TOPICS/vdw/sarkozyONE.pdf">On difference sets of sequences of integers, I.</a>, Acta Mathematica Academiae Scientiarum Hungaricae 31:1-2 (1978), pp. 125-149.
%F A210570 n * (log n)^((1/12) * log log log log n) << a(n) << n^k with k = 2/(1+log(7)/log(65)) = 1.364112553....
%F A210570 Green & Sawhney improve the lower bound to n * exp((log n)^c) for any c < 1/4. - _Charles R Greathouse IV_, Nov 27 2024
%e A210570 There are no nontrivial differences in {1}, so a(1) = 1. {1, 2} contains the square 2-1 as a difference, but {1, 3} is valid so a(2) = 3.
%e A210570 a(3) = 6: {1, 3, 6}
%e A210570 a(4) = 8: {1, 3, 6, 8}
%e A210570 a(5) = 11: {1, 3, 6, 8, 11}
%e A210570 a(6) = 13: {1, 3, 6, 8, 11, 13}
%e A210570 a(7) = 16: {1, 3, 6, 8, 11, 13, 16}
%e A210570 a(8) = 18: {1, 3, 6, 8, 11, 13, 16, 18}
%e A210570 a(9) = 21: {1, 3, 6, 8, 11, 13, 16, 18, 21}
%e A210570 a(10) = 23: {1, 3, 6, 8, 11, 13, 16, 18, 21, 23}
%e A210570 a(11) = 35: {1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35}
%e A210570 a(12) = 38: {1, 4, 6, 9, 11, 14, 16, 21, 28, 33, 35, 38}
%e A210570 a(13) = 43: {1, 3, 6, 9, 11, 14, 16, 21, 33, 35, 38, 40, 43}
%o A210570 (PARI) ev(v)=my(h=sum(i=1, #v, v[i]), m, u); if(h<2, return(h)); m=#v; while(v[m]==0, m--); u=vector(m-1, i, v[i]); h=ev(u); for(k=1, sqrtint(m-1), u[m-k^2]=0); max(h, 1+ev(u))
%o A210570 a(n)=my(k=(5*n-3)\2, t); while(1, t=ev(vector(k, i, 1)); if(t==n, return(k)); k+=n-t)
%Y A210570 Cf. A210380 (no two elements sum to a square).
%Y A210570 Cf. A224839.
%K A210570 nonn,nice
%O A210570 1,2
%A A210570 _Charles R Greathouse IV_, Apr 02 2012
%E A210570 a(17)-a(31) from _Giovanni Resta_, Dec 21 2012
%E A210570 a(32)-a(58) from _Jon E. Schoenfield_, Dec 28 2013
%E A210570 a(59)-a(66) from _Fausto A. C. Cariboni_, Nov 28 2018