|
|
A100719
|
|
Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.
|
|
8
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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.
|
|
REFERENCES
|
Bloom, Thomas F., and James Maynard. "A new upper bound for sets with no square differences." Compositio Mathematica 158.8 (2022): 1777-1798; also arXiv:2011.13266, Feb 24 2021.
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.
|
|
LINKS
|
|
|
FORMULA
|
a(n) is known to be at least O(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Computed via integer programming by Rob Pratt, Sep 17 2007
|
|
STATUS
|
approved
|
|
|
|