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
Keywords
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