# Prime sum identity

Let $\Lambda(k)$ denote the von Mangoldt function: $$\Lambda(k) \stackrel{\text{def}}{=} \begin{cases} 0 & \text{if  k  is not a prime power}, \\ \ln(p) & \text{if  k = p^{j} }. \end{cases}$$ Also, let $\lfloor x \rfloor$ be the floor function.

Can anyone prove any of the following identities: $$\sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \ln(3k+1) = \sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \Lambda(3k + 1) \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor + \sum_{k=0}^{\left\lfloor (n - 2)/3 \right\rfloor} \Lambda(3k + 2) \left\lfloor \frac{n}{9k + 6} + \frac{1}{3} \right\rfloor.$$ $$\sum_{k=0}^{\left\lfloor (n - 3)/4 \right\rfloor} \ln(4k+1)=\sum_{k=0}^{\left\lfloor (n - 1)/4 \right\rfloor} \Lambda(4k + 1) \left\lfloor \frac{n}{16k + 4} + \frac{1}{4} \right\rfloor + \sum_{k=0}^{\left\lfloor (n - 3)/4 \right\rfloor} \Lambda(4k + 3) \left\lfloor \frac{n}{16k +12} + \frac{3}{4} \right\rfloor.$$ $$\sum_{k=1}^{n} \ln(k)= \sum_{k=1}^{n} \Lambda(k) \left\lfloor \frac{n}{k} \right\rfloor$$ The latter ones obvious, I just thought id post it for comparison.

-
It might help if you supplied a bit of background. Where does this come from and why do you expect it to be true? – Tobias Kildetoft Dec 30 '12 at 4:22
@Ethan This question is actually suitable for induction (apart from that, it's not nice to laugh at people's attempts). Those identities and their generalizations are proved by the simple identity $\ln m = \sum_{d|m} \Lambda(d)$ (which is often the definition of $\Lambda$) and interchanging the order of summation. The curios floor functions count multiples of some $x$ less than some $y$ that lie in a certain arithmetic progression. – Ofir Dec 30 '12 at 10:51
@Ethan "being proved by simple methods like induction" Induction is by no means a trivial method. One of the most important objects in mathematics, namely, the set of natural numbers, is defined inductively. Any statement which needs to be proved for all $n$ needs to rely on induction at some point. – user17762 Dec 30 '12 at 22:34
@Ethan It is not polite to change the question so much after someone went to a fair bit of trouble to answer. – Erick Wong Dec 31 '12 at 2:24
@Ethan - I agree with Erick. You changed the question after I answered, without giving an explanation. So my answer has been accepted without being a suitable answer for the current question. If you had a new question, you should have opened a new question or asked me in a comment to my answer. What would have happened if someone gave an answer to your new question? You would've accepted his answer instead of mine, as required. Anyway, I answered your new question because the same method applies. – Ofir Dec 31 '12 at 8:36

## 2 Answers

EDIT: I'll prove the single identity you now wrote, for completeness sake. As in my original answer, note that $\Lambda * 1 = \log n$, where $*$ denotes convolution.

In general, if $f,g$ are functions from $\mathbb{N}$ to $\mathbb{C}$ and $F(x)=\sum_{n\le x}f(x), G(x) = \sum_{n\le x} g(x)$ are the corresponding summatory functions, we have the following identity: $$\sum_{1\le n \le x} (f*g)(n) = \sum_{1\le n \le x} \sum_{d|n} f(d)g(n/d) = \sum_{1 \le d \le x} f(d) (\sum_{d|n, 1\le n \le x}g(n/d))=$$ The number of multiples of d between $1$ and $x$ is $\lfloor \frac{x}{d} \rfloor$, thus: $$\sum_{1 \le d \le x} f(d) (\sum_{1 \le i \le \lfloor \frac{x}{d} \rfloor} g(i))=\sum_{1 \le i \le x}f(i)G(\frac{x}{i})$$ Similarly, $$\sum_{1\le n \le x} (f*g)(x) =\sum_{1 \le i \le x}g(i)F(\frac{x}{i})$$

If you've heard about "Dirichlet's Hyberbola Method", it is just a refinement of this which states: $$\sum_{1\le n \le x} (f*g)(n) =\sum_{1 \le i \le V}f(i)G(\frac{x}{i}) + \sum_{1 \le j \le U}g(j)F(\frac{x}{j}) - F(V)G(U)$$ Where U,V are positive reals such that $UV=x$. The proof is similar and has a geometric interpretation - hence the name. If you take $U=x,V=1$ or $U=1,V=x$, you get the original identities easily.

Back to your specific identity - just plug $f=\Lambda, g=1$ (i.e. $g$ is identically 1), and you'll find: $$\sum_{1\le n \le x} (\Lambda*1)(x) =\sum_{1 \le i \le x}f(i)G(\frac{x}{i})$$ $$=\sum_{1 \le i \le x} f(i)\lfloor \frac{x}{i} \rfloor =\sum_{1 \le i \le x}\lfloor \frac{x}{i} \rfloor \Lambda(x)$$

