Summation involving Euler's totient function

Question

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$.

Answer 1

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.)

Answer 2

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$.