|
|
A210570
|
|
Consider all sequences of n distinct positive integers for which no two different elements have a difference which is a square. This sequence gives the smallest maximal integer in such sequences.
|
|
4
|
|
|
1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 38, 43, 48, 53, 58, 66, 68, 71, 73, 81, 86, 92, 97, 102, 107, 112, 118, 120, 125, 131, 133, 138, 144, 146, 151, 157, 159, 164, 189, 199, 203, 206, 208, 219, 223, 236, 242, 248, 253, 258, 263, 266, 269, 283, 285, 288, 293, 311, 314, 323, 328, 331, 334, 343, 346
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
László Lovász conjectured, and Hillel Furstenberg and András Sárközy (1978) independently showed that a(n) is superlinear. Erdős conjectured that a(n) >> n^2/log^k n for some k. Sárközy proved that a(n) = o(n^2/log^k n) for all k, but still conjectured that a(n) >> n^(2-e) for all e > 0. Ruzsa showed that in fact a(n) << n^1.365.
|
|
REFERENCES
|
András Sárközy, On difference sets of sequences of integers, II., Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica 21 (1978), pp. 45-53.
|
|
LINKS
|
|
|
FORMULA
|
n * (log n)^((1/12) * log log log log n) << a(n) << n^1.365.
|
|
EXAMPLE
|
There are no nontrivial differences in {1}, so a(1) = 1. {1, 2} contains the square 2-1 as a difference, but {1, 3} is valid so a(2) = 3.
|
|
PROG
|
(PARI) ev(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=ev(u); for(k=1, sqrtint(m-1), u[m-k^2]=0); max(h, 1+ev(u))
a(n)=my(k=(5*n-3)\2, t); while(1, t=ev(vector(k, i, 1)); if(t==n, return(k)); k+=n-t)
|
|
CROSSREFS
|
Cf. A210380 (no two elements sum to a square).
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|