The On-Line Encyclopedia of Integer Sequences (OEIS)

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A046657 revision #33

A046657

a(n) = A002088(n)/2.

1, 2, 3, 5, 6, 9, 11, 14, 16, 21, 23, 29, 32, 36, 40, 48, 51, 60, 64, 70, 75, 86, 90, 100, 106, 115, 121, 135, 139, 154, 162, 172, 180, 192, 198, 216, 225, 237, 245, 265, 271, 292, 302, 314, 325, 348, 356, 377, 387, 403, 415, 441, 450, 470, 482

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,2

COMMENTS

a(n) = |{(x,y) : 1 <= x <= y <= n, x + y <= n, 1 = gcd(x,y)}| = |{(x,y) : 1 <= x <= y <= n, x + y > n, 1 = gcd(x,y)}|. - Steve Butler, Mar 31 2006

Brousseau proved that if the starting numbers of a generalized Fibonacci sequence are <= n (for n > 1) then the number of such sequences with relatively prime successive terms is a(n). - Amiram Eldar, Mar 31 2017

LINKS

Giovanni Resta, Table of n, a(n) for n = 2..10000

Alfred Brousseau, A Note on the Number of Fibonacci Sequences, The Fibonacci Quarterly, Vol. 10, No. 6 (1972), pp. 657-658.

FORMULA

a(n) = 1/2 + Sum_{i<j<=n, gcd(i, j) = 1} i/j. - Joseph Wheat, Feb 22 2018

MAPLE

a:=n->sum(numtheory[phi](k), k=1..n): seq(a(n)/2, n=2..60); # Muniru A Asiru, Mar 05 2018

MATHEMATICA

Rest@ Accumulate[EulerPhi@ Range@ 56]/2 (* Michael De Vlieger, Apr 02 2017 *)

PROG

(PARI) a(n) = sum(k=1, n, eulerphi(k))/2; \\ Michel Marcus, Apr 01 2017

(GAP) List([2..60], n->Sum([1..n], k->Phi(k)/2)); # Muniru A Asiru, Mar 05 2018