7 - 10,001st Prime

Problem

By listing the first six prime numbers: $2, 3, 5, 7, 11$, and $13$, we can see that the $6$th prime is $13$. What is the $10,001$st prime number?

Foundations

Prime number checks with un reduce mul

If you've recently looked at chapter 3 on prime checks then this will be familiar and you can skip this section.

Length check

What happens when un reduce mul is called on a prime?

    °/× 19
[19]
    °/× 21
[3 7]
    °/× 23
[23]
    °/× 29
[29]

It seems that un reduce mul returns an array that contains $N$ and only $N$ when $N$ is prime.

Therefore, a prime check might be to check the length

    IsPrime ← =1 ⧻ °/×

Let's get all primes under $100$. We can use where for this after applying IsPrime to a range. Since where is 0-indexed, we need to account for that with +1

    +₁⊚ ≡IsPrime⇡₁100
[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]

Pervasion

Note that un reduce mul is pervasive. Take the range $1-10.$

    °/× ⇡₁10
╭─
╷ 1 1 1 1 1 1 1 2 1 1
  1 1 1 2 1 2 1 2 3 2
  1 2 3 2 5 3 7 2 3 5
                      ╯

Over this range, the largest collection of factors comes from $8$ which has prime factors $[2\ 2\ 2]$. All other elements are padded with $1s.$ That does make sense since multiplying by $1$ doesn't change the result. $1 * 2 * 5$ is just as much $10$ as $2 * 5.$

Well now, if a prime is entered, the last element of that column is the same as the number which generated it.

    °/× [7 9 11]
╭─
╷ 1 3  1
  7 3 11
         ╯

So if we get the last element of each

    ⊣ °/× [7 9 11]
[7 3 11]

and preserve the original range for comparison

    ⊣ ⊸°/× [7 9 11]
[7 9 11]
[7 3 11]

then primes is where these arrays are equal.

    ▽ ⊸= ⊣ ⊸°/× [7 9 11]
[7 11]

We can then define.

    IsPrimePervasive ← =⊙(≠1) ⊸=⊣ ⊸°/×
    +₁ ⊚ IsPrimePervasive ⇡₁10
[2 3 5 7]

Note that we need to correct for 1 as it is not a prime number.

Difference in performance

On single checks, both should be fast enough for our purposes. But what about a range of numbers?

A very very informal rule to keep in mind.

$$If\ it's\ rows,\ then\ it's\ slows!$$

Let's benchmark the prime checks on half a million elements.

    ⊙◌⍜now(+₁ ⊚ ≡IsPrime⇡₁500000)
    ⊙◌⍜now(+₁ ⊚ IsPrimePervasive⇡₁500000)
0.41751933097839355
0.032407283782958984

The pervasive version is about 10x faster than the prime checker that needs rows.

Brute force solution

Wait a second. We can check half a million elements in ~0.03 seconds. Can we just throw computation at this problem and see what happens? Let's count how many primes this is. We can just sum it up since it is $1s$ for primes and $0s$ else.

    /+ IsPrimePervasive⇡₁500000
41538

Wowee. So, what if we just grab the 10001st one?

Let's use where for this. Remember to add,1 for the offset. What are the first 20? Does this look right?

    ↙20 +₁ ⊚ IsPrimePervasive⇡₁500000
[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71]

Sure. Those are primes. Let's just pick the 10001st one. We use 10000 because of 0-indexing

    ⊡ 10000 +₁ ⊚ IsPrimePervasive⇡₁500000
104743

How fast?

Fast.

    ⊙◌⍜now(⊡ 10000 +₁ ⊚ IsPrimePervasive⇡₁500000)
0.030573606491088867

Though, this program doesn't feel satisfying, does it? There is nothing smart about it. It just smashes through a range that we picked at random.

Can we do something smarter?

Note: I'm renaming IsPrimePervasive to IsPrime for the remainder of this document

    IsPrime ← =⊙(≠1) ⊸=⊣ ⊸°/×

What we could try is to approach the bounds gradually. We could just assume that for a range of length $X$, it's fine to start searching for a range of size $2 \times X$ since even numbers are not prime.

This range is likely not sufficient and therefore we keep multiplying the range size by 2 until it contains our prime number.

We could do this with a do loop whose condition is to check how many primes are over a range, and stop once our desired index is available.

For the condition, we can reduce add the IsPrime calculation on a range to get how many there are. We continue if it is less than our target.

    N           ← 10000
    DoCondition ← ≤ N /+ IsPrime⇡₁

