Summation involving Euler's totient function 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$.
 A: Too long for a comment, but not a complete answer. Note that
\begin{align*}
\sum_{i = 1} ^ n \bigg\lfloor \frac{n}{i} \bigg\rfloor \phi(ip) (-1) ^ i
&= \sum_{i = 1} ^ n \sum_{\substack{1\le k\le n \\ i\mid k}} 1 \cdot \phi(ip) (-1) ^ i \\
&= - \phi(p) \sum_{k = 1} ^ n \sum_{i\mid k} \frac{\phi(ip)}{\phi(p)} (-1)^{i-1}.
\end{align*}
The function $\frac{\phi(ip)}{\phi(p)} (-1)^{i-1}$ is a multiplicative function of $i$, and therefore the inner sum, call it $f(k)$, is a multiplicative function of $k$ whose values on prime powers $q^j$ can be written down exactly: if $q\notin\{p,2\}$ then $f(q^j) = q^j$, while $f(p^j) = \sigma(p^j)$ (the sum-of-divisors function) and $f(2^j) = 2-2^j$. (If $p=2$ then these last two values must be replaced by $f(2^j) = 2-\sigma(2^j)$.)
This won't give an exact formula (which is probably too ambitious) but it will show that the sum is quite close to $-\phi(p)\sum_{1\le k\le n} k$, probably asymptotic to that times some close-to-$1$ constant depending on $p$.
A: 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.)
