|
%I #78 Sep 07 2023 04:25:29
%S 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 102,107,112,118,120,125,131,133,138,144,146,151,157,159,164,189,199,
%U 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 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 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 a(n) is the least m such that A100719(m) = n. - _Glen Whitney_, Aug 30 2015
%D 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 Fausto A. C. Cariboni, <a href="/A210570/b210570.txt">Table of n, a(n) for n = 1..74</a>
%H Fausto A. C. Cariboni, <a href="/A210570/a210570.txt">Sets that yield a(n) for n = 2..74</a>, Feb 03 2019
%H 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 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 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 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 n * (log n)^((1/12) * log log log log n) << a(n) << n^1.365.
%e 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.
%o (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 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 Cf. A210380 (no two elements sum to a square).
%Y Cf. A224839.
%K nonn,nice
%O 1,2
%A _Charles R Greathouse IV_, Apr 02 2012
%E a(17)-a(31) from _Giovanni Resta_, Dec 21 2012
%E a(32)-a(58) from _Jon E. Schoenfield_, Dec 28 2013
%E a(59)-a(66) from _Fausto A. C. Cariboni_, Nov 28 2018
|
