A091369 a(n) = Sum_{i=1..n} phi(i)*ceiling(n/i).

1, 3, 7, 12, 20, 27, 39, 50, 64, 77, 97, 112, 136, 155, 177, 200, 232, 255, 291, 318, 350, 381, 425, 456, 500, 537, 581, 620, 676, 713, 773, 820, 872, 921, 979, 1026, 1098, 1153, 1215, 1270, 1350, 1403, 1487, 1550, 1618, 1685, 1777, 1840, 1930, 1999, 2081, 2156

Offset: 1

Author

Jon Perry, Mar 01 2004

Keywords

• nonn
• easy

Crossrefs

Cf. A063985.

Programs

Maple

A091369:=n->add(numtheory[phi](i)*ceil(n/i), i=1..n): seq(A091369(n), n=1..100); # Wesley Ivan Hurt, Apr 13 2017

Mathematica

A091369[n_] := Sum[EulerPhi[i]*Ceiling[n/i], {i, n}] (* Robert G. Wilson v, Mar 02 2004 *)

PARI

a(n) = sum(k=1, n, eulerphi(k)*ceil(n/k)); \\ Michel Marcus, Apr 13 2017

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A091369(n):
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A091369(k1)-(k1*(k1-1)+1))
        j, k1 = j2, n//j2
    return n*(n-1)-(c-j)//2 # Chai Wah Wu, Mar 29 2021

Formula

a(n) = n^2 - A063985(n). - Enrique Pérez Herrero, Feb 25 2012

Extensions

More terms from Robert G. Wilson v, Mar 02 2004