A015614 a(n) = -1 + Sum_{i=1..n} phi(i).

0, 1, 3, 5, 9, 11, 17, 21, 27, 31, 41, 45, 57, 63, 71, 79, 95, 101, 119, 127, 139, 149, 171, 179, 199, 211, 229, 241, 269, 277, 307, 323, 343, 359, 383, 395, 431, 449, 473, 489, 529, 541, 583, 603, 627, 649, 695, 711, 753, 773, 805, 829, 881, 899, 939, 963

Offset: 1

Author

Olivier Gérard

Keywords

• nonn

Comments

Number of elements in the set {(x,y): 1 <= x < y <= n, 1=gcd(x,y)}. - Michael Somos, Jun 13 1999

Number of fractions in (Haros)-Farey series of order n.

The asymptotic limit for the sequence is a(n) ~ 3*n^2/Pi^2. - Martin Renner, Dec 12 2011

2*a(n) is the number of proper fractions reduced to lowest terms with numerator and denominator less than or equal to n in absolute value. - Stefano Spezia, Aug 09 2019

Examples

			x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 11*x^6 + 17*x^7 + 21*x^8 +27*x^9 + ...
		

References

• Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966, pp. 170-171.

Links

• Stanislav Sykora, Table of n, a(n) for n = 1..10000
• James J. Sylvester, On the number of fractions contained in any Farey series of which the limiting number is given, in: London, Edinburgh and Dublin Philosophical Magazine (5th series) 15 (1883), p. 251.

Crossrefs

Cf. A000010, A002088, A018805, A185670.

Column k=2 of triangle A186974.

Programs

GAP

List([1..60],n->Sum([1..n],i->Phi(i)))-1; # Muniru A Asiru, Jul 31 2018

Haskell

a015614 = (subtract 1) . a002088  -- Reinhard Zumkeller, Jul 29 2012

Magma

[-1+&+[EulerPhi(i): i in [1..n]]:n in [1..56]]; // Marius A. Burtea, Aug 09 2019

Maple

with(numtheory): a:=n->add(phi(i),i=1..n): seq(a(n)-1,n=1..60); # Muniru A Asiru, Jul 31 2018

Mathematica

Table[Sum[EulerPhi[m],{m,1,n}]-1,{n,1,56}] (* Geoffrey Critzer, May 16 2014 *)
Table[Length[FareySequence[n]]-2,{n,60}] (* Harvey P. Dale, Jan 30 2025 *)

PARI

{a(n) = if( n<1, 0, sum(k=1,n,eulerphi(k), -1))} /* Michael Somos, Sep 06 2013 */

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A015614(n): # based on second formula in A018805
    if n == 0:
        return -1
    c, j = 2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A015614(k1)+1)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

Formula

a(n) = -1 + A002088(n).

a(n) = (A018805(n) - 1)/2. - Reinhard Zumkeller, Apr 08 2006

For n > 1: A214803(a(n)) = A165900(n-1). - Reinhard Zumkeller, Jul 29 2012

a(n) = A018805(n) - A002088(n). - Reinhard Zumkeller, Jan 21 2013

G.f.: (1/(1 - x)) * (-x + Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020

a(n) = A000217(n-1) - A185670(n). - Hossein Mahmoodi, Jan 20 2022

Extensions

More terms from Reinhard Zumkeller, Apr 08 2006