HP49-50G Willan's formulae to find p(n), the n-th prime number

[Albert Chan]

Willans formula for primes.



Floored expression is simply (pi(i-1) < pi(i) < n), where pi = prime-counting function.
Or, if you prefer, (isprime(i) && pi(i)<n) = 0 or 1

2^n upper bound is thus overkill. All we need is upto p_n - 1

p_n = 1 + Σ((pi(i-1) < pi(i) < n), i = 1 .. p_n - 1)      // stop sum when pi(i) = n

This is still very inefficient, with many expensive pi(i)'s.
Instead, we can solve for pi(min(x)) = n, for x

Example, for x = 1000-th prime

pi(x) = n ≈ x/ln(x)   → Rough estimate, x ≈ n*ln(n) ≈ 6908

pi(2) = 1            // 1st prime = 2
pi(6908) = 888   // secant root, n=1000 --> x≈7780
pi(7780) = 985   // secant root, n=1000 --> x≈7915
pi(7915) = 999
pi(7917) = 999
pi(7919) = 1000 // x = p₁₀₀₀ = 7919