A317625 - OEIS

%I #39 Dec 13 2024 16:43:30

%S 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,

%T 58,68,61,78,60,83,68,80,85,100,74,99,94,110,91,116,90,121,104,116,

%U 127,152,100,131,122,144,137,166,130,161,136,162,171,202,126,171,164,182,163,190

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

%H Robert Israel, <a href="/A317625/b317625.txt">Table of n, a(n) for n = 1..10000</a>

%H Olivier Bordellès, Randell Heyman, and Igor E. Shparlinski, <a href="https://arxiv.org/abs/1808.00188">On a sum involving the Euler function</a>, arXiv:1808.00188 [math.NT], 2018.

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

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

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

%e 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.

%p 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:

%t Array[Sum[EulerPhi[Floor[#/k]], {k, #}] &, 65] (* _Michael De Vlieger_, Aug 02 2018 *)

%o (PARI) a(n) = sum(x=1, n, eulerphi(n\x)); \\ _Michel Marcus_, Aug 02 2018

%K nonn

%O 1,2

%A _Randell G Heyman_, Aug 02 2018

%E More terms from _Michel Marcus_, Aug 02 2018