Detailed mathematical approach

Problem Summary

The goal is to find the smallest integer \(n\) such that the four consecutive numbers \(n, n+1, n+2, n+3\) each have exactly four distinct prime factors. If

$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$

with distinct primes \(p_i\), then the relevant arithmetic function is \(\omega(m)=t\).

The implementations solve the problem directly. They do not build a sieve or a table of precomputed factorizations. Instead, they move upward one integer at a time, compute \(\omega(m)\) by trial division, and stop as soon as the first valid four-term block appears. Because the scan is strictly increasing, the first block found is automatically the smallest possible answer.

Mathematical Approach

The mathematics is simple but very precise: unique factorization tells us how to count distinct prime divisors correctly, and a running streak invariant turns those local counts into the first global solution.

The arithmetic function \(\omega(n)\)

Problem 47 is about distinct prime factors, not total multiplicity. Thus

$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$

even though both numbers contain repeated prime powers. The target condition is therefore

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

This is the exact quantity computed by the C++, Python, and Java implementations.

Why removing prime powers counts each prime exactly once

Suppose we want \(\omega(m)\). If \(2\mid m\), then 2 contributes one distinct prime factor, so the count should increase by exactly 1. After that, dividing out every factor of 2 leaves a reduced number whose remaining distinct prime divisors are all odd. The same logic applies to every odd divisor \(p\): once \(p\mid m\), the count increases by 1, and then every copy of \(p\) is removed before the search continues.

Formally, if

$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$

then

$\omega(m)=1+\omega(q).$

Stripping the full power \(p^a\) is exactly what prevents a repeated prime such as \(2^2\) or \(3^2\) from being counted more than once.

Why the remaining cofactor is either 1 or one last prime

After removing the factor 2, the implementations test odd divisors \(3,5,7,\dots\) only while

$p^2 \le m_{\mathrm{red}},$

where \(m_{\mathrm{red}}\) denotes the current reduced number. If the loop ends with \(m_{\mathrm{red}}>1\), that leftover value must be prime. Otherwise it would be composite and would therefore have a prime divisor at most \(\sqrt{m_{\mathrm{red}}}\), contradicting the fact that all such candidates have already been tested and removed.

If \(r(m)\) denotes the number of distinct prime divisors removed during the loop, the final count is

$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$

The consecutive-run invariant

Once \(\omega(m)\) can be computed for one integer, the search becomes a streaming recurrence. Let \(s_m\) be the length of the longest suffix of consecutive integers ending at \(m\) for which every value has four distinct prime factors. Then

$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$

As soon as \(s_m=4\), the desired block is

$m-3,\ m-2,\ m-1,\ m.$

Because the scan checks integers in increasing order, the first time this happens yields the smallest possible starting value.

Worked Example: the first successful block

The first block reached by the search is

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

Their factorizations are

$134043=3\cdot 7\cdot 13\cdot 491,$

$134044=2^2\cdot 23\cdot 31\cdot 47,$

$134045=5\cdot 17\cdot 19\cdot 83,$

$134046=2\cdot 3^2\cdot 11\cdot 677.$

Each number has exactly four distinct prime factors, so the streak length reaches 4 at \(m=134046\), and the algorithm returns \(134046-3=134043\).

How the Code Works

Counting distinct prime factors of one integer

The C++, Python, and Java implementations all use the same structure. They first test divisibility by 2, count that prime once if it appears, and divide out all powers of 2. Then they try odd divisors in increasing order. Whenever an odd divisor divides the current value, the implementation counts one new distinct prime and strips that divisor completely before moving on. If the reduced value is still greater than 1 after the loop, it is counted as one final prime factor.

Searching for the first valid block

After the factor count for one integer is available, the implementation advances to the next integer and updates two pieces of state: the length of the current streak of successful consecutive numbers and the first integer in that streak. A mismatch resets the streak immediately. A match extends it. When the streak length reaches four, the stored starting value is returned without any further search.

Before solving the target case, the implementations also validate the logic on smaller checkpoint cases. In particular, they confirm that \(14=2\cdot 7\) has two distinct prime factors and that the first case of two consecutive integers with two distinct prime factors starts at \(14\). Those checks verify both the factor-counting routine and the streak update logic.

Complexity Analysis

For a single integer \(m\), trial division costs \(O(\sqrt{m})\) in the worst case. The practical constant is smaller because the factor 2 is handled separately, only odd candidates are tested afterward, and repeated prime powers are removed in batches. If \(N\) denotes the first returned value, then scanning through \(N+3\) costs

$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$

in the worst case.

The extra memory usage is \(O(1)\). No sieve table, factor cache, or prime list is stored. That tradeoff matches the implementations well: the code stays short and transparent, and the first valid block occurs early enough that plain trial division is easily fast enough.

Footnotes and References

1. Problem page: Project Euler 47
2. Prime omega function: Wikipedia - Prime omega function
3. Fundamental theorem of arithmetic: Wikipedia - Fundamental theorem of arithmetic
4. Trial division: Wikipedia - Trial division
5. Integer factorization: Wikipedia - Integer factorization