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

Author

Franklin T. Adams-Watters, Apr 21 2010

Keywords

• easy
• nice
• nonn

Comments

Equivalently, number of pairs of integers 0 < i < j <= n such that i + j is a square.

Suggested by R. K. Guy

Examples

			For n = 7 the graph contains the 4 edges 1-3, 2-7, 3-6, 4-5.
		

Links

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

Crossrefs

Cf. A000196, A022554, A103128, A281706.

Column k=2 of A281871.

Programs

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 *)

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))

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.