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.

I was attempting to construct a formula for the n th prime using elementary functions - I didn't achieve this* but I did come up with some formulae in finite products and sums of elementary functions for various number theoretic functions such as the Euler Totient, Prime Pi, Möbius Mu, Divisor Sigma, Next Prime, LCM, etc.

For example it can be easily verified from the property of cosine that the below expression is equal to the divisor sigma function σ_k(n) for each k,n. $$ σ_k(n)=\sum _{m=1}^n m^{k-1} \sum _{l=1}^m \cos \left(2 \pi \frac{l n}{m}\right)$$

*Edit: Below is an expression for the n'th prime as a function of n in elementary functions.

$$p(n)=\sum _{a=2}^{2^n} \sin \left(\pi 2{}^{\wedge}\left(\left(n-\sum _{b=2}^a \frac{\sin ^2\left(\frac{\pi }{b}((b-1)!)^2\right)}{\sin ^2\left(\frac{\pi }{b}\right)}\right){}^2-1\right)\right)\frac{a \sin ^2\left(\frac{\pi }{a} ((a-1)!)^2\right) }{\sin ^2\left(\frac{\pi }{a}\right)}$$

What motivates me to comment is that none of the commonly cited examples of prime generating functions involve only elementary functions - they will employ congruence modulus or the least integer function or integral part or something related, and so I wonder then if the idea above is in fact novel in some way. The Prime Formulas article (Mathworld) gives the following account : "There exist a variety of formulas for either producing the nth prime as a function of n or taking on only prime values. However, all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge of the primes ahead of time in order to use the formula (Dudley 1969; Ribenboim 1996, p. 186)." But in the above construction of Next Prime we can enumerate NP(n) (or just the inner sum enumerating j) to give a sequence that consists only of primes and is not constrained by the above criteria.

share|improve this question
How widely have you looked for elementary formulas for primes? Have you looked at Hardy and Wright? at Crandall and Pomerance? at Niven, Zuckerman, and Montgomery? at MathSciNet? –  Gerry Myerson Jun 9 '11 at 12:30
Hello Gerry, please forgive my ignorance but I am not familiar with these authors. –  AEv Jun 9 '11 at 13:46
@A. E.: if you're not familiar with G.H. Hardy, then you have some rather delightful reading ahead of you! And I heartily encourage you to read more into the number theory; believe it or not, things get even more fascinating once you get past the 'surface' of quirky formulas like the one you found and into the meat of the subject. –  Steven Stadnicki Jun 10 '11 at 2:14
Eh, I do not know if this is the place to say so, since the lack of experience, but, judging from my narrow view, the branch of mathematics named analytic number-theory is $not$ number-theory at all; moreover, as Weil put it, Hardy is not a number-theorist. If one can gain insights into number-theory, as the author wants, then tell me so as to correct my wrong view, thanks. P.S. My view does not matter as a commonly accepted knowledge, and I put it here just to judge this. –  awllower Jun 10 '11 at 7:37
"analytic number theory is not number theory" is meaningless without a definition of terms. –  Gerry Myerson Jun 10 '11 at 12:24

2 Answers 2

up vote 8 down vote accepted

Every "elementary" formula I know of is a disguised implementation of a slow algorithm for testing whether a number is prime. For actually computing primes, it's better just to directly implement a fast primality testing algorithm, of which there are many. For actually proving something about primes, experience has shown that it's better to either ask for asymptotic rather than exact information or to use more sophisticated techniques (e.g. the Riemann zeta function).

A basic reason formulas like the one you give are not useful for proving anything is that they involve the cancellation of many terms, and there's no way to extract reliable asymptotic information without knowing much more about how the terms cancel.

share|improve this answer
Thanks Quiacho, this is just what I had supposed and as you say my formulae are in fact just obfuscated sieves. Just as an exercise I did come up with a similar formula for the n'th prime which I have edited into my original post. –  AEv Jun 10 '11 at 1:07
Also I think I may have misunderstood the definition of elementary. From Mathworld : "A function built up of a finite combination of constant functions, field operations (addition, multiplication, division, and root extractions--the elementary operations)--and algebraic, exponential, and logarithmic functions and their inverses under repeated compositions (Shanks 1993, p. 145; Chow 1999)." But does this definition include repeated summation/multiplication as in the formulae I gave ? –  AEv Jun 10 '11 at 1:13
@A. E.: not only does it not include 'indefinite' summations or products (i.e., those whose bounds are functions rather than constants), it also doesn't include the factorial function (which could be viewed as such an indefinite product), so your functions are 'non-elementary' in two different fashions. –  Steven Stadnicki Jun 10 '11 at 2:09
I would argue that by your definition it is non-elementary in exactly one fashion, since $$n!=\prod _{i=1}^n i=\exp \left(\sum _{i=1}^n \ln (i)\right)$$, but I get the point ! –  AEv Jun 10 '11 at 2:33

C P Willans, On formulae for the $n$th prime, Math Gazette 48 (1964) 413-415 gives $$\pi(m)=\sum_2^m(\sin^2\pi{((j-1)!)^2\over j})/\sin^2(\pi/j))$$ This is quoted in Paulo Ribenboim, The Little Book of Bigger Primes.

share|improve this answer

Your Answer


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.