### Large primes and curious fractions

### The 10001st prime number

Task 1 for week 146 is a more of a challenge than in recent weeks: we are asked to calculate the 10001st prime number.

The first question to ask is whether the desired number can be represented as an integer in Perl. The largest number which Perl treats as an integer is given by ~1 + 1 and on my computer that is 18446744073709551615 or about 2 * (10**19). Primes get a bit thin on the ground as they get larger, but I think we can safely postulate that we will find 10**5 of them before we hit that limit.

My 'go to' algorithm for primes is the sieve of Eratosthenes. Born in 276 BC, Eratosthenes was the first person to estimate the circumference of the earth - remarkably accurately - while managing the largest library in the world, in Alexandria.

His sieve works like this. Write down all the numbers from 2 to however large you want - say n. Take the leftmost number - 2 - and rub out all its multiples - 2, 4, 6, 8 and so on. Now do it again: the leftmost number remaining is 3, because you rubbed out 2, so now you rub out 3, (not 6 because you already rubbed it out), 9, 15 and so on. You repeat that until the leftmost number is more than the square root of n, and what remains is a list of all the prime numbers less than or equal to n.

So that gets us all the primes less than n, but what we want is the nth prime number. Eratosthenes unfortunately neglected to address that problem, but we can improvise.

After a bit of experimenting I came up with this:

- Make a sieve out of 1-1000
- Count the primes
- If you haven't reached 10001 of them then ...
- Make a sieve of 1-2000
- and so on

### Curious fractions

- The left child of parent a/b is a/(a+b)
- The right child is (a+b)/b.
- It follows that if a member is < 1 then it is a left child
- and if > 1 then a right child.

## Comments

## Post a Comment