login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I

%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) ~ (2sqrt(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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 12:09 EST 2018. Contains 317306 sequences. (Running on oeis4.)