## Two Factoring Games

### February 18, 2011

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*_{1} = 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

[…] today’s Programming Praxis exercise, our goal is to implement two algorithms related to prime factors; one […]

My Haskell solution (see http://bonsaicode.wordpress.com/2011/02/18/programming-praxis-two-factoring-games/ for a version with comments):

My solution isn’t very long, but the machinery behind the scenes is rather

extensive. In an effort to save memory, I’ve tried to make heavy use of

iterators—sort of like lazy evaluation of lists in Haskell. Below is what I

wrote for this exercise; I also used an implementation of the Sieve of

Eratosthenes for primes and a Miller-Rabin primality test.

The full code is available here.