login
A317625
a(n) = Sum_{k=1..n} phi(floor(n/k)) where phi is the Euler totient function.
4
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
Olivier Bordellès, Randell Heyman, 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
KEYWORD
nonn
AUTHOR
Randell G Heyman, Aug 02 2018
EXTENSIONS
More terms from Michel Marcus, Aug 02 2018
STATUS
approved