Prime powers, patterns similar to $\lbrace 0,1,0,2,0,1,0,3\ldots \rbrace$ and formulas for $\sigma_k(n)$

Question

Some time ago when decomponsing the natural numbers, $\mathbb{N}$, in prime powes I noticed a pattern in their powers. Taking, for example, the numbers $\lbrace 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 \rbrace$ and factorize them, we will get $$\begin{align} 1&=2^0\times 3^0\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 2&=2^1\times 3^0\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\3&=2^0\times 3^1\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 4&=2^2\times 3^0\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 5&=2^0\times 3^0\times 5^1\times 7^0\times 11^0\times 13^0\times\ldots \\ 6&=2^1\times 3^1\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 7&=2^0\times 3^0\times 5^0\times 7^1\times 11^0\times 13^0\times\ldots \\ 8&=2^3\times 3^0\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 9&=2^0\times 3^2\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 10&=2^1\times 3^0\times 5^1\times 7^0\times 11^0\times 13^0\times\ldots \\ 11&=2^0\times 3^0\times 5^0\times 7^0\times 11^1\times 13^0\times\ldots \\ 12&=2^2\times 3^1\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\ 13&=2^0\times 3^0\times 5^0\times 7^0\times 11^0\times 13^1\times\ldots \\ 14&=2^1\times 3^0\times 5^0\times 7^1\times 11^0\times 13^0\times\ldots \\ 15&=2^0\times 3^1\times 5^1\times 7^0\times 11^0\times 13^0\times\ldots \\ 16&=2^4\times 3^0\times 5^0\times 7^0\times 11^0\times 13^0\times\ldots \\\end{align}$$ Now if we look at the powers of $2$ we will notice that they are $$\lbrace f_2(n)\rbrace=\lbrace 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4\rbrace$$ and for the powers of $3$ we have $$\lbrace f_3(n)\rbrace=\lbrace 0,0,1,0,0,1,0,0,2,0,0,1,0,0,1,0\rbrace$$ This, of course, is a well known fact.

Since then I wondered if there was a formula for $f_2(n)$ or $f_3(n)$ or $f_p(n)$, with $p\in \mathbb{P}$. It seemed impossible but I was able to devise the suitable formulas. They are $$\displaystyle\begin{align} f_2(n)=\sum_{r=1}^{\infty}\frac{r}{{2^{r+1}}}\sum_{k=0}^{2^{r+1}-1}\cos\left( \frac{2k\pi(n+2^{r})}{2^{r+1}} \right)\end{align}$$ and for the general case we have $$\displaystyle f_p(n)=\sum_{r=1}^{\infty}\frac{r}{p^{r+1}}\sum_{j=1}^{p-1}\left(\sum_{k=0}^{p^{r+1}-1}\cos\left( \frac{2k\pi(n+(p-j)p^{r})}{p^{r+1}} \right)\right)$$ If one cares to analyse the formula for $f_p(n)$ it can be concluded that it needs not to be restricted to the prime numbers, so that we have $f_m(n), m \in \mathbb{N}$ and similar patterns for $\lbrace f_m(n)\rbrace$ will result. Now, the wonderfull thing is that we can express the arithmetical divisor functions $\sigma_k(n)$ in terms of $f_m(n)$ as follows $$\displaystyle \sigma_a(n)=1+\sum_{m=2}^{\infty}\sum_{r=1}^{\infty}\frac{m^{a}}{m^{r+1}}\sum_{j=1}^{m-1}\left(\sum_{k=0}^{m^{r+1}-1}\cos\left( \frac{2k\pi(n+(m-j)m^{r})}{m^{r+1}} \right)\right)$$ And, if we consider the divisor summatory function, $D(n)$, as $$D(n)=\sum_{m \leq n}d(m)$$ with $$d(n)=\sigma_{0}(n)=\sum_{d|n}1$$ we can express $D(n)$ as $$D(n)=\sum_{m=2}^{\infty}\sum_{r=1}^{\infty}\frac{r}{m^{r+1}}\sum_{j=1}^{m-1}\left(\sum_{k=0}^{m^{r+1}-1}\cos\left( \frac{2k\pi(2^{n}+(m-j)m^{r})}{m^{r+1}} \right)\right)$$ Now, we know that, $d(n)$ and $D(n)$ are related to the Riemann zeta-function by $$\zeta^{2}(z)=\sum_{n=1}^{\infty}\frac{d(n)}{n^{z}}$$ and $$\zeta^{2}(z)=z\int_{1}^{\infty}\frac{D(x)}{x^{z+1}}dx$$

Now, my questions

• What can we say about the convergence of $f_m(z)$, $\sigma_a(z)$ and $D(z)$ with $z \in \mathbb{C}$? We can see that they converge for $z \in \mathbb{N}$.
• I think that $\sigma_a(z)$ and $D(z)$ are only curiosities and aren't interesting in the context of the Riemann zeta-function because they are hard to compute. What do you think?
• Are formulas $f_m(z)$, $\sigma_a(z)$ and $D(z)$ original. I think they are. I'd like to know if anyone has found something like this before. I've posted this as an answer to this post sometime ago.
• Finally, is this intereting enough to publish somewhere? I'm just an amateur...

To conclude I'd like to apologise for presenting all this formulas without showing how I got them but you can consider this previous post of mine and the question Greatest power of two dividing an integer, Difficult Infinite Sum and On the 61-st, the 62-nd, and the 63-rd Smarandache's problem page 38.

And now a challenge, can you present a formula for the characteristic function of the prime numbers?

EDIT: I'm answering my challenge and leaving another. Considering that the characteristic function of the primes, $u(n)$, is given by

