Vtgyjfy

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.

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

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 quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad;;; rho mapsto rho cup {(n,n+n)}$

We define

$tag 2 mu_n: mathcal P to mathcal P$
$quad quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad;;; 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 }$
$quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad mathtt E(1) = emptyset$
$quadquad quadquadquadquadquadquadquadquadquadquadquadquadquadquad 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 quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad;;; 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.