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

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

| cite | improve this answer | |
  • $\begingroup$ 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... $\endgroup$ – cupcake111680 Sep 27 '19 at 21:41
  • $\begingroup$ Lol what a coincidence math.stackexchange.com/questions/3373058/mathematical-series $\endgroup$ – 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.