The do body should simply take the range size argument and double it. The argument to the do body is the range size.

    ⍢(×2|DoCondition) ×2N
160000

Great. This tells us that the range 160000 includes the 10001st prime.

    ⊡N+₁ ⊚ IsPrime⇡₁ ⍢(×2|DoCondition) ×2N 
104743

Speedy?

    ⊙◌⍜now(⊡N+₁ ⊚ IsPrime⇡₁ ⍢(×2|DoCondition) ×2N)
0.024101734161376953

This is about 0.006 seconds faster. That's not a lot. If we think about it, it makes sense. We check $10+20+40+80+160=310$ thousand numbers for the condition, then we check a $160$ thousand numbers again. That's $470$ thousand numbers vs randomly chosen $500$ thousand. Surely we can do better?

Math

The most optimal thing for this method is if we could somehow know the range to check beforehand. A close second would be to speed up the calculation of the DoCondition, preferably with a single calculation instead of something over an ever increasing range.

There is a theorem for this close second. Take a look at the Prime Number Theorem and the Prime Counting Function.

We define $\pi(x)$ as the prime counting function. This function gives us the amount of primes that are less or equal to $x$. The simple estimate is

$$ \pi(x) \sim \frac{x}{ln(x)}$$

The natural logarithm in Uiua is attained with un exp X . See exponential

The prime counting function article on Wikipedia seems to imply that the error rises to at most ~15% and then drops as the numbers get larger. Keep this in mind.

Let's replace the DoCondition with the prime counting function.

We want to divide our input with the natural logarithm of said input. We'll start with a fork

    fork un exp id
    ⊃°ₑ ∘

Then we divide to attain $$ \frac{x}{ln(x)}$$

  div fork un exp id
  ÷ ⊃°ₑ ∘

We'll store this as function P and rewrite our DoCondition.

    P ← ÷ ⊃°ₑ ∘
    N           ← 10000
    DoCondition ← ≤ N P

Now, let's see if this gives us the same result as our former do loop.

    ⍢(×2|DoCondition) ×2N
160000

Yes. It is the same. However, our DoCondition is much faster now, since it doesn't calculate over the same range it outputs. We can get away with a much lower increment to get closer to the real range. Let's try a factor of 1.001 and let's also add in our worst case error correction of ~15%.

    ⌈ × 1.15 ⍢(×1.001|DoCondition) ×1.001 N
134306

Now, is the factor of $1.001$ slow enough to be significant?

    ⊙◌⍜now(⌈ × 1.15 ⍢(×1.001|DoCondition) ×1.001 N)
0.00435948371887207

No, not at all. Putting it all together

    ⊡ N +₁ ⊚ IsPrime⇡₁ ⌈ × 1.15 ⍢(×1.001|DoCondition) ×1.001 N
104743

# And speed?
    ⊙◌⍜now(⊡ N +₁ ⊚ IsPrime⇡₁ ⌈ × 1.15 ⍢(×1.001|DoCondition) ×1.001 N)
0.01471567153930664

Extra credit - Big Primes

Let's see how our range doubling and prime-counting versions fare against bigger primes.

According to bigprimes.net the 1000001st prime is $15485867.$

Range doubling method

We re-initialize N and DoCondition to the new parameters.

    N           ← 1000000
    DoCondition ← ≤ N /+ IsPrime⇡₁

and then run the final program as before

    ⊡N+₁ ⊚ IsPrime⇡₁ ⍢(×2|DoCondition) ×2N
15485867

Great. It gives us the correct answer. But how fast?

    ⊙◌⍜now(⊡N+₁ ⊚ IsPrime⇡₁ ⍢(×2|DoCondition) ×2N)
3.39035964012146

Ok. Not too bad.

Prime counting method

Adjusting to the new parameters

    P ← ÷ ⊃°ₑ ∘
    N           ← 1000000
    DoCondition ← ≤ N P

and running our final program as before.

    ⊡ N +₁ ⊚ IsPrime⇡₁ ⌈ × 1.15 ⍢(×1.001|DoCondition) ×1.001 N
15485867

Great. Also correct, but is it faster?

    ⊙◌⍜now(⊡ N +₁ ⊚ IsPrime⇡₁ ⌈ × 1.15 ⍢(×1.001|DoCondition) ×1.001 N)
1.5464730262756348

Yeah. About twice as fast. Remember, that the error goes down as we check higher and higher primes. Lowering the error correction to $5%$ is about 100ms faster.