$$ \begin{equation} u(n)=\begin{cases} &1\;\;\;\text{ if } n \in \mathbb{P} \\ &\\ &\\ &0\;\;\;\text{ if } n \notin \mathbb{P} \end{cases} \end{equation} $$

I have found that $u(n)$ is given by the following formula

$$ \begin{equation} u(n)=\prod_{m=2}^{\infty}\;\;\prod _{r=1}^{\infty} \left\{1-\frac{1}{m^{r+1}} \sum _{j=1}^{m-1}\;\;\;\sum _{k=0}^{m^{r+1}-1} \cos\left(2 k \pi \cdot\frac{n-m+(m-j) m^r }{m^{r+1}}\right)\right\} \end{equation} $$ Now, in the same spirit, what is formula for the prime counting function, $\pi(x)$?

Answer 1

You should take a look at this math stack exchange post, and the answer there, as it applies directly here.

For a formula for $\pi (x)$ you can take a look at this wikipedia page.

Such elementary formulas tend to encode some complex algorithm which would check the result, and evaluate the function. Usually they are not of too much interest because:

(1) Any analysis is very difficult, and people do not tend to be able to use such formulas to prove theorems regarding the primes or $\sigma(n)$ (2) Evaluating the series takes longer then other known computational methods for $\sigma(n)$ or $\pi(x)$. (3) They do not tell us about the nature of the functions at hand, as they simply encode an algorithm which calculates those functions. Studying the algorithm would be more fruitful then the series for a greater understanding. (4) There seems to be a lot of these series.

For example, the formula for $\pi(x)$,

$$\pi(k) = k - 1 + \sum_{j=1}^k \left\lfloor {2 \over j} \left(1 + \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right\rfloor$$

is an encoding of the Sieve of Eratosthenes, which is more interesting and easier to understand when just looked at by itself. Indeed, the idea behind the sieve can be explained to a highschool student, but trying to understand the formula above without having seen it become could intimidate many strong undergraduates or graduate students.

We also have the formula for the $n^{th}$ prime number:

$$p_n = 1 + \sum_{k=1}^{2(\lfloor n \ln(n)\rfloor+1)} \left(1 - \left\lfloor{\frac{1}{n}\left(k - 1 + \sum_{j=1}^k \left\lfloor {2 \over j} \left(1 + \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right\rfloor\right)} \right\rfloor\right)$$

Having said all of this, I still think it is quite interesting that you managed to discover these formulas. I would encourage you to write it up, and explain the ideas behind why they are correct. (Also perhaps have some computations verifying the formulas to comfort the reader.) Someone might have been looking for exactly these formulas, and it helps others to know that they even exists. Also, perhaps the ideas that go into your formulas are deeper then what I described above.

Answer 2

These formulas are convoluted and what looks to me as probably useless representations of the p-adic order of an integer. All you seem to have done is taken advantage of the fact that: $$1_{p^j\mid n}=\frac{1}{p^j}\sum_{t=0}^{p^j-1}e^{2\pi i t\frac{n}{p^j}}$$ And then re-wrote it it without the imaginary part of each root of unity, so you got a sum of cosines, and then summed over the powers in $j$, so that it counted the multiplitices $p$ of a given integer, which you gave as a complex double sum. In addition I doubt this is of any use in a computational context, since: $$v_p(n)=\gcd(p^{\lfloor \log_p(n) \rfloor},n)$$Which can be calculated very fast using the euclidean algorithm.

Also, just to show you that it is not hard to obtain results about this function: $$\frac{\zeta(s)}{p^s-1}=\sum_{n=1}^\infty\frac{v_p(n)}{n^s}=\sum_{n=1}^\infty\frac{f_p(n)}{n^s}$$ $$\sum_{k=1}^n v_p(k)=\sum_{k=1}^nf_p(k)=\sum_{j=1}^{\lfloor \log_p(n) \rfloor}\lfloor \frac{n}{p^j} \rfloor$$ $$\sum_{k=1}^np^{v_p(k)}=\sum_{k=1}^np^{f_p(k)}=n+(1-\frac{1}{p})\sum_{j=1}^{\lfloor \log_p(n) \rfloor}p^j\lfloor \frac{n}{p^j} \rfloor$$ And in general if we define for a fixed prime $p$ and an arbitrary function $g$ the function $\delta_p$: $$ \delta_p(k) \stackrel{}{=} \begin{cases} g(j)-g(j-1) & \text{if } k = p^j \text{ with } j\ge 1, \\ g(0) & \text{if } k=1 \\ 0 & \text{otherwise} \end{cases} $$

So that $\sum_{d\mid k}\delta_p(d)=g(v_p(k))=g(f_p(k))$

Then we have for arbitrary functions $g$ and $h$:

$$\sum_{k=1}^ng(f_p(k))h(k)=\sum_{k=1}^n(\sum_{d\mid k}\delta_p(d))h(k)=\sum_{k=1}^n\delta_p(k)\sum_{m=1}^{\lfloor n/k\rfloor}h(mk)$$

$$=g(0)\sum_{m=1}^nh(m)+\sum_{j=1}^{\lfloor \log_p(n) \rfloor}(g(j)-g(j-1))\sum_{m=1}^{\lfloor n/p^j \rfloor}h(mp^j)$$ Where the upper index $n$ in this sum has been simplified to a sum with an upper index of $O(\ln(n))$ thus allowing any sort of sum evolving the p-adic order or as you are refering to it with the function $f_p$ to be calculatetable in an exponentially faster time then the sums you use just to represent one value of $f_p$.

So I wouldn't say your formulas are original, nor would I say they are very practical. Though for whatever my opinion is worth (probably not much) I would say that despite this, it is still great you are exploring and finding new things that interest you.