[seqfan] Re: Help, please

Richard Guy rkg at cpsc.ucalgary.ca
Wed Apr 21 00:24:18 CEST 2010


Well done, Franklin.  Will someone put it into
OEIS?  Ditto with `perfect square' replaced
by `prime' (probably already in?) `triangular
number', `pentagonal number' (this one in two
versions, perhaps, since you may take
`positive rank only' or `positive or
negative rank'), `perfect cube',
`Fibonacci number'. ...  Strangely(?)
there are applications for these.   R.

On Tue, 20 Apr 2010, franktaw at netscape.net wrote:

> 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