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

0, 0, 1, 2, 5, 6, 11, 14, 19, 22, 31, 34, 45, 50, 57, 64, 79, 84, 101, 108, 119, 128, 149, 156, 175, 186, 203, 214, 241, 248, 277, 292, 311, 326, 349, 360, 395, 412, 435, 450, 489, 500, 541, 560, 583, 604, 649, 664, 705, 724, 755, 778, 829, 846, 885, 908, 943

Offset: 1

Author

Joseph L. Pe, Oct 24 2002

Keywords

• nonn

Comments

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A000010, A000217, A002088, A049820, A091369.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 0,
       numtheory[phi](n)-1+a(n-1))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 11 2019

Mathematica

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}]
Table[Sum[EulerPhi[i](Ceiling[n/i]-Floor[n/i]),{i,n}],{n,60}] (* Harvey P. Dale, Feb 06 2025 *)

Python

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

Formula

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

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

a(n) = A091369(n) - A000217(n). - Alois P. Heinz, Aug 11 2019

Extensions

Edited by Vladeta Jovovic, Mar 23 2003