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.

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

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 1-3, 2-7, 3-6, 4-5.

Maple

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

Mathematica

a[n_] := Sum[Floor[Sqrt[2k-1]] - Floor[Sqrt[k]], {k, 1, n}]; Table[a[n], {n, 1, 68}] (* Jean-Franç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), n-floor(k^2/2))
(PARI) a(n)=sum(k=1, n, sqrtint(2*k-1)-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. Adams-Watters, Apr 21 2010

Status

approved