Computer a list of prime numbers using primitive recursion

[johnie104]

Hey,

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.

[Harg]

Given a number n you can primitively recursively find the least prime greater than n. This can be done in a variety of ways; an elegant way is to use Bertrand's postulate which guarantees you the existence of a prime between n and 2n. You can then do a bounded search of this interval to find your prime. With this nextPrime function in hand, you can use recursion to find the nth prime.

[johnie104]

Ok, thanks! That worked perfectly.

Then, I have a follow up question. Suppose you have a subset of the natural numbers P and you have the primitive recursive characteristic function of P, X(n) such that X(n)=1 iff n in P and X(n)=0 otherwise.
Is it then garanteed that the function returning the kth smallest n in P is primitive recursive?

Of course, if P is finite then this is obviously true, and intuively it sounds like this should always be true. But has it been proven?
I think you can reduce this problem to finding a primitive recursive function that describes the bound in which you can find the next n in P, because if you have that bound you can use the same technique as with the prime number finding.
So, next question: If a subset of the natural numbers has a primitive recursive characteristic function, is the maximum distance between 2 following points in P a primitive recursive function?