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

Cf. A000196, A022554, A103128, A281706.

Column k=2 of A281871.

Sequence in context: A050741 A285710 A133810 * A291453 A185660 A191839

Adjacent sequences:  A176612 A176613 A176614 * A176616 A176617 A176618

KEYWORD

easy,nice,nonn

AUTHOR

Franklin T. Adams-Watters, Apr 21 2010

STATUS

approved

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 October 17 16:22 EDT 2017. Contains 293471 sequences.