Voozh

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

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