Problem Analysis
The task is to count how many distinct values appear in the set of powers ab as a and b each range over an interval. If every pair (a, b) produced a different number, the answer would just be the count of pairs. It does not, because different bases and exponents can coincide - the canonical small example is 24 = 42 = 16. To get the right count I must detect and discard these collisions.
The reason collisions occur, and the key to characterising them cheaply, is the fundamental theorem of arithmetic: every integer above one has a unique factorisation into primes. If a base a factors as p1e1 · p2e2 · ..., then ab = p1e1b · p2e2b · ... Two powers are equal precisely when these prime-exponent maps match. That gives me a canonical signature - the tuple of (prime, scaled-exponent) pairs - that encodes equality of two potentially enormous numbers using only small integers. The point matters because 100100 already has roughly 200 decimal digits and 10001000 about 3000, so direct comparison demands either arbitrary-precision arithmetic or a compact encoding.
In either representation, the algorithm is the same: generate every power, reduce it to a hashable key (the raw big-integer value or its prime signature), insert each key into a hash set, and report the set's size. There are roughly (amax - amin + 1) × (bmax - bmin + 1) insertions, each expected O(1), plus a factorisation cost per base. Factoring a single base by trial division is O(√a). So overall I expect O(amax · bmax) for the insertions plus O(amax · √amax) for factoring - and at these sizes the insertion term dominates.
Solution Approach
Algorithm 0 - Direct big-integer set, with prime-signature fallback (hand-rolled factoriser)
Both p0029_s0.py and p0029_s0.c branch on min(a_max, b_max) against a threshold of 100. The idea is to use the simplest correct method for small bounds and the memory-efficient method for large ones.
Small-range path. In Python this is a one-liner: len({a**b for a in range(...) for b in range(...)}). Python integers are arbitrary-precision, so there is no overflow, and the built-in set handles hashing and equality of the big values. In C there is no native big integer, so I built one: numbers live in arrays of 32-bit limbs in base 109, least significant limb first. For each base a I compute ab_min by repeated multiplication, then obtain each successive power by a single multiply by a. Each value is serialised to a decimal string and inserted into a custom string-keyed hash set; the final element count is the answer.
Large-range path. Here I factorise each base a by trial division (the inner loop tries divisors d while d · d ≤ n), producing (prime, exponent) pairs. For each exponent b I scale every exponent by b to form the signature of ab. In Python the signature is a tuple of (prime, power * b) pairs added to a set; in C it is encoded as a comma-separated string like "2:6,5:3" and inserted into the same hash table. This path never builds a large number - it works entirely with small integers - which is why it scales gracefully to a = b = 1000.
Algorithm 1 - Same dual-path strategy with a sieve-backed factoriser
p0029_s1.py and p0029_s1.c are algorithmically identical to Algorithm 0. The only difference is the factorisation step: instead of trial-dividing against every integer, they first generate all primes up to √amax using the primesieve library (the primes function in Python, primesieve_generate_primes in C) and trial-divide only against that prime list. This is asymptotically the same as trial division against all integers but avoids wasted attempts on composite divisors. The reason for keeping both variants is to let the benchmark answer whether factorisation is the bottleneck - and as the timings show, it is not, because hash-set insertion dominates.