|
Search: id:A100719
|
|
|
| A100719 |
|
Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square. |
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Prompted by a question about thhe 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
|
A. Balog, J. Pelikan, J. Pintz and E. Szemeredi, Difference sets without $\kappa$th powers, Acta Math. Hungar. 65 (1994), no. 2, 165-187.
I. Ruzsa, Period. Math. Hungar. 15 (1984), no. 3, 205-209.
Pintz, Steiger and Szemeredi, J. London. Math. Soc. 37, 1988, 219-231.
A. Sarkozy, On difference sets of sequences of integers I, II, III.
|
|
LINKS
|
Rob Pratt, Table of n, a(n) for n = 1..100
|
|
FORMULA
|
Comment from Sujith Vijay, Sep 18 2007: 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).
Comment from Tsz Ho Chan (tchan(AT)MEMPHIS.EDU), Sep 19 2007: A. Sarkozy worked on this problem. There is also the following result of A. Balog, J. Pelikan, J. Pintz, E. Szemeredi: the size of largest square-free difference sets = O(N / (\log N)^{\log \log \log \log N / 4}).
|
|
CROSSREFS
|
Cf. A131752, A131753, A131754.
Sequence in context: A057366 A061375 A029920 this_sequence A057354 A097508 A109964
Adjacent sequences: A100716 A100717 A100718 this_sequence A100720 A100721 A100722
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Sep 17 2007
|
|
EXTENSIONS
|
Computed via integer programming by Rob Pratt (Rob.Pratt(AT)sas.com), Sep 17 2007
|
|
|
Search completed in 0.002 seconds
|
