

A176615


Number of edges in the graph on n vertices, labeled 1 to n, where two vertices are joined just if their labels sum to a perfect square.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Equivalently, number of pairs of integers 0 < i < j <= n such that i + j is a square.
Suggested by R. K. Guy


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..20000


FORMULA

Asymptotically, a(n) ~ (2*sqrt(2)  2)/3 n^(3/2). The error term is probably O(n^(1/2)); O(n) is easily provable.


EXAMPLE

For n = 7 the graph contains the 4 edges 13, 27, 36, 45.


MAPLE

b:= n> 1+floor(sqrt(2*n1))ceil(sqrt(n+1)):
a:= proc(n) option remember; `if`(n=0, 0, a(n1)+b(n)) end:
seq(a(n), n=1..100); # Alois P. Heinz, Jan 30 2017


MATHEMATICA

a[n_] := Sum[Floor[Sqrt[2k1]]  Floor[Sqrt[k]], {k, 1, n}]; Table[a[n], {n, 1, 68}] (* JeanFrançois Alcover, Nov 04 2011, after Pari *)


PROG

(PARI) a(n)=sum(k=1, sqrtint(n+1), ceil(k^2/2)1)+sum(k=sqrtint(n+1)+1, sqrtint(2*n 1), nfloor(k^2/2))
(PARI) a(n)=sum(k=1, n, sqrtint(2*k1)sqrtint(k))


CROSSREFS

Cf. A000196, A022554, A103128, A281706.
Column k=2 of A281871.
Sequence in context: A305669 A325364 A133810 * A291453 A185660 A191839
Adjacent sequences: A176612 A176613 A176614 * A176616 A176617 A176618


KEYWORD

easy,nice,nonn


AUTHOR

Franklin T. AdamsWatters, Apr 21 2010


STATUS

approved



