8
$\begingroup$

"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}$?

  • 2
    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}$.2011-12-06

3 Answers 3

1

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$.

  • 0
    I didn't take the time to understand it yet but it looks interesting.2012-01-27
-1

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

  • 0
    @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$.2012-01-27
-1

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.

  • 0
    I think we're looking for fun$c$tio$n$s su$c$h that all primes occur as values for some i$n$put while minimizing the asymptotic density of composite integers that also occur.2012-01-28