|
| |
|
|
A100719
|
|
Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.
|
|
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; refs; listen; history; 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
| 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 squarefree difference sets = O(N / (\log N)^{\log \log \log \log N / 4}).
|
|
|
CROSSREFS
| Cf. A131752, A131753, A131754.
Sequence in context: A189663 A061375 A029920 * A057354 A172476 A172267
Adjacent sequences: A100716 A100717 A100718 * 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
|
| |
|
|
