A015614 - OEIS

%I #72 Mar 15 2022 05:10:22

%S 0,1,3,5,9,11,17,21,27,31,41,45,57,63,71,79,95,101,119,127,139,149,

%T 171,179,199,211,229,241,269,277,307,323,343,359,383,395,431,449,473,

%U 489,529,541,583,603,627,649,695,711,753,773,805,829,881,899,939,963

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

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

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

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

%C 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

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

%H Stanislav Sykora, <a href="/A015614/b015614.txt">Table of n, a(n) for n = 1..10000</a>

%H James J. Sylvester, <a href="https://doi.org/10.1080/14786448308627346">On the number of fractions contained in any Farey series of which the limiting number is given</a>, in: London, Edinburgh and Dublin Philosophical Magazine (5th series) 15 (1883), p. 251.

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

%F a(n) = (A018805(n) - 1)/2. - _Reinhard Zumkeller_, Apr 08 2006

%F For n > 1: A214803(a(n)) = A165900(n-1). - _Reinhard Zumkeller_, Jul 29 2012

%F a(n) = A018805(n) - A002088(n). - _Reinhard Zumkeller_, Jan 21 2013

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

%F a(n) = A000217(n-1) - A185670(n). - _Hossein Mahmoodi_, Jan 20 2022

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

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

%t Table[Sum[EulerPhi[m],{m,1,n}]-1,{n,1,56}] (* _Geoffrey Critzer_, May 16 2014 *)

%o (Haskell)

%o a015614 = (subtract 1) . a002088  -- _Reinhard Zumkeller_, Jul 29 2012

%o (PARI) {a(n) = if( n<1, 0, sum(k=1,n,eulerphi(k), -1))} /* _Michael Somos_, Sep 06 2013 */

%o (GAP) List([1..60],n->Sum([1..n],i->Phi(i)))-1; # _Muniru A Asiru_, Jul 31 2018

%o (Magma) [-1+&+[EulerPhi(i): i in [1..n]]:n in [1..56]]; // _Marius A. Burtea_, Aug 09 2019

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A015614(n): # based on second formula in A018805

%o     if n == 0:

%o         return -1

%o     c, j = 2, 2

%o     k1 = n//j

%o     while k1 > 1:

%o         j2 = n//k1 + 1

%o         c += (j2-j)*(2*A015614(k1)+1)

%o         j, k1 = j2, n//j2

%o     return (n*(n-1)-c+j)//2 # _Chai Wah Wu_, Mar 24 2021

%Y Cf. A000010, A002088, A018805, A185670.

%Y Column k=2 of triangle A186974.

%K nonn

%O 1,3

%A _Olivier Gérard_

%E More terms from _Reinhard Zumkeller_, Apr 08 2006