login
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
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
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
Column k=2 of A281871.
Sequence in context: A305669 A325364 A133810 * A291453 A185660 A191839
KEYWORD
easy,nice,nonn
AUTHOR
STATUS
approved