|
%I #18 Sep 01 2019 11:23:37
%S 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,
%T 38,40,42,44,46,49,52,55,57,59,61,63,65,68,71,74,77,80,83,86,89,91,93,
%U 96,99,102,105,108,111,114,117,120,123,127,131,135,138,141,144,147,150
%N 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.
%C Equivalently, number of pairs of integers 0 < i < j <= n such that i + j is a square.
%C Suggested by _R. K. Guy_
%H Alois P. Heinz, <a href="/A176615/b176615.txt">Table of n, a(n) for n = 1..20000</a>
%F 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.
%e For n = 7 the graph contains the 4 edges 1-3, 2-7, 3-6, 4-5.
%p b:= n-> 1+floor(sqrt(2*n-1))-ceil(sqrt(n+1)):
%p a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+b(n)) end:
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jan 30 2017
%t 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 *)
%o (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))
%o (PARI) a(n)=sum(k=1,n,sqrtint(2*k-1)-sqrtint(k))
%Y Cf. A000196, A022554, A103128, A281706.
%Y Column k=2 of A281871.
%K easy,nice,nonn
%O 1,5
%A _Franklin T. Adams-Watters_, Apr 21 2010
|
