notes.html
problem 70 · 12 lines
<article>
<h3>Problem Analysis</h3>
<p><a class="reference-source" href="https://en.wikipedia.org/wiki/Euler%27s_totient_function" rel="noopener noreferrer" target="_blank">Euler's totient function</a> phi(n) counts the positive integers up to n that are <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">relatively prime</a> to n - sharing no common factor with n other than 1. The function is <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplicative_function" rel="noopener noreferrer" target="_blank">multiplicative</a>, and for any <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> p we have phi(p) = p - 1 because every smaller number is coprime to a prime. When n is the product of two distinct primes p and q (a <a class="reference-source" href="https://en.wikipedia.org/wiki/Semiprime" rel="noopener noreferrer" target="_blank">semiprime</a>), the <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplicative_function" rel="noopener noreferrer" target="_blank">multiplicative</a> property gives the exact closed form phi(p*q) = (p-1)*(q-1). This formula is the linchpin of an efficient solution: it lets me compute the totient with no factorisation work at all.</p>
<p>The task is to minimise the ratio n/phi(n) subject to phi(n) being a digit-<a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a> of n. Minimising n/phi(n) means making phi(n) as close as possible to n. The general formula phi(n) = n * prod (1 - 1/p) over the distinct prime factors p of n means the ratio n/phi(n) equals the product of p/(p-1) over those same primes. Each distinct prime factor pushes the ratio above 1, and small primes push hardest: 2/1 = 2, 3/2 = 1.5, 5/4 = 1.25, and so on. To keep the ratio near 1 I want as few distinct prime factors as possible, and those factors should be large. A prime n would give the smallest possible ratio, but phi(prime) = prime - 1 can never be a <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a> of the prime (subtracting 1 changes the digit sum by 1, which breaks the divisibility-by-9 alignment that any digit rearrangement must preserve). The next best structure is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Semiprime" rel="noopener noreferrer" target="_blank">semiprime</a> n = p*q with both p and q large, ideally near sqrt(10^7). This insight collapses the search space: instead of testing all 10^7 candidates, I only test products of two primes drawn from a narrow band around the square root of the limit. The dominant cost is then sieving the primes once, an O(N log log N) operation, followed by a comparatively tiny pair search.</p>
<h3>Solution Approach</h3>
<h4>Semiprime Prime-Pair Search (Python and C, index 0)</h4>
<p>Both implementations share one algorithm: enumerate pairs of distinct primes (p1, p2) with p1 in the band [sqrt(limit)/2, sqrt(limit)], form n = p1*p2 and phi(n) = (p1-1)*(p2-1), test the <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a> condition, and track the pair giving the minimum ratio.</p>
<p>The band for p1 is derived algebraically. Because I require p2 > p1 to avoid double-counting and keep both primes distinct, and because p1*p2 must stay below the limit, p1 cannot exceed sqrt(limit) - otherwise p2 > p1 forces n above the limit. The lower bound sqrt(limit)/2 reflects that if p1 drops much below the square root, the matching p2 needed to reach a near-square product climbs out of range, and the band would otherwise contain only pairs whose ratio is provably worse than what I have already found near the square root. Inside the loop I set the upper bound for p2 to limit/p1 so that n stays under the limit, and I require p2 > p1 + 2 so the two primes are genuinely distinct (and not twins, which give a slightly worse ratio and rarely pass the permutation test).</p>
<p>The Python version drives the outer loop with a generator expression that filters a lazy prime stream, breaking once p1 exceeds the upper bound. The permutation test sorts the digit strings of n and phi(n) and compares them - concise and readable. The <a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#assignment-expressions" rel="noopener noreferrer" target="_blank">walrus operator</a> binds <code>number</code> and <code>totient</code> inline so each is computed once and reused for the ratio comparison.</p>
<p>The C version pre-computes all primes up to the limit with a classical <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a> into a flat array, then walks index ranges. It first locates the starting index for p1 (the first prime above min_prime_1) and, for each p1, the starting index for p2, so both inner and outer loops are simple array scans with an early <code>break</code> whenever a bound is exceeded. The permutation test uses a 10-element digit-frequency array: it increments counts while consuming the digits of n and decrements while consuming the digits of phi(n); if all ten counts are zero, the two numbers are permutations. This is allocation-free and avoids string handling entirely.</p>
</article>