Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone happen to have at hand a short proof that demonstrates that there do (or do not) exist one or more algebraically representable prime number generating functions?

share|cite|improve this question
What do you mean by "algebraically representable"? – Qiaochu Yuan Jun 1 '12 at 3:30
A reasonable version might be: there is a nonconstant bivariate polynomial $P(z,w)$ such that for some sequence $p_n$ of distinct primes, $P(n,p_n) = 0$. – Robert Israel Jun 1 '12 at 19:04
I guess that wasn't precise. By 'algebraically representable' I meant: – enthdegree Jun 3 '12 at 0:24
up vote 1 down vote accepted

You clarified that you meant, "Is there an algebraic function which generates the primes", that is, "Is there a fixed expression using only addition, subtraction, multiplication, division, and (fixed) root extraction which generates the primes?" The answer is no, because algebraic expressions cannot have the required growth rate, lacking anything that grows logarithmically, while $p_n\sim n\log n.$

share|cite|improve this answer


share|cite|improve this answer
$$\pi(x)=\sum_{n\le x}\left|\operatorname{sgn}\prod_{k=2}^n\prod_{l=2}^n(n-kl)\right|$$ is a representation that can be linked fairly directly to the definition of primes. – anon Jun 1 '12 at 1:54
@anon I'm not sure that can be called "algebraic." – Thomas Andrews Jun 1 '12 at 2:12

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.