Problem Analysis
Euler's totient function phi(n) counts the positive integers up to n that are relatively prime to n - sharing no common factor with n other than 1. The function is multiplicative, and for any prime 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 semiprime), the multiplicative 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.
The task is to minimise the ratio n/phi(n) subject to phi(n) being a digit-permutation 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 permutation 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 semiprime 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.
Solution Approach
Semiprime Prime-Pair Search (Python and C, index 0)
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 permutation condition, and track the pair giving the minimum ratio.
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).
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 walrus operator binds number and totient inline so each is computed once and reused for the ratio comparison.
The C version pre-computes all primes up to the limit with a classical Sieve of Eratosthenes 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 break 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.