notes.html

problem 26 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
When you carry out long division to express the unit fraction 1/d as a decimal, the digits after the point either terminate or eventually fall into a repeating loop. The fraction terminates exactly when d's only prime factors are 2 and 5 - the prime factors of our base, 10. For every other d, the expansion settles into a purely repeating cycle, and the length of that cycle is a well-studied number-theoretic quantity called the <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplicative_order" rel="noopener noreferrer" target="_blank">multiplicative order</a> of 10 modulo d. The <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplicative_order" rel="noopener noreferrer" target="_blank">multiplicative order</a> of a base a modulo n is the smallest positive integer k such that a^k is congruent to 1 modulo n - written a^k = 1 (mod n). It exists if and only if a and n are <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">coprime</a> (their <a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a> is 1). The reason this maps onto our problem is that the remainders produced during long division of 1/d are precisely the sequence 10^k mod d, and the cycle closes the first time that remainder returns to its starting value of 1.
</p>
<p>
The observation that makes the search efficient is a bound on how long a cycle can be. The remainders in the long-division process are all in the range 1 to d-1, so the cycle length can be at most d-1. When d is prime, <a class="reference-source" href="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem" rel="noopener noreferrer" target="_blank">Fermat's little theorem</a> tells us the order divides d-1, and the maximum achievable is exactly d-1. This means the longest cycle below a limit L must come from a large d near L, because a small d simply cannot produce a long enough cycle. I exploit this by scanning the top of the range downward rather than testing every d from 2 upward. Computing the order by direct simulation costs O(d) per candidate, and restricting the scan to the top tenth of the range makes the whole search O(L/10 * L) - trivially fast for L = 1000.
</p>
<h3>Solution Approach</h3>
<h4>Multiplicative-Order Search by Simulation (Python and C)</h4>
<p>
Both files implement the same algorithm in two languages. The heart of it is <code>multiplicative_order(a, modulus)</code>: I start with a remainder <code>r = 1</code> and repeatedly apply <code>r = r * a % modulus</code>, counting each step until <code>r</code> returns to 1. The step count at that moment is the cycle length. I cap the loop at <code>modulus - 1</code> iterations because, by Fermat's argument above, the order can never exceed that - and if the loop finishes without returning to 1, no order exists and I return <code>None</code> (or <code>-1</code> in C).
</p>
<p>
Before invoking the order computation I filter with a <a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a> check: if <code>gcd(d, 10) != 1</code>, then d shares a factor of 2 or 5 with the base, the order does not exist, and the simulation loop would never terminate by finding <code>r == 1</code>. Skipping these candidates is both a correctness guard and a small performance win. The Python version uses <code>math.gcd</code>; the C version implements the <a class="reference-source" href="https://en.wikipedia.org/wiki/Euclidean_algorithm" rel="noopener noreferrer" target="_blank">Euclidean algorithm</a> by hand in a tight <code>while</code> loop.
</p>
<p>
The search window covers the top 10% of the range (with a floor of 10 iterations so tiny limits like the dev case of 10 still examine enough candidates). I justify this restriction with the cycle-length bound: a d below L/10 can produce a cycle no longer than L/10, which will always be beaten by a large d near L carrying a near-maximal cycle. The Python solution feeds a generator of <code>(cycle_length, d)</code> tuples into <code>max()</code>, relying on lexicographic tuple comparison to maximise length first and break ties toward the larger d. The C solution tracks <code>best_len</code> and <code>best_d</code> explicitly, encoding the identical tie-break in a conditional. Both take the limit as a runtime argument so the same binary handles the dev and main cases without recompilation.
</p>
</article>