Remark: if you choose $f=\mu, g=1$, you find $1=\sum_{1 \le i \le x} \lfloor \frac{x}{i} \rfloor \mu(x)$ for $x\ge 1$, since $\mu * 1 = \delta_{n,1}$. This is another famous identity. Challenge - use this to prove $|\sum_{n=1}^{x} \frac{\mu(n)}{n}| \le 1$.

(Answer to original question - might contain some calculation mistake)

I'll elaborate on my partial answer from the comments. First, we need to agree that $\ln m = \sum_{d|m} \Lambda(d)$. The simplest way to prove it is to use the formula for $\Lambda$ and just plug it in. This identity is very basic, and is fruitful in analytic number theory - it allows one to compute certain interesting sums, such as $\sum_{m \le n} \sum_{d|m} \Lambda(d) = \ln n! \sim n \ln n$. Another way to prove it is to use Möbius Inversion.

Anyway, consider the first sum: $$\sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \ln(3k+1) = \sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \Lambda(3k + 1) \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor + \sum_{k=0}^{\left\lfloor (n - 2)/3 \right\rfloor} \Lambda(3k + 2) \left\lfloor \frac{n}{9k + 6} + \frac{1}{3} \right\rfloor$$

We'll use the identity I mentioned: $$\sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \ln(3k+1)= \sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \sum_{d | 3k+1} \Lambda(d)=$$ $$\sum_{d \le 3 \left\lfloor (n - 1)/3 \right\rfloor + 1} \Lambda(d) \sum_{k=0, d|3k+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1$$

Note that if $3|d$ then it appears with weight equal to zero, since $3k+1$ is never divisible by $3$. Thus we can divide the $d$'s into 2 types - $3k+1$ and $3k+2$:

$$\sum_{3k+1 \le 3\left\lfloor (n - 1)/3 \right\rfloor +1} \Lambda(3k+1) (\sum_{i=0, 3k+1|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1 )+ \sum_{3k +2 \le 3\left\lfloor (n - 1)/3 \right\rfloor + 1} \Lambda(3k+2) (\sum_{i=0, 3k+2|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1)=$$ $$\sum_{k \le \left\lfloor (n - 1)/3 \right\rfloor} \Lambda(3k+1) (\sum_{i=0, 3k+1|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1 )+ \sum_{k \le \left\lfloor (n - 1)/3 \right\rfloor - 1} \Lambda(3k+2) (\sum_{i=0, 3k+2|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1)$$ (Note that I changed the names of some of the variables)

The next logical step is to prove $\sum_{i=0, 3k+1|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1 = \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor$. There's no fun in it, but I'll do it :) Note that if $3k+1 | 3i+1$ then $3i+1 = (3k+1)(3r+1)$ for some $r$. We're actually counting those $r$'s. $r$ is non-negative and $(3k+1)(3r+1) \le 3\left\lfloor (n - 1)/3 \right\rfloor+1$, i.e. $0 \le r \le \frac{1}{3} (\frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{3k+1} - 1)$. Thus it remains to show: $$1 + \left\lfloor \frac{1}{3} (\frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{3k+1} - 1) \right\rfloor= \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor$$ The LHS simplifies a little - $$\left\lfloor \frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{9k+3} - \frac{1}{3} + 1 \right\rfloor = \left\lfloor \frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{9k+3} + \frac{2}{3} \right\rfloor = \left\lfloor \frac{n}{9k+3} + \frac{2}{3} - \frac{\{\frac{n-1}{3} \}}{3k+1} \right\rfloor$$ And indeed $\left\lfloor \frac{n}{9k+3} + \frac{2}{3} - \frac{\{\frac{n-1}{3} \}}{3k+1} \right\rfloor = \left\lfloor \frac{n}{9k+3} + \frac{2}{3} \right\rfloor$! For $n \equiv 1 \mod 3$, this is immediate. In the other cases, this is also true, since otherwise $\frac{n}{9k+3}$ is really close to $\frac{1}{3}$ from above (in the sense that it's $\frac{3\text{ or }6}{9k+3}=\frac{3\{\frac{n-1}{3} \}}{9k+3}$ away), which can't happen since $k \le \left\lfloor (n - 1)/3 \right\rfloor$.

I am a bit lying - if $k \le \frac{n-7}{3}$, then $\frac{n}{9k+3}-\frac{1}{3} \ge \frac{3k+7 - 3k-1}{9k+3}=\frac{6}{9k+3} \ge \frac{3\{\frac{n-1}{3}\}}{9k+3}$, as we wanted. But I am not sure about $\frac{n-6}{3} \le k \le \lfloor \frac{n-1}{3} \rfloor$, maybe I did some calculation mistake.

The other half of the sum is similar, and so are the rest of the identities - simply use the relation between $\ln n$ and $\Lambda(d)$, and count numbers $i$ that satisfy: $0\le i \le t, d|ai+b$.

-

A perhaps simpler proof, using the $p$-adic expansion of $n!$:

$$\log(n!)=\sum_{p \text{ prime}}\log(p)\left(\left \lfloor \frac{n}{p} \right \rfloor+\left \lfloor \frac{n}{p^2} \right \rfloor+...\right)=\sum_{k=1}^n \Lambda(k)\left \lfloor \frac{n}{k} \right \rfloor.$$

-