[seqfan] Re: Help, please

[franktaw at netscape.net]

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/