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

• Do you need closed-form expression exactly? It will be easyer to prove asymptotic formula for this sum. – Alexey Ustinov Sep 27 '19 at 3:59
• @AlexeyUstinov Yes, a closed-form expression is preferred. – cupcake111680 Sep 27 '19 at 4:09
• The observation follows because then p and i are coprime and then we have $\phi(pii)=\phi(p)\phi(i)$ – user35593 Sep 27 '19 at 5:50
• @user35593 Correct -- but how do we get a closed form for all $n$, $p$? – cupcake111680 Sep 27 '19 at 6:01
• Do you need a closed-form expression, or just a sufficiently fast algorithm to evaluate the sum (e.g. for some math-programming puzzle)? – WhatsUp Sep 27 '19 at 16:09

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

• I was playing around with different summations involving the totient function, actually starting with the $g(n)$ one you mention, to see what they would yield. (I'm fascinated by the totient and mobius functions.) Your solution by the way is very elegant - thank you. I'm still curious though, if my above sum has a simple inclusion-exclusion/combinatorial interpretation... – cupcake111680 Sep 27 '19 at 21:41
• Lol what a coincidence math.stackexchange.com/questions/3373058/mathematical-series – WhatsUp Sep 28 '19 at 13:52

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