Project Euler Problem 47

Solution

Answer: 134043

We seek the first run of four consecutive integers each having exactly four distinct prime factors.

Let $\omega(n)$ denote the number of distinct prime factors of $n$.

We want the smallest $n$ such that

$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$

---

Mathematical analysis

A number has four distinct prime factors if its prime factorization contains four different primes, regardless of exponent size.

For example:

$$644 = 2^2 \cdot 7 \cdot 23$$

has distinct primes ${2,7,23}$, so it has exactly $3$ distinct prime factors.

The brute-force strategy would be:

1. Factor every integer.
2. Count distinct prime divisors.
3. Search for four consecutive integers satisfying the condition.

However, repeated factorization is slow if done naively.

---

Efficient idea: modified sieve

Instead of factoring each number independently, we can use a sieve-like approach.

Create an array:

$$\text{count}[n]$$

where count[n] will store the number of distinct prime factors of $n$.

Initially all entries are $0$.

Now iterate through integers $p$:

• If count[p] == 0, then $p$ is prime.
• For every multiple of $p$, increment its count by $1$.

This works because every prime contributes exactly once to each multiple.

Example:

• Prime $2$ increments all even numbers.
• Prime $3$ increments all multiples of $3$.
• etc.

After the sieve finishes:

$$\text{count}[n] = \omega(n)$$

for every $n$.

Then scan for four consecutive entries equal to $4$.

This is extremely efficient and mirrors the classical Sieve of Eratosthenes.

---

Python implementation

def first_consecutive_integers(target_factors=4, consecutive=4, limit=200000):
    """
    Find the first integer in the first run of `consecutive`
    consecutive integers each having exactly `target_factors`
    distinct prime factors.
    """

    # count[n] will store the number of distinct prime factors of n
    count = [0] * (limit + 1)

    # Modified sieve
    for p in range(2, limit + 1):

        # If count[p] == 0, then p is prime
        if count[p] == 0:

            # Add this prime factor to all multiples of p
            for multiple in range(p, limit + 1, p):
                count[multiple] += 1

    # Search for consecutive integers
    streak = 0

    for n in range(2, limit + 1):

        if count[n] == target_factors:
            streak += 1

            if streak == consecutive:
                return n - consecutive + 1
        else:
            streak = 0

    return None

# Compute the Project Euler answer
answer = first_consecutive_integers()

print(answer)

---

Code walkthrough

Function definition

def first_consecutive_integers(target_factors=4, consecutive=4, limit=200000):

We parameterize the problem:

• target_factors=4
• consecutive=4

so the same function can solve related variants.

---

Create counting array

count = [0] * (limit + 1)

count[n] will eventually equal the number of distinct prime factors of $n$.

---

Modified sieve

for p in range(2, limit + 1):

We inspect every integer.

---

Detect primes

if count[p] == 0:

If no smaller prime has marked $p$, then $p$ itself must be prime.

---

Increment multiples

for multiple in range(p, limit + 1, p):
    count[multiple] += 1

Every multiple of $p$ gains one additional distinct prime factor.

Example:

• After processing $2$:

• $2,4,6,8,\dots$ all gain one factor.

• After processing $3$:

• $3,6,9,12,\dots$ gain another.

Thus:

$$count[12] = 2$$

because $12 = 2^2 \cdot 3$.

---

Search for consecutive values

streak = 0

Tracks the current run length.

---

If current number qualifies

if count[n] == target_factors:
    streak += 1

Extend the streak.

---

Found the answer

if streak == consecutive:
    return n - consecutive + 1

If the streak length reaches $4$, return the first integer in that block.

---

Verification on smaller examples

The problem states:

$$14 = 2 \times 7$$

$$15 = 3 \times 5$$

Both have exactly $2$ distinct prime factors.

Running the function with:

first_consecutive_integers(2, 2)

returns:

$$14$$

Correct.

Similarly:

first_consecutive_integers(3, 3)

returns:

$$644$$

matching the example.

---

Final verification

The computed sequence is:

$$134043,\ 134044,\ 134045,\ 134046$$

Their factorizations are:

$$134043 = 3 \times 7 \times 13 \times 491$$

$$134044 = 2^2 \times 23 \times 31 \times 47$$

$$134045 = 5 \times 17 \times 19 \times 83$$

$$134046 = 2 \times 3 \times 11 \times 677$$

Each has exactly four distinct prime factors, and this is the first such consecutive run.

Answer: 134043