cp's OEIS Frontend

A015613 a(n) = Sum_{i=1..n} phi(i) * (ceiling(n/i) - floor(n/i)).

%I A015613 #40 Feb 06 2025 12:55:19
%S A015613 0,0,1,2,5,6,11,14,19,22,31,34,45,50,57,64,79,84,101,108,119,128,149,
%T A015613 156,175,186,203,214,241,248,277,292,311,326,349,360,395,412,435,450,
%U A015613 489,500,541,560,583,604,649,664,705,724,755,778,829,846,885,908,943
%N A015613 a(n) = Sum_{i=1..n} phi(i) * (ceiling(n/i) - floor(n/i)).
%C A015613 a(n) is half the number of fractions reduced to lowest terms with numerator and denominator in {2, 3, ..., n}.  a(5) = 5 = (1/2) * |{2/3, 2/5, 3/2, 3/4, 3/5, 4/3, 4/5, 5/2, 5/3, 5/4}|. - _Stefano Spezia_, Aug 11 2019
%H A015613 Alois P. Heinz, <a href="/A015613/b015613.txt">Table of n, a(n) for n = 1..10000</a>
%F A015613 a(n) = sum of phi(e) where e ranges over all nondivisors of n that are between 1 and n. - _Joseph L. Pe_, Oct 24 2002
%F A015613 a(n) = A002088(n) - n.
%F A015613 a(n) = A091369(n) - A000217(n). - _Alois P. Heinz_, Aug 11 2019
%p A015613 a:= proc(n) option remember; `if`(n=0, 0,
%p A015613        numtheory[phi](n)-1+a(n-1))
%p A015613     end:
%p A015613 seq(a(n), n=1..100);  # _Alois P. Heinz_, Aug 11 2019
%t A015613 f[n_] := Module[{s, i}, s = 0; For[i = 1, i < n, i++, If[Mod[n, i] != 0, s = s + EulerPhi[i]]]; s]; Table[f[i], {i, 1, 100}]
%t A015613 Table[Sum[EulerPhi[i](Ceiling[n/i]-Floor[n/i]),{i,n}],{n,60}] (* _Harvey P. Dale_, Feb 06 2025 *)
%o A015613 (Python)
%o A015613 from functools import lru_cache
%o A015613 @lru_cache(maxsize=None)
%o A015613 def A015613(n): # based on second formula in A018805
%o A015613     if n == 0:
%o A015613         return 0
%o A015613     c, j = 0, 2
%o A015613     k1 = n//j
%o A015613     while k1 > 1:
%o A015613         j2 = n//k1 + 1
%o A015613         c += (j2-j)*(2*(A015613(k1)+k1)-1)
%o A015613         j, k1 = j2, n//j2
%o A015613     return (n*(n-3)-c+j)//2 # _Chai Wah Wu_, Mar 25 2021
%Y A015613 Cf. A000005, A000010, A000217, A002088, A049820, A091369.
%K A015613 nonn
%O A015613 1,4
%A A015613 _Joseph L. Pe_, Oct 24 2002
%E A015613 Edited by _Vladeta Jovovic_, Mar 23 2003