notes.html
problem 5 · 105 lines
<article>
<h3>Problem Analysis</h3>
<p>
A number "evenly divisible by all of the numbers from 1 to N" is exactly the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of the set {1, 2, ..., N}: the smallest positive integer that has every member of the set as a
divisor. So the smallest positive number divisible by all of 1..N is precisely the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of 1..N, and by definition nothing smaller can work.
</p>
<p>
The tool that makes this tractable is the identity lcm(a, b) = a × b / gcd(a, b), in which
the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
is the largest integer dividing both a and b. This identity lets me build the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of a whole set as a sequence of pairwise combinations, threading a running accumulator through the
range. Each pairwise step needs only one
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>,
which the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Euclidean_algorithm" rel="noopener noreferrer" target="_blank">Euclidean algorithm</a>
computes in O(log(min(a, b))) steps, so the overall cost is O(N log N) bit operations - negligible
here.
</p>
<p>
One subtlety matters for scale. By the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_factorization" rel="noopener noreferrer" target="_blank">prime factorisation</a>
view, the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of 1..N is the product, over every prime p up to N, of the highest
<a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_power" rel="noopener noreferrer" target="_blank">prime power</a>
of p not exceeding N, so the result grows rapidly. For N = 20 it fits in 32 bits, but for the
extra cases (N up to 100) it reaches 40+ decimal digits, far beyond any native integer type - so I
need
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>.
</p>
<h3>Solution Approach</h3>
<h4>
Iterative
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
via the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
(Python and C, index 0)
</h4>
<p>
Both files implement the same algorithm: start with a running result of 1 (the identity element
for the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>),
then for each y from 2 to N replace result with the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of result and y. After the loop, result equals the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of 1..N.
</p>
<p>
In the <strong>Python solution</strong> the entire computation is a single
<code>functools.reduce</code> over <code>range(2, n + 1)</code> with initial accumulator 1 and the
lambda <code>x * y // math.gcd(x, y)</code> - a direct transcription of the identity. I rely on
Python's built-in
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision integers</a>,
so multiplying and floor-dividing huge numbers just works with no special handling. I chose
<code>math.gcd</code> over a hand-written loop because the standard-library
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
is implemented in C and is faster. I also write <code>x * y // gcd</code> (multiply first, then
divide) rather than <code>x // gcd * y</code>; both are exact because the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
divides x, but the chosen form mirrors the textbook identity directly.
</p>
<p>
In the <strong>C solution</strong> I have no native big integer, so I implemented a minimal
<code>BigInt</code>: an array of 32-bit limbs in
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
order (least-significant limb first), base 2^32. Three primitives drive everything:
</p>
<ul>
<li><code>bi_div_small</code> divides the <code>BigInt</code> by a small value and returns the
remainder, walking limbs from most significant to least and carrying the remainder forward in a
64-bit intermediate (<code>(rem << 32) | limb</code>).</li>
<li><code>bi_mul_small</code> multiplies the <code>BigInt</code> by a small value, walking limbs
from least to most significant and propagating carry - which is why
<a class="reference-source" href="https://en.wikipedia.org/wiki/Endianness" rel="noopener noreferrer" target="_blank">little-endian</a>
order is convenient.</li>
<li><code>bi_lcm_small</code> computes the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Least_common_multiple" rel="noopener noreferrer" target="_blank">least common multiple</a>
of result and y in place: it copies result, reduces the copy
<a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modulo</a>
y with <code>bi_div_small</code> to get a small remainder, finds the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
of that remainder and y with the native <code>gcd_ll</code>, then divides result by that
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
and multiplies by y.</li>
</ul>
<p>
The crucial design choice in C is that I never implement a big-integer
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>.
Because gcd(a, b) = gcd(a mod b, b) and y is small, one
<a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modular</a>
reduction step turns the big operand into a small one, after which the whole
<a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a>
runs in native <code>long long</code> arithmetic. Finally <code>bi_to_str</code> converts the
result to decimal by repeated division by 10, collecting digits least-significant-first into a
stack buffer and reversing them into a heap-allocated string.
</p>
</article>