Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
To get italics, use *<text>* or _<text>_; to get bold, use **<text>**. Better than mathitalic. –  Arturo Magidin Dec 29 '10 at 19:35
    
There was an error in the first and second formulas, now they are correct. –  Neves Jan 5 '11 at 9:25
    
$\lbrace f_{2}(n)\rbrace$ is related to OEIS sequence A007814 and $\lbrace f_{2}(2n) \rbrace$ is related to A00151. –  Neves Jan 6 '11 at 14:50
    
Maybe you should ask the same question at MO too. –  minasteris Jan 18 '11 at 12:48
    
By the way, you perhaps mean the prime exponents and not the prime powers. –  al-Hwarizmi Jun 6 '13 at 7:26
show 3 more comments

2 Answers

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.

share|improve this answer
    
Thanks for your answer, I'm aware that those formulas (in my question) have no value for calculation, but I think that formally they are special because they involve roots of unity and Gaussian sums and it is in that spirit that I'm asking for $\pi(x)$, the answer should contain infinite sums and somehow Gaussian sums, that would be a nice answer. –  Neves Oct 26 '11 at 10:40
1  
@ericnaslund The expressions he gives come from the fact $$1_{p^j\mid n}=\frac{1}{p^j}\sum_{t=0}^{p^j-1}cos(2\pi\ t\frac{n}{p^j})$$, he has simply extracted the real part of each root of unity, to obtain a sum of cosines, and then summed over the integers j, so it counted the multiplicity p of the integer n. –  Ethan Mar 1 '13 at 4:19
add comment

These formulas are convoluted and what looks to me as useless representations of the p adic order of an integer, all you seem to have done is taken advantage of the fact $$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 j, so that it counted the multiplitices p of a given integer, which you gave as an ugly double sum, in addition I doubt this is of any use, sense $$v_p(n)=\gcd(p^{[\log_p(n)]},n)$$, which can be calculated very fast useing the euclidean algorithm.

Also, just to show you 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}^{[\log_p(n)]}[\frac{n}{p^j}]$$ $$\sum_{k=1}^np^{v_p(k)}=\sum_{k=1}^np^{f_p(k)}=n+(1-\frac{1}{p})\sum_{j=1}^{[\log_p(n)]}p^j[\frac{n}{p^j}]$$ And in general $$\sum_{k=1}^nf_p(k)g(k)$$ can be calculated for any function $g(k)$ with exponentially smaller partial sums, then the ones you use just to represent one value of $f_p(k)$.

So I wouldn't say your formulas are any more original, then say, some long convoluted trigonometric identity, that no one has formally recorded, but can be derived in a pinch.

share|improve this answer
    
Very nice answer. –  Eric Naslund Mar 1 '13 at 4:21
    
Like your answer. By the way any reference where your first equation (roots of unity...) is used in p-adic number theory? –  al-Hwarizmi Jun 5 '13 at 14:51
    
@al-Hwarizmi This just comes out of the fact $$1_{a\mid n}=\frac{1}{a}\sum_{t=0}^{a-1}e^{2\pi i\frac{tn}{a}}$$ which can be proven using the geometric series formula. –  Ethan Jun 5 '13 at 22:56
    
sure. Thanks. I just wanted to know if somewhere else someone brought this form up in connect to p-adic orders. Thanks. –  al-Hwarizmi Jun 6 '13 at 7:21
    
By the way, remind the Gauss sums! –  al-Hwarizmi Jun 6 '13 at 9:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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