A210570 -id:A210570 - cp's OEIS frontend

A100719 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.

1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 20

Offset: 1

N. J. A. Sloane, Sep 17 2007

nonn

Prompted by a question about the rate of growth of this sequence asked by Sujith Vijay (sujith(AT)EDEN.RUTGERS.EDU) to the Number Theory List.
The problem can be thought of as finding a maximum independent set in a graph with node set {1, 2, ..., n} and an edge (i, j) if |i - j| is a square. - Rob Pratt
The index of the first occurrence of m is A210570(m). - Glen Whitney, Aug 30 2015

H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions, J. Analyse Math. 31 (1977), 204-256.
A. Sárközy, On difference sets of sequences of integers II, Annales Univ. Sci. Budapest, Sectio Math.

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..410 (terms n = 1..100 from Rob Pratt)
A. Balog, J. Pelikan, J. Pintz and E. Szemeredi, Difference sets without kappa-th powers, Acta Math. Hungar. 65 (1994), no. 2, 165-187.
Thomas F. Bloom and James Maynard, A new upper bound for sets with no square differences, arXiv:2011.13266 [math.NT], 2020-2021; Compositio Mathematica 158.8 (2022): 1777-1798.
Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 3..314, Nov 28 2018.
Ben Green and Mehtaab Sawhney, Improved bounds for the Furstenberg-Sárközy theorem, arXiv preprint arXiv:2411.17448 [math.NT], 2024.
J. Pintz, W. L. Steiger and E. Szemeredi, On Sets of Natural Numbers Whose Difference Set Contains No Squares, J. London. Math. Soc. 37, 1988, 219-231.
I. Ruzsa, Difference sets without squares, Period. Math. Hungar. 15 (1984), no. 3, 205-209.
A. Sárközy, On difference sets of sequences of integers I, Acta Mathematica Academiae Scientiarum Hungarica, March 1978, Volume 31, Issue 1, pp 125-149.
A. Sárközy, On difference sets of sequences of integers III, Acta Mathematica Academiae Scientiarum Hungarica, September 1978, Volume 31, Issue 3, pp 355-386.

Cf. A210570.

Cf. A131752, A131753, A131754.

a(n) >> n^0.733 (I. Ruzsa, Period. Math. Hungar. 15 (1984), no. 3, 205-209). The best upper bound appears to be O(N (log n)^(- c log log log log N)) due to Pintz, Steiger and Szemeredi (J. London. Math. Soc. 37, 1988, 219-231). - Sujith Vijay, Sep 18 2007
A. Sárközy worked on this problem. There is also the following result of A. Balog, J. Pelikan, J. Pintz, E. Szemeredi: the size of largest squarefree difference sets = O(N / (log N)^(log log log log N / 4)). - Tsz Ho Chan (tchan(AT)MEMPHIS.EDU), Sep 19 2007
Green & Sawhney improve the upper bound to a(n) << n exp(-(log n)^c) for any c < 1/4. - Charles R Greathouse IV, Nov 28 2024

Computed via integer programming by Rob Pratt, Sep 17 2007

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.

Original entry on oeis.org

1, 2, 4, 6, 9, 10, 11, 15, 18, 20, 21, 24, 26, 28, 32, 34, 36, 38, 40, 42, 50, 52, 54, 56, 58, 60, 62, 64, 72, 74, 76, 78, 80, 82, 84, 86, 88, 99, 101, 103, 105, 107, 109, 111, 114, 116, 118, 129, 130, 133, 135, 137, 139, 141, 143, 145, 152, 159, 160, 163, 167

Offset: 1

Charles R Greathouse IV, Mar 27 2012

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

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.

