Programming Praxis

Over at mersenneforum.org, a small community of people interested in factoring large integers talk about their craft, share tips and accomplishments, and sometimes play factoring games. Today’s exercise is about two of those games.

The home prime of a number n is computed by factoring the number into its prime factors, concatenating the digits of the prime factors (which have been sorted into ascending order), and repeating until the result is prime; this prime number is known as the home prime. For instance, 99 factors as 3 · 3 · 11; 3311 factors as 7 · 11 · 43, and 71143 is prime, so HP(99) = 71143, computed in three steps. Sloane has the list of home primes at A037274. Note that the home prime of a prime number is the number itself. Many numbers resolve to their home prime in just a few steps, as above, but others take longer, and it not known if all numbers eventually resolve to a home prime. At mersenneforum, and at the World of Numbers, Alex Gruppa, Paul Leyland, and Nicolas Daminelli have been working on the calculation of HP49 for ten years, and are currently stalled, after 105 steps, by a 210-digit composite.

Another factoring game involves the Euclid-Mullin sequence, which starts with a₁ = 2 and continues ; the first few terms are 2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, … (A000945). Currently, only the first 47 terms are known, with calculations stalled by a 256-digit composite; the 43rd term was only found last year after a lengthy effort. It is conjectured but not known that the sequence includes all the prime numbers, as it is closely related to Euclid’s original proof of the infinitude of primes.

Your task is to write two functions to compute the home prime of a given number and to compute the Euclid-Mullin sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2