notes.html

problem 29 · 28 lines

<article>
<h3>Problem Analysis</h3>
<p>
The task is to count how many <em>distinct</em> values appear in the set of powers a<sup>b</sup> 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 2<sup>4</sup> = 4<sup>2</sup> = 16. To get the right count I must detect and discard these collisions.
</p>
<p>
The reason collisions occur, and the key to characterising them cheaply, is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic" rel="noopener noreferrer" target="_blank">fundamental theorem of arithmetic</a>: every integer above one has a unique factorisation into primes. If a base a factors as p<sub>1</sub><sup>e<sub>1</sub></sup> · p<sub>2</sub><sup>e<sub>2</sub></sup> · ..., then a<sup>b</sup> = p<sub>1</sub><sup>e<sub>1</sub>b</sup> · p<sub>2</sub><sup>e<sub>2</sub>b</sup> · ... Two powers are equal precisely when these prime-exponent maps match. That gives me a canonical <em>signature</em> - the tuple of (prime, scaled-exponent) pairs - that encodes equality of two potentially enormous numbers using only small integers. The point matters because 100<sup>100</sup> already has roughly 200 decimal digits and 1000<sup>1000</sup> about 3000, so direct comparison demands either arbitrary-precision arithmetic or a compact encoding.
</p>
<p>
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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Hash_table" rel="noopener noreferrer" target="_blank">hash set</a>, and report the set's size. There are roughly (a<sub>max</sub> - a<sub>min</sub> + 1) × (b<sub>max</sub> - b<sub>min</sub> + 1) insertions, each expected O(1), plus a factorisation cost per base. Factoring a single base by <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> is O(√a). So overall I expect O(a<sub>max</sub> · b<sub>max</sub>) for the insertions plus O(a<sub>max</sub> · √a<sub>max</sub>) for factoring - and at these sizes the insertion term dominates.
</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0 - Direct big-integer set, with prime-signature fallback (hand-rolled factoriser)</h4>
<p>
Both <code>p0029_s0.py</code> and <code>p0029_s0.c</code> branch on <code>min(a_max, b_max)</code> 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.
</p>
<p>
<strong>Small-range path.</strong> In Python this is a one-liner: <code>len({a**b for a in range(...) for b in range(...)})</code>. Python integers are arbitrary-precision, so there is no overflow, and the built-in <code>set</code> 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 10<sup>9</sup>, least significant limb first. For each base a I compute a<sup>b_min</sup> 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.
</p>
<p>
<strong>Large-range path.</strong> Here I factorise each base a by <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> (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 a<sup>b</sup>. In Python the signature is a tuple of <code>(prime, power * b)</code> pairs added to a <code>set</code>; in C it is encoded as a comma-separated string like <code>"2:6,5:3"</code> 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.
</p>
<h4>Algorithm 1 - Same dual-path strategy with a sieve-backed factoriser</h4>
<p>
<code>p0029_s1.py</code> and <code>p0029_s1.c</code> 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 √a<sub>max</sub> using the <a class="reference-source" href="https://github.com/kimwalisch/primesieve" rel="noopener noreferrer" target="_blank">primesieve</a> library (the <code>primes</code> function in Python, <code>primesieve_generate_primes</code> in C) and trial-divide only against that prime list. This is asymptotically the same as <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> 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.
</p>
</article>