# Which is the most restrictive closed-form expression that still generates all primes?

"The set $\{f(n)\}, n=1,2,\ldots$ includes all primes except a finite number of exceptions."

This statement is true for $$f(n)=\sqrt{1+24n},$$ for which the exceptions are 2 and 3. It also generates non-integers and non-prime integers, however. (spoiler alert) The proof uses the fact that the two neighbours of all primes (except 2 and 3) contain the factors 2, 3 and 4 between them (2*3*4=24).

Since no more factors than 2^3 and 3 can be found generally in the two neighbours of primes, the expression $f(n)=\sqrt{1+24n}$ is the most restrictive expression of that particular functional form that still generates all primes. That is, it generates all primes and the smallest number of non-primes.

Other expressions that fit the statement above are $f(n)=\sqrt{1+4n}$, $f(n)=2n-1$ and of course $f(n)=n$, but they produce more non-primes.

My question: Is it known which closed-form expression $f(n)$ generates all primes and the smallest number (in some sense) of non-primes? Is it perhaps $f(n)=\sqrt{1+24n}$?

• The question isn't well-defined, since as you rightly point out $\sqrt{1+24n}$ doesn't generate all primes, so you'd have to say something about how many exceptions are allowed or how to combine the numbers of false positives and false negatives, e.g. look for the lowest sum of the two. Also, $\sqrt{1+24n}$ generates infinitely many non-primes, so it can't generate the smallest number of non-primes in the sense of cardinality -- are you thinking in terms of asymptotic densities? Oct 7, 2011 at 9:16
• The number of primes in $\{1,2,\ldots,N\}$ is $\pi(N)$ (where $\pi$ is the prime counting function). Since $f(n)=O(\sqrt{n})$, the number of primes in $\{f(n):1 \leq n \leq N\}$ is at most $\pi(f(N))<\pi(N)$ for sufficiently large $N$. So, $f(n)=n$ produces fewer non-primes than $f(n)=\sqrt{1+24n}$. Oct 7, 2011 at 9:21
• Also note that there are expressions which generate exactly the primes. These would be the optimal solutions unless you exclude things like sums or the floor function from your notion of "closed-form expression". Oct 7, 2011 at 9:25
• @Douglas: That depends on whether you compute the density with respect to the arguments or the function values. This underscores my point that the question isn't well-defined. Oct 7, 2011 at 9:26
• For the same reasons that all primes $>3$ occur as values of this formula, all primes greater than $5$ occur as values of $\sqrt[4]{120n+1}$ and all primes greater than $7$ as values of $\sqrt[12]{10920n+1}$. The nonprime integer values of these formulas are a bit sparser than for $\sqrt{24n+1}$. Dec 6, 2011 at 15:41

A number is relatively prime to $24$ if and only if it is a square root of unity mod $24$. So $f(n)$ generates all integers that are not divisible by $2$ or $3$, including all primes greater than $3$. It is possible to do better: $g(x) = \sqrt{\frac{5 + 33 \cdot (-1)^n + 15 n}{2}}$ generates all primes greater than $5$ without including any integers divisible by $2$, $3$, or $5$.

• ,What do you think about my closed form expression which links primes and Lambert W function ? Jan 27, 2012 at 7:52
• I didn't take the time to understand it yet but it looks interesting. Jan 27, 2012 at 8:05

I wrote these two small source codes in Maple:

$1)$

"for n from 1 to 100 by 1 do

if isprime(2n-3) then

print(n);

end if;

end do;"

$2)$

"for n from 1 to 100 by 1 do

if type(sqrt(24n+1),prime) then

print(n);

end if;

end do;"

The first code is giving $44$ values for n when result of expression is prime number,and second code is giving only $13$ values for n.

So we may conclude that closed form $f(n)=2n-3$ is "richer" than closed form $f(n)=\sqrt{24n+1}$

EDIT :

In one of my previous posts I have shown that :

$M_p \equiv 1 \pmod {6\cdot p}$ , where $M_p$ is Mersenne number .

So :

$2^{p}-1=6np+1 \Rightarrow 2^p=6np+2 \Rightarrow 2^{p-1}=3np+1$

If we solve this equality for $p$ we will get the next formula :

$$p=-\left(\frac{3n\cdot W\left(-\frac{2^{-1-\frac{1}{3n}}\cdot \ln 2}{3n}\right)+\ln 2}{n\cdot \ln 8}\right)$$

where $W$ is Lambert W function

This closed-form expression generates all primes greater than $3$ and the small number (in sense of asymptotic density ) of the non-prime integers .

Correction :

Actually this closed expression produces integer values for lower branch of Lambert W function which is denoted as $W_{-1}(x)$ so formula is :

$$p=-\left(\frac{3n\cdot W_{-1}\left(-\frac{2^{-1-\frac{1}{3n}}\cdot \ln 2}{3n}\right)+\ln 2}{n\cdot \ln 8}\right)$$

• See my comments under the question. Oct 7, 2011 at 10:31
• Well, I'm looking for expressions "poorer" than $f(n)=\sqrt{1+24n}$ :). Oct 7, 2011 at 10:57
• @pedja, your code is mistaken because it tests $1 < n < m$ but it needs to test $1 < f(n) < m$ to give a fair comparison. $2n-3$ is a strict superset of the other excepting the element $2$. Jan 27, 2012 at 7:42

It was shown in the answer at: Does the formula $\sqrt{ 1 + 24n }$ always yield prime?

that the expression doesn't generate all primes. There isn't any known algebraic expression that generates an infinite number of consecutive primes. So there can't be a "simplest" such expression. There are of course expressions that generate long strings of primes then fail.

• I think you are misinterpreting the question. It is not the same as the one you linked, but some of the answers there apply here as well. Jan 27, 2012 at 7:45
• Dan you're right. But the question "Is it known which closed-form expression f(n) generates all primes and the smallest number (in some sense) of non-primes?" doesn't make sense now that I read it carefully. F(n) doesn't generate "all primes." The word "and" is a conjunction not a qualifier. So is andreasdr looking for some measure on how much an equation deviates from the ideal of generating all the primes in sequence, then ranking equations against that measure?
– MaxW
Jan 27, 2012 at 21:35
• I think we're looking for functions such that all primes occur as values for some input while minimizing the asymptotic density of composite integers that also occur. Jan 28, 2012 at 1:48