cp's OEIS Frontend

A210380 Consider all n-tuples of distinct positive integers for which no two different elements add up to a square. This sequence gives the smallest maximal integer in such tuples.

%I A210380 #65 Aug 06 2024 10:33:47
%S A210380 1,2,4,6,9,10,11,15,18,20,21,24,26,28,32,34,36,38,40,42,50,52,54,56,
%T A210380 58,60,62,64,72,74,76,78,80,82,84,86,88,99,101,103,105,107,109,111,
%U A210380 114,116,118,129,130,133,135,137,139,141,143,145,152,159,160,163,167
%N A210380 Consider all n-tuples of distinct positive integers for which no two different elements add up to a square. This sequence gives the smallest maximal integer in such tuples.
%D A210380 J. P. Massias, Sur les suites dont les sommes des termes 2 à 2 ne sont pas des carrés, Publications du département de mathématiques de Limoges, 1982.
%H A210380 Giovanni Resta, <a href="/A210380/b210380.txt">Table of n, a(n) for n = 1..175</a> (first 100 terms from Jon E. Schoenfield)
%H A210380 Ayman Khalfalah, Sachin Lodha, and Endre Szemerédi, <a href="https://citeseerx.ist.psu.edu/pdf/49bd02834127972c11fe3862c75203ffa82da74c">Tight bound for the density of sequence of integers the sum of no two of which is a perfect square</a>, Discr. Math. 256 (2002) 243 <a href="http://dx.doi.org/10.1016/S0012-365X(01)00435-6">[DOI]</a>
%H A210380 J. C. Lagarias, A. M. Odlyzko, J. B. Shearer, <a href="http://dx.doi.org/10.1016/0097-3165(82)90005-X">On the density of sequences of integers the sum of no two of which is a square. I. Arithmetic progressions</a>, Journal of Combinatorial Theory. Series A, 33 (1982), pp. 167-185.
%H A210380 J. C. Lagarias, A. M. Odlyzko, J. B. Shearer, <a href="http://dx.doi.org/10.1016/0097-3165(83)90051-1">On the density of sequences of integers the sum of no two of which is a square. II. General sequences</a>, Journal of Combinatorial Theory. Series A, 34 (1983), pp. 123-139.
%H A210380 Jon E. Schoenfield, <a href="/A210380/a210380.txt">Lexicographically first sequences for n = 1..100</a>
%H A210380 Jon E. Schoenfield, <a href="/A210380/a210380_1.txt">Excel/VBA macro</a>
%F A210380 a(n) ~ (32/11)*n.
%F A210380 a(n) <= (32/11)*n - 2. Erdős conjectured that a(n) >= (32/11)*n - k for some fixed k.
%e A210380 For a(29)=72 one sequence is 8, 10, 12, 14, 19, 21, 23, 25, 27, 29, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 51, 53, 55, 57, 59, 61, 63, 65, 72. - _Giovanni Resta_, Dec 24 2012
%e A210380 The above example sequence is the lexicographically first 29-tuple of distinct positive integers for which no two different elements add up to a square and the maximal integer is a(29). For such sequences for a(1)..a(100), see the "Lexicographically first sequences for n = 1..100" link. - _Jon E. Schoenfield_, Jan 31 2014
%t A210380 CZ[v_List] :=
%t A210380    Block[{u = Most[v]}, If[Length[u] > 0 && Last[u] == 0, CZ[u], u]]
%t A210380 ev[v_List] := ev[v] =
%t A210380    Module[{h = Plus @@ v, u = v}, If[h < 2, h, h = ev[CZ[u]];
%t A210380     For[k = Floor[Sqrt[Length[u]]] + 1, k < Sqrt[2*Length[u]], k++,
%t A210380      u[[k^2 - Length[u]]] = 0]; Max[h, 1 + ev[CZ[u]]]]]
%t A210380 a[n_] := Module[{k = n, t}, While[True, t = ev[Table[1, {k}]];
%t A210380    If[t == n, Return[k], k += n - t]]]
%o A210380 (PARI) most(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=most(u);for(k=sqrtint(m)+1,sqrtint(2*m-1),u[k^2-m]=0);max(h,1+most(u))
%o A210380 a(n)=my(k=n,t);while(1,t=most(vector(k,i,1));if(t==n,return(k));k+=n-t)
%Y A210380 See A099107 for another version.
%Y A210380 Cf. A210570 (no two elements differ by a square).
%K A210380 nonn,nice
%O A210380 1,2
%A A210380 _Charles R Greathouse IV_, Mar 27 2012
%E A210380 a(25)-a(29) from _Giovanni Resta_, Dec 24 2012
%E A210380 More terms from _Jon E. Schoenfield_, Dec 28 2013