notes.html

problem 47 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem rests on <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_factorization" rel="noopener noreferrer" target="_blank">prime factorization</a> - decomposing an integer into the primes whose product equals it. The decisive subtlety is the word <em>distinct</em>: we count only how many <em>different</em> primes divide a number, ignoring multiplicity. Thus 644 = 2<sup>2</sup> x 7 x 23 has three distinct prime factors (2, 7, 23) even though the prime 2 appears squared. The task is to find the first integer that begins a run of four consecutive integers, each having exactly four distinct prime factors.
</p>
<p>
The workhorse here is <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a>: to factor n, I test candidate divisors d from 2 upward, and each time d divides n I record it and strip out every copy. The first efficiency observation is that I only need to test divisors up to the square root of n - if n had a factor larger than its square root, the cofactor would be smaller than the square root and would already have been found, so whatever survives the loop above 1 is itself a prime factor. The second, equally important observation is that no <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">sieve</a> or precomputed table is needed: the answer (134,043) is small, so a plain linear scan suffices. Counting distinct prime factors of n costs O(sqrt(n)), and scanning candidates up to the answer A while testing windows of length n gives an overall cost of about O(A * sqrt(A)) - a few million operations, which is trivial at this scale.
</p>
<h3>Solution Approach</h3>
<h4>Linear Scan with Trial Division (Python and C)</h4>
<p>
Both files implement the same algorithm, so I describe them together. There are two parts: a function that counts the distinct prime factors of one integer, and a search loop that finds the first window of n consecutive qualifying integers.
</p>
<p>
The counter uses <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> with in-place reduction. I begin at d = 2 and loop while d*d &lt;= n. When d divides n, I increment the count once, then drain out every copy of that factor with an inner loop (<code>while n % d == 0: n //= d</code>). Draining all copies is precisely what makes a separate primality test unnecessary: by the time d reaches a composite value such as 4, the factor 2 has already been fully stripped, so 4 can never divide the reduced n. Every d that successfully divides is therefore guaranteed prime. After the loop, if n still exceeds 1, that remainder is a prime larger than the square root of the original, so I count it as well. The result is exactly the number of distinct prime factors.
</p>
<p>
The search loop starts at number = 2 and increments by 1. For each starting position it checks whether number, number+1, ..., number+(n-1) all have exactly n distinct prime factors, using early exit: the instant one element fails, the window is abandoned. In C this is a flag (<code>all_match</code>) plus a <code>break</code>; in Python it is <code>not any(prime_factor_count(number + i) != n for i in range(0, n))</code>, where <code>any</code> short-circuits identically.
</p>
<p>
Both programs take n as a command-line argument, so a single executable solves all three test cases (n=2, n=3, n=4) without modification. The Python version adds one layer of structure: <code>prime_factorization</code> returns a tuple of (prime, exponent) pairs and <code>prime_factor_count</code> simply returns its length. That is slightly more than this problem needs, but it leaves a reusable building block. The C version counts inline and omits the tuple machinery that C does not express naturally, which is marginally simpler and faster.
</p>
</article>