\documentclass[12pt]{article} \input{defs2} \begin{document} \cl {\bf PRIME GENERATING FUNCTIONS} \cl {Darren D. Wick} \cl {Ashland University} \cl {April 2, 2005} \noi \cl {\bf Do there exist functions} $$f:\fatn \rightarrow \fatz $$ \cl {\bf that output:} \noi \noi 1) ONLY PRIMES? \noi \noi 2) ALL PRIMES? \noi \noi 3) ONLY ALL PRIMES? \noi \cl {QUESTION 1} \cl { Do there exist functions generating} \cl{ ONLY prime numbers?} \noi \cl {EXAMPLE} \cl {Euler's polynomial} $$f(n)=n^2+40n+41$$ \noi \cl { $f$ is prime for $n=\{ 0,1,2,\ldots ,39\}$} \noi \cl { $f(40)=3241=7\cdot 463$} \noi\noindent The following result shows that searching for a polynomial that outputs only primes is futile: \noi If $f:\fatn^k \rightarrow \fatc$ is a polynomial in $k$ variables with complex coefficients that outputs only prime numbers, then $f$ is constant. \noi HOWEVER, there do exist functions that output only prime numbers \noi \cl {EXAMPLE} \noi There exists a constant $$\theta = 1.3064\ldots$$ such that \noi $$f(n)=\Big\lfloor \theta^{3^n} \Big\rfloor$$ \noi is prime for all $n\geq 1$ \noi $$f(1)=2 \ \ \ f(2)=11 \ \ \ f(3)=1361 $$$$ f(4)=2521008887$$ \noi \cl {EXAMPLE} \noi There exists a constant $$\omega =1.9287800\ldots$$ such that $$g(n)=\Big\lfloor 2^{2^{2^{.^{.^{2^\omega}}}}}\Big\rfloor$$ \noi is prime for all $n\geq 1$ $$g(1)=3 \ \ \ \ \ g(2)=13 \ \ \ \ \ \ g(3)=16381 $$ \noi \cl {QUESTION 2} \cl { Do there exist functions generating} \cl { ALL prime numbers?} \noi (Maybe) suprisingly, as a consequence of the solution to Hilbert's tenth problem, there are polynomials that do the trick. \noi In 1976, Jones, Sato, Wada and Wiens explicitly produced a polynomial $F$ in 26 variables of (total) degree 25 such that: \noi The set of positive outputs of $F$ is the set of all primes. \noi \noi \includegraphics[height=2in,width=6in]{/home/dwick/DATA/Professional/Research/Talks/Primes/26varpoly.pdf} \noi Unfortunately, this polynomial produces lots of composite negative integers. \noi There also exist similar polynomials with \noi \hskip20pt 42 variables and degree 5 \noi \hskip20pt 10 variables and degree about $1.6\times 10^{45}$ \noi \cl {QUESTION 3} \cl { Do there exist functions generating} \cl { ONLY ALL prime numbers?} \noi \cl { WILSON'S THEOREM} \noi \hskip30pt a) If $n$ is prime, then $$(n-1)! \equiv -1 ({\rm mod} \ n)$$ \noi \hskip30pt b) If $n>4$ is composite, then $$(n-1)! \equiv 0 ({\rm mod} \ n)$$ \noi \cl {PRIME COUNTING FUNCTION} \noi Define $$F(n)=\Big\lfloor \cos^2 \pi {{(n-1)! +1}\over {n}}\Big\rfloor$$ \noi If $n$ is prime, then $(n-1)!+1=kn$ is a multiple of $n$ so that $F(n)=\lfloor \cos^2 k\pi \rfloor = 1$. \noi \noi If $n$ is composite, then $(n-1)!=kn$ is a multiple of $n$ so that $${{(n-1)!+1}\over{n}}={{kn+1}\over n}$$ is not an integer and $$F(n)=\Big\lfloor \cos^2 \pi {{kn +1}\over {n}}\Big\rfloor=0$$ \noi Thus $$ F(n)=\cases{\ds 1 \ \ \ {\rm if \ } n {\rm \ prime} {\rm \ or } \ n=1 \cr 0 \ \ \ {\rm if \ } n {\rm \ composite} \cr }$$ \noi The prime counting function $\pi (m)=$ the number of primes $p$ with $p\leq m$ $$\pi (m)=-1+\sum_{j=1}^m F(j)$$ \noi \noi \cl {EXAMPLE: (Willans)} $$p_n =1+\sum_ {m=1}^{2^n} \Bigg\lfloor \Big\lfloor {n\over {1+\pi (m)}} \Big\rfloor^{1\over n}\Bigg\rfloor$$ \noi \noi \cl {EXAMPLE: (Gandhi)} \noi The Mobius function $\mu$ is defined as $$ \cases{\ds \mu (1)=1 \cr {\rm if \ n \ is \ the \ product \ of \ r \ distinct \ primes,} \ \mu (n)=(-1)^r \cr {\rm if \ the \ square \ of \ a \ prime \ divides \ n,} \ \mu (n)=0 \cr }$$ \noi Let $P_{k}=p_1 p_2 \cdots p_k$, then $$p_n = \Big\lfloor 1 - {1\over {\log 2}} \log \Big( {-{1\over 2}} + \sum_{d|P_{n-1}} {{\mu (d)}\over {2^d -1}} \Big) \Big\rfloor$$ \noi \cl {EXAMPLE: (Ernvall) } \noi Let $$d={\rm gcd} ((m!)^{m!} -1,(2m)!)$$ $$t={{d^d}\over {{\rm gcd} (d^d ,d!)}}$$ \noi Let $a$ be the unique integer such that $d^a$ divides $t$ but $d^{a+1}$ does not divide $t$. Then the smallest prime larger than $m$ is $$p={{d}\over {{\rm gcd} ({t\over {d^a}} ,d)}}$$ \noi \cl { EXAMPLE : (Jones 1975)} \noi Define $r(y,x)$ to be the remainder upon division of $y$ by $x$. Define $$s(y,x)={{(|y-x|+y-x)}\over {2}}$$ Then $$p_n=\sum_{i=0}^{n^2} s(1,s(\sum_{j=0}^i r(s(j,1)!^2,j),n))$$ \noi \cl {EXAMPLE: (Moser 1950) } \noi Let $p_n$ denote the $n^{th}$ prime and define the number $$A=.203005000700011000013\ldots $$$$=\sum_{n=1}^{\infty} {p_n \over {10^{{n(n+1)}\over 2}}}$$ \noi The existence of $A$, i.e. the non-overlapping of the non-zero digits, is assured by Bertrand's postulate, $p_{n+1}<2p_n$ \noi One then extracts the $n^{th}$ prime from $A$ via $$p_n = \Big\lfloor {10^{{n(n+1)}\over 2}A} \Big\rfloor - 10^n \Big\lfloor {10^{{n(n-1)}\over 2}A} \Big\rfloor$$ \noi \cl { EXAMPLE: (Ruiz)} \noi For $n>1$ define $$f(n)=2+[2(n-1)!({\rm mod} \ n)]$$ By Wilson's Theorem, \noi If $n$ is prime, then $2(n-1)!\equiv -2({\rm mod} \ n)$ so that $f(n)=2+(n-2)=n$. \noi Also, $f(4)=2$ and if $n>4$ is composite, $2(n-1)!\equiv 0({\rm mod} \ n)$ so that $f(n)=2$. Thus $$f(n)= \cases{ n \ \ \ \ {\rm if } \ n \ {\rm is \ prime} \cr 2 \ \ \ \ \ \ \ \ \ {\rm otherwise} \cr}$$ \noi $$ f(2)=2+2({\rm mod} \ 2) =2$$ $$ f(3)=2+4({\rm mod} \ 3) =3$$ $$ f(4)=2+12({\rm mod} \ 4) =2$$ $$ f(5)=2+48({\rm mod} \ 5) =5$$ $$ f(6)=2+240({\rm mod} \ 6) =2$$ $$ f(7)=2+1440({\rm mod} \ 7) =7$$ $$ f(8)=2+10080({\rm mod} \ 8) =2$$ $$ f(9)=2+80640({\rm mod} \ 9) =2$$ $$ f(10)=2+725760({\rm mod} \ 10) =2$$ $$ f(11)=2+7257600({\rm mod} \ 11) =11$$ \noi SUMMARY: While all of these functions are interesting and may have some theoretical interest, due to their computational complexity they are useless when calculating large primes. \noi \cl {APPENDIX 1} \cl {The constants $\theta$ and $\omega$} \noi Recall that the functions $$g(n)=\Big\lfloor 2^{2^{2^{.^{.^{2^\omega}}}}}\Big\rfloor$$ $$f(n)=\Big\lfloor \theta^{3^n} \Big\rfloor$$ are prime for all $n\geq 1$, where $$\omega =1.9287800\ldots$$ $$\theta = 1.3064\ldots$$ The numbers $\theta$ and $\omega$ are obtained in a similar fashion. We prove the existence of $\omega$. \noi Proof (Wright): It is known that for every $N\geq 2$, there is a prime between $N$ and $2N$. Choose a sequence of primes $\{ P_n \}$ with $$2^{P_n}