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

This works fine and gets the answer in 3 seconds on my computer. However if we want, say, the 1000001th prime it takes about 27 seconds, So I improved on it by extending the existing sieve by 1000 rather than making a new one. This makes the code somewhat harder to follow, but it reduced the time for the 10001th prime to under a second and the million and first one to under 7 seconds.

Curious fractions

Task 2 gives us a rather curious binary tree of fractions expressed as a/b, with 1/1 at the root, and asks for a script that can find the parent and grandparent of a given node. 

The relationship between parent and children turns out to be as follows:

• 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.

From that, the solution is fairly trivial and no doubt someone will come up with a one-liner.

But do all values for (positive integer) a and b occur in the tree? The answer is no: although it may be possible to calculate parent and grandparents for a given a/b, it does not follow that there is a path back to the root 1/1.  In fact, I think that a and b have to be mutually prime - ie share no prime factor - for a/b to appear in the tree.