Does the following sum have a closed-form expression? I've tried an Inclusion-Exclusion interpretation, to no avail:


$f(n, p) = \sum\_{i = 1} ^ n \lfloor \frac{n}{i} \rfloor \phi(p i) (-1) ^ i$


($p$ is a prime number.)


Interesting observation: for $p > n$, $f(n, p) / (p - 1)$ is independent of $p$.



Summation involving Euler's totient function
A fast algorithm for calculating the expression:


We first try to remove the $(-1)^i$ part.


Let $g(n, m)$ be the sum $\sum\_{i = 1} ^ n \lfloor \frac{n}{i} \rfloor \phi(m i)$. Then it is clear that $f(n, p) = g(n, p) - 2 g(\lfloor \frac{n}{2} \rfloor, 2p)$.


Therefore we are reduced to calculating $g(n, p)$ and $g(n, 2p)$.


If $p = 2$, then we have $g(n, 2p) = 2g(n, p)$; otherwise, we have $g(n, 2p) = g(n, p) + g(\lfloor \frac{n}{2} \rfloor, 2p)$. Thus up to a factor of $\log(n)$, we are reduced to calculating $g(n, p)$.


Similarly, since $g(n, p) = (p - 1) g(n, 1) + g(\lfloor \frac{n}{p} \rfloor, p)$, again up to a factor of $\log(n)$, we are reduced to calculating $g(n, 1)$, which we will now simply call $g(n)$.


We have:


\begin{eqnarray\*}
g(n) &=& \sum\_{i = 1} ^ n \lfloor \frac{n}{i} \rfloor \phi(i)\\
&=& \sum\_{i = 1}^n\sum\_{j=1\\i\mid j}^n \phi(i)\\
&=& \sum\_{j = 1}^n \sum\_{i \mid j} \phi(i)\\
&=& \sum\_{j = 1}^n j\\
&=& \frac{n(n + 1)}{2}.
\end{eqnarray\*}


(By the way: just in case this comes from some math-programming puzzle, it would be better that you link the original problem; otherwise ignore this sentence.)


