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

%I #35 Mar 31 2021 02:57:21

%S 1,3,7,12,20,27,39,50,64,77,97,112,136,155,177,200,232,255,291,318,

%T 350,381,425,456,500,537,581,620,676,713,773,820,872,921,979,1026,

%U 1098,1153,1215,1270,1350,1403,1487,1550,1618,1685,1777,1840,1930,1999,2081,2156

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

%F a(n) = n^2 - A063985(n). - _Enrique PĂ©rez Herrero_, Feb 25 2012

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

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

%o (PARI) a(n) = sum(k=1, n, eulerphi(k)*ceil(n/k)); \\ _Michel Marcus_, Apr 13 2017

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A091369(n):

%o if n == 0:

%o return 0

%o c, j = 0, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

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

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

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

%Y Cf. A063985.

%K nonn,easy

%O 1,2

%A _Jon Perry_, Mar 01 2004

%E More terms from _Robert G. Wilson v_, Mar 02 2004