Why does $\sum\omega\left(2n-p\right)=\sum\pi_{p,b}\left(2n-p\right)$?

68 Views Asked by At

Why does: $$ \sum_{_{3\leq p\leq2n-3}}\omega\left(2n-p\right)=\sum_{_{3\leq p\leq2n-3}}\pi_{p,b}\left(2n-p\right) $$

where:

$ p\text{ is prime} $,
$ \omega\left(x\right)\text{ counts each distinct prime factor of } x $,
$ \pi_{p,b}\left(x\right)\text{ denotes the number of odd primes of the form }pk+b\text{ less than or equal to }x $,
and $ b=\left(2n-p\right)\mod p $

The two sums are equal, and the first few value, from $n=3$ is: $$ 1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 10, 10, 8, 11, 12, 11, 14, 14, 13, 16, 17, 15, 18, 20, 16, 20, 22, 17, 24 \ldots $$

Visually, I can see why the two sums are equal. In the example below, $n=54$, if we look in the right column, the number of times each prime $p$ appears is equal to the number of distinct factors of $2n-p$ in the second column.

What I need is a mathematical explanation, something I can use in a proof to explain why the sums are equal for all $n$?

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

I'll use the Iverson's Bracket notation.

Observe that $\omega(n) = \sum\limits_{p\le n} [p\mid n]$. If $n$ is odd, we have $\omega(n) =\sum\limits_{3\le p\le n} [p\mid n]$.

Also, with your (non-standard) definition, we have $\pi_{m,a}(x) = \sum\limits_{3\le p\le x}[p \equiv a \pmod m]$.

Then \begin{align} \sum_{3\le p \le 2n-3}\omega(2n-p) &= \sum_{3\le p \le 2n-3}\;\sum_{3\le q\le 2n-p} [q \mid2n-p]\\ &= \sum_{3\le p \le 2n-3}\;\sum_{3\le q\le 2n-3} [q \mid2n-p]\\ &=\sum_{3\le q \le 2n-3}\;\sum_{3\le p\le 2n-3} [q \mid2n-p]\\ &=\sum_{3\le q \le 2n-3}\;\sum_{3\le p\le 2n-q} [q \mid2n-p]\\ &=\sum_{3\le q \le 2n-3}\;\sum_{3\le p\le 2n-q} [p \equiv 2n \pmod q]\\ &=\sum_{3\le q \le 2n-3}\pi_{q,2n}(2n-q)\\ &=\sum_{3\le q \le 2n-3}\pi_{q,b}(2n-q)\\ \end{align}

I think the exclusion of $2$ just complicate things. Probably you'll get a nicer formula using the standard definition of $\pi_{m,a}$ and not excluding $p=2$ in the sums.