Project Euler Problem 47: Distinct Primes Factors

The source code for this problem can be found here.

Problem Statement

The first two consecutive numbers to have two distinct prime factors are:

\[\begin{split}14 &= 2 \times 7 \\ 15 &= 3 \times 5\end{split}\]

The first three consecutive numbers to have three distinct prime factors are:

\[\begin{split}644 &= 2^2 \times 7 \times 23 \\ 645 &= 3 \times 5 \times 43 \\ 646 &= 2 \times 17 \times 19.\end{split}\]

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

Solution Discussion

The obvious approach to this problem is to increment through integers, factor them, and identify a run of four integers, each with four unique prime factors. Even those these integers are quite small, factoring is very expensive. It would be good to avoid repetitive factoring.

A slight tweak on prime sieving will actually work very well for this problem. During traditional prime sieving we build a list of primes by invalidating composite numbers. Each composite will be marked by each of its prime divisors. So, rather that simply mapping an integer to a boolean indicating “prime or not”, we can store a count of the number of prime numbers that divide each composite number.

Once sieving has completed, we may search for a run, four long, of integers with a count of four prime divisors.

There is actually one simple improvement that can be made on this scheme. Note that sieving occurs by iterating over the integers in ascending order, and that as we process each integer we know any smaller prime divisors have been accounted for. Further, an integer is only divisible by smaller prime factors. This means, that as we process each integer, we know that we have already considered all prime divisors of that integer. Therefore, we can search for the run of four successive integers with four distinct prime divisors while sieving occurs.

Solution Implementation

def solve():
    """ Compute the answer to Project Euler's problem #47 """

    target = 4  # number of prime factors and successive integers
    limit = 150000  # arbitrary upper-bound on the search, found by trial and error
    n_prime_divisors = [0] * limit  # the number of prime divisors of each integer considered

    run_length = 0  # length of the current run of valid integers
    for n in range(2, limit):
        if n_prime_divisors[n] == 0:
            # n is prime, sieve out multiples of n
            for m in range(2 * n, limit, n):
                n_prime_divisors[m] += 1  # m is divisible by n (prime)
            run_length = 0  # n is invalid, reset our run counter
        elif n_prime_divisors[n] == target:
            run_length += 1  # n is valid, increment our run counter
        else:
            run_length = 0  # n is invalid, reset our run counter

        if run_length == target:
            return n - target + 1  # we've found the smallest target run


expected_answer = 134043

solutions.problem47.solve()

Compute the answer to Project Euler’s problem #47