Intereting Posts

Mathematics – The big picture
Limitations of approximating $\sin(x) = x$
Finding UMVUE of $p^s$ in Bernoulli distribution
Differential Equations with Deviating Argument
Intersection of ellipse with circle
Find the breaking time in IVP for classical Burgers equation
Ring without distributive law?
Integration operation, and its relation to differentials
Is following system of nonlinear ODEs recognized?
Inversion of matrices is a diffeomorphism.
To estimate $\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$
Prove or disprove that the given expression is “always” positive
Cyclic group order 15
Proving a certain inequality
Is Proof by Resolution really needed here?

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

- Prove that $x^2+1$ cannot be a perfect square for any positive integer x?
- A series related to $\zeta (3)$.
- Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $.
- Generalizing values which Euler's-totient function does not take
- Can you derive a formula for the semiprime counting function from the prime number theorem?
- First 10-digit prime in consecutive digits of e

- 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)$?

- Divisibility of integers
- Two problems about Squarefree numbers
- Is $7$ the only prime followed by a cube?
- Special matrices with determinant 0
- General formula to obtain triangular-square numbers
- What is the sum of the squares of the differences of consecutive element of a Farey Sequence
- Prime Zeta Function proof help: Why are these expressions not equal?
- A multiplication algorithm found in a book by Paul Erdős: how does it work?
- Find $a$ such that $(x+a)(x+1991)+1=(x+b)(x+c)$ with $a,b,c\in\Bbb Z$
- The effect of roots of Dirichlet's $\beta$ function condenses to $\frac12\left(1+ie^{i2\pi\frac{p}4}\right)$

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.

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.

- Computing the variance of hypergeometric distribution using indicator functions
- Strictly diagonally dominant matrices are non singular
- Why are duals in a rigid/autonomous category unique up to unique isomorphism?
- Bounds for the size of a circle with a fixed number of integer points
- Produce a sequence $(g_n):g_n(x)\ge 0$ and $\lim g_n(x)\neq 0$ but $\int_{0}^{1} g_n\to 0$
- Ulam spiral: Is there an “unusual amount of clumping” in prime-rich quadratic polynomials?
- Repeated squaring method
- Example of a Markov chain transition matrix that is not diagonalizable?
- Counting arrays with gcd 1
- Proofs about continuity and convergence in topological spaces
- Simplifying an integral by changing the order of integration
- Is every nonzero integer the discriminant of some algebraic number field?
- Subjects studied in number theory
- Are compact subsets of metric spaces closed and bounded?
- Greatest prime divisor of consecutive integers