Using the recursion theorem to implement the Sieve of Eratosthenes.

Question

Update: I provided an answer here that shows how to define a mathematical function using the recursion theorem. This function can be reconfigured to compute the prime-counting function, $\pi(x)$.

Only one question remains:

Question 1: Has the Sieve of Eratosthenes already been mathematically revamped as a recursive function?

I did not find the word 'recursion' in the wikipedia article Generating primes, so this theory might be useful.

When running computers to get a list of all primes numbers using recursion, the 'state variables' should be retained for the next computer run.

---

The initial development was the construction of a Python program that maintained/updated state variables to generate, and keep generating, the list of prime numbers. I was using concepts found in the wiki article The Sieve of Eratosthenes.

Answer 1

The Legendre formula,

https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_π(x) http://mathworld.wolfram.com/LegendresFormula.html

which based on the sieve, is recursive: $\phi(x,a)=\phi(x,a-1)-\phi(\frac{x}{p_a},a-1)$. With it you can find $\pi(x)=\phi(x,a)+a-1$ where $a=\pi(\sqrt[2]{x})$.

However, I am not sure it is recursive the way you want it to be recursive

Answer 2

Here $\mathbb N = \{2,3,4,\dots\}$.

Let $\mathcal P$ denote the set of all finite subsets of $\mathbb N \times \mathbb N$.

We define

$\tag 1 \gamma_n: \mathcal P \to \mathcal P$ $\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\; \rho \mapsto \rho \cup \{(n,n+n)\}$

We define

$\tag 2 \mu_n: \mathcal P \to \mathcal P$ $\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\; \rho \mapsto \rho \cup \{(m,n+m) \; | \; (m,n) \in \rho \}$

The mapping $\Gamma: \mathbb N \times \mathcal P \to \mathcal P$ is defined by

$$ \Gamma(n,\rho) = \left\{\begin{array}{lr} \gamma_n(\rho), & \text{when } n \notin \text{Range}(\rho)\\ \mu_n(\rho), & \text{otherwise} \end{array}\right\} $$

Using the recursion theorem, we define

$\tag 3 \mathtt E: \mathbb N \cup \{1\} \to \mathcal P \quad \quad \text{ by }$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \mathtt E(1) = \emptyset$ $\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \mathtt E(n+1) = \Gamma(n+1,\mathtt E(n))$

The function $\mathtt E$ has the property that the projection of $\mathtt E(n)$ onto the first coordinate is the set of all prime numbers less than or equal to $n$. So, letting $pr_1$ denote this projection, we define

$\tag 4 \pi': \mathbb N \to \mathbb N$ $\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\; n \mapsto \text{#} \left[\, pr_1(\mathtt E(n))\,\right]$

so that $\pi'(n)$ is the set of all primes less than or equal to $n$. It is immediate that this function is the restriction of the prime-counting function $\pi$ to $\mathbb N$.

Values of $\mathtt E(n)$ for $n \le 11:$

E(2) = {(2, 4)}
E(3) = {(2, 4), (3, 6)}
E(4) = {(2, 6), (2, 4), (3, 6)}
E(5) = {(2, 6), (5, 10), (2, 4), (3, 6)}
E(6) = {(2, 6), (5, 10), (3, 9), (3, 6), (2, 8), (2, 4)}
E(7) = {(7, 14), (2, 6), (5, 10), (3, 9), (3, 6), (2, 8), (2, 4)}
E(8) = {(7, 14), (2, 6), (5, 10), (3, 9), (3, 6), (2, 8), (2, 4), (2, 10)}
E(9) = {(7, 14), (2, 6), (5, 10), (3, 9), (3, 6), (3, 12), (2, 8), (2, 4), (2, 10)}
E(10) = {(7, 14), (2, 6), (5, 10), (3, 12), (2, 8), (2, 10), (3, 9), (5, 15), (2, 12), (3, 6), (2, 4)}
E(11) = {(7, 14), (2, 6), (5, 10), (3, 12), (2, 8), (11, 22), (2, 10), (3, 9), (5, 15), (2, 12), (3, 6), (2, 4)}

Note: These function values came from the Python program. Since mathematics is not concerned with 'efficiency' in any way, the program was 'dumbed down' so the outputs of $\mathtt E$ can contain elements that are no longer used by the recursion algorithm; this made it easier to define the algorithm.