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

Author

Randell G Heyman, Aug 02 2018

Keywords

• nonn

Examples

			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.
		

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.

Programs

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 *)

PARI

a(n) = sum(x=1, n, eulerphi(n\x)); \\ Michel Marcus, Aug 02 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).

Extensions

More terms from Michel Marcus, Aug 02 2018