[seqfan] Re: Help, please
franktaw at netscape.net
franktaw at netscape.net
Wed Apr 21 00:24:56 CEST 2010
Here's another approach: the number of new edges introduced for n is
floor(sqrt(2n-1)) - floor(sqrt(n)).
Naively integrating this gives a(n) = (2sqrt(2) - 2)/3 n^(3/2) + O(n).
This error estimate is almost certainly too large.
The first term here, floor(sqrt(2n-1)), is A103128. (The description
and formula for this sequence were both wrong; I have submitted a
correction. The sequence matching the old description is in the
database.) The cumulative sums of this sequence are not in the database.
The second term, floor(sqrt(n)), is A000196; its sums are in A022554.
There is a useful exact formula in A022554. If we had a similar formula
for the sums of A103128, we would have completely solved the problem.
Franklin T. Adams-Watters
-----Original Message-----
From: franktaw at netscape.net
In PARI, I get:
a(n)=sum(k=1,sqrtint(n+1),ceil(k^2/2)-1)+sum(k=sqrtint(n+1)+1,sqrtint(2*n
-1),n-floor(k^2/2))
which produces:
0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 16, 17, 18, 20, 22, 24,
26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 49, 52, 55, 57, 59, 61, 63,
65, 68, 71, 74, 77, 80, 83, 86, 89, 91, 93, 96, 99, 102, 105, 108, 111,
114, 117, 120, 123, 127, 131, 135, 138, 141, 144, 147, 150, 153, 156,
159, 162, 166, 170, 174, 178, 182, 186, 190, 194, 197, 200, 203, 206,
210, 214, 218, 222, 226, 230, 234, 238, 242, 246, 250, 254, 258, 262,
267, 271
And no, it isn't in the database.
The first sum in that program represents the contribution for
"completed" squares; all pairs of distinct positive integers summing to
k^2 are present. The second sum is naturally the contribution for
squares that are not yet completed. We then have:
a(n)
~ sum(k = 1..sqrt(n), k^2/2) + sum(k=sqrt(n)..sqrt(2*n), n - k^2/2)
~ n^(3/2) * (1/6 + sqrt(2) - 1 - (2sqrt(2) - 1)/6)
= (2sqrt(2) - 2)/3 n^(3/2).
I think we in fact get a(n) = (2sqrt(2) - 2)/3 n^(3/2) + O(sqrt(n)),
but I haven't quite worked it through in enough detail to be sure of
the error term.
Franklin T. Adams-Watters
-----Original Message-----
From: Richard Guy <rkg at cpsc.ucalgary.ca>
I'm sure that this sequence is in OEIS, but
I'm not a good looker, and I've probably
made mistakes.
Number of edges in the graph on n vertices,
1, 2, 3, ..., n, where two vertces are
joined just if their label sum to a perfect
square.
a(1) = 0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9,
11, 13, 15, 16,
E.g., for n = 7 the graph contains the 4 edges
1-3, 2-7, 3-6, 4-5.
For extra credit: what is the size of a(n),
asymptotically?
Thanks in anticipation of help. R.
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list