After studying primitive recursion a bit in a math class I took the task to me to remake some primitive recursion functions in Python using strict rules. This means you can only use the S(n)=n+1, Z(n)=0 and Projection function together with the f=(g.h) and Recursion operator.
Using only this I was able to make an isPrime function, so that
isPrime(n) = 1 iff n is prime
isPrime(n) = 0 iff n isn't prime
What I would like to do now is to create a function that returns the n'th prime, but this is harder then I thought.
I have a function Count which returns the number of primes below a given number, so what I would like to do is to find the minimum number m so that Count(m)=n. This can be done easily in Total Recursion using the mu-function, but I would like to do it without.
There is a primitive recursive analog of the mu-function, but then you need to supply an upper bound in which the search takes place, so then I would need to know the upper bound under which the n'th prime is proven to be, and I'n not sure that upper bound exists.
So, does anybody have an idea how to construct a primitve recursive function that returns the n'th prime. Or more generally: A function List(n) that given a function f returns the smallest number m so that Count(f,m)=n. Or alternatively, a primitive recursive function that gives the upper bound under which the n'th prime is definitely located.
Signature removed because of it's blinding awesomeness.