A317625 a(n) = Sum_{k=1..n} phi(floor(n/k)) where phi is the Euler totient function.

1, 2, 4, 5, 8, 8, 13, 12, 16, 17, 24, 18, 27, 26, 32, 31, 40, 32, 45, 36, 46, 51, 64, 42, 57, 58, 68, 61, 78, 60, 83, 68, 80, 85, 100, 74, 99, 94, 110, 91, 116, 90, 121, 104, 116, 127, 152, 100, 131, 122, 144, 137, 166, 130, 161, 136, 162, 171, 202, 126, 171, 164, 182, 163, 190

Offset

1,2

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Olivier Bordellès, Randell Heyman, and Igor E. Shparlinski, On a sum involving the Euler function, arXiv:1808.00188 [math.NT], 2018.

Formula

a(n) <= (1/2)*(1 + 1/zeta(2))*n*log(n) + 4*n + sqrt(n)*log(n)/4 + sqrt(n), uniformly for n >= 3.

a(n) >= ((2629/4009)+o(1))*n*log(n)/zeta(2) as n approaches infinity.

Cautious conjecture: a(n) ~ n*log(n)/zeta(2).

Example

a(4) = phi(floor(4/1))+phi(floor(4/2))+phi(floor(4/3))+phi(floor(4/4)) = phi(4)+phi(2)+phi(1)+phi(1) = 2+1+1+1 = 5.

Maple

with(numtheory): S:=0: for x to 30 do: for m to x do: S := S+phi(trunc(x/m)) end do; print(x, S); S := 0:end do:

Mathematica

Array[Sum[EulerPhi[Floor[#/k]], {k, #}] &, 65] (* Michael De Vlieger, Aug 02 2018 *)

Prog

(PARI) a(n) = sum(x=1, n, eulerphi(n\x)); \\ Michel Marcus, Aug 02 2018

Crossrefs

Sequence in context: A061884 A286002 A029935 * A308447 A350506 A123291

Adjacent sequences: A317622 A317623 A317624 * A317626 A317627 A317628

Keyword

nonn

Author

Randell G Heyman, Aug 02 2018

Extensions

More terms from Michel Marcus, Aug 02 2018

Status

approved