Giovanni Resta, Table of n, a(n) for n = 1..175 (first 100 terms from Jon E. Schoenfield)
Ayman Khalfalah, Sachin Lodha, and Endre Szemerédi, Tight bound for the density of sequence of integers the sum of no two of which is a perfect square, Discr. Math. 256 (2002) 243 [DOI]
J. C. Lagarias, A. M. Odlyzko, J. B. Shearer, On the density of sequences of integers the sum of no two of which is a square. I. Arithmetic progressions, Journal of Combinatorial Theory. Series A, 33 (1982), pp. 167-185.
J. C. Lagarias, A. M. Odlyzko, J. B. Shearer, On the density of sequences of integers the sum of no two of which is a square. II. General sequences, Journal of Combinatorial Theory. Series A, 34 (1983), pp. 123-139.
Jon E. Schoenfield, Lexicographically first sequences for n = 1..100
Jon E. Schoenfield, Excel/VBA macro

See A099107 for another version.

Cf. A210570 (no two elements differ by a square).

CZ[v_List] :=
   Block[{u = Most[v]}, If[Length[u] > 0 && Last[u] == 0, CZ[u], u]]
ev[v_List] := ev[v] =
   Module[{h = Plus @@ v, u = v}, If[h < 2, h, h = ev[CZ[u]];
    For[k = Floor[Sqrt[Length[u]]] + 1, k < Sqrt[2*Length[u]], k++,
     u[[k^2 - Length[u]]] = 0]; Max[h, 1 + ev[CZ[u]]]]]
a[n_] := Module[{k = n, t}, While[True, t = ev[Table[1, {k}]];
   If[t == n, Return[k], k += n - t]]]

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))
a(n)=my(k=n,t);while(1,t=most(vector(k,i,1));if(t==n,return(k));k+=n-t)

a(n) ~ (32/11)*n.

a(n) <= (32/11)*n - 2. Erdős conjectured that a(n) >= (32/11)*n - k for some fixed k.

a(25)-a(29) from Giovanni Resta, Dec 24 2012

More terms from Jon E. Schoenfield, Dec 28 2013

A224839 a(1) = 1 and a(n) is the smallest number greater than a(n-1) with no square difference with any preceding term.

Original entry on oeis.org

1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, 53, 58, 63, 66, 68, 73, 86, 96, 110, 120, 125, 128, 131, 133, 138, 143, 148, 151, 171, 178, 181, 183, 188, 193, 198, 205, 211, 216, 239, 244, 250, 256, 258, 261, 263, 268, 273

Offset: 1

Jean-François Alcover, Sep 18 2013

nonn

The first 11 terms are identical to those of A210570.

This sequence represents the losing positions in the misère version of a one-heap nim game, where players remove a square number of objects (> 0) on their turn. - Kiran Ananthpur Bacche, Feb 23 2025

Jean-François Alcover, Table of n, a(n) for n = 1..1000

Cf. A030193, A210570, A010052.

a224839 n = a224839_list !! (n-1)
a224839_list = f [1..] [] where
   f (x:xs) ys = if all ((== 0) . a010052) $ map (x -) ys
                    then x : f xs (x:ys) else f xs ys
-- Reinhard Zumkeller, May 02 2014

N:= 1000: # to get all terms <= N
V:= Vector(N):
Res:= NULL:
for m from 1 to N do
  if V[m] = 0 then
    V[m]:= 1;
    Res:= Res, m;
    for k from 1 to floor(sqrt(N-m)) do V[m+k^2]:= 1 od:
  fi
od:
Res; # Robert Israel, Nov 30 2016

a[1] = 1; a[n_] := a[n] = For[k = a[n-1]+1, True, k++, If[FreeQ[k - Array[a, n-1], d_ /; IntegerQ[Sqrt[d]]], Return[k]]]; Table[a[n], {n, 1, 40}]

a(n) >= A210570(n) by definition of the latter. - Charles R Greathouse IV, Nov 28 2024

a(n) = A030193(n-1) + 1. - Kiran Ananthpur Bacche, Feb 23 2025

cp's OEIS Frontend

A100719 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A224839 a(1) = 1 and a(n) is the smallest number greater than a(n-1) with no square difference with any preceding term.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula