Project Euler Problem 29 Solution

Project Euler Problem 29 Statement

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Solution

Project Euler version

A lazy solution that gives you an answer

r = range(2, 101)
print(len({a**b for a in r for b in r}))

A more profound and rewarding solution for the HackerRank version

The HackerRank solution is less intuitive than simply storing all $a^b$ in a set, it's a way of reducing the amount of repeated work and condensing the counting.

On HackerRank, we need to handle multiple queries and manage time constraints that discourage a brute-force solution shown above. This technique tries to:

Skip redundant checks: If $a$ is already recognized as some power $x^y$, we avoid recomputing powers from that base (because they'd overlap with powers of $x$).
Track exponents: By using the powers.update(...) line, the code tracks how many exponent-values go out of range (beyond $N$). This helps the code efficiently sum up how many distinct exponent "spots" come from each base.

The Setup

N = int(input())
seen = [False]*(N+1)
s = 0

We read the value of N and create a Boolean array (indexed 0 to N) initialized to False. This array serves to mark bases as "already seen." sis our accumulator for the final count of distinct terms.

The Outer Ring

for a in range(2, N+1) checks each possible base $a$ from 2 to $N$.
if not seen[a] only proceeds if $a$ has not already been flagged as some power of a smaller base. If seen[a] is True, that means $a$ itself is $x^y$ for some smaller $x$, so the code skips heavy computation.

The Inner Ring and "Seen" Powers

b = 2: Start exponents from 2 (since 1 is not considered in the set).
while a**b <= N: continues to compute $a^b$ while the result is within $[1, N]$.
- seen[a**b] = True: Mark the number $a^b$ as 'seen,' indicating it's a power encountered by this base. Then, in future iterations of the outer loop, if we come across a^b as a base itself, we'll know it was already covered.
- powers.update(p for p in range(2*b, N*b+1, b) if p > N): This line iterates over multiples of $b$ from $2b$ to $Nb$ (stepping by $b$) and only adds those multiples that exceed $N$. Essentially, this is tracking exponent 'spots' that go beyond the upper limit $N$.
b += 1: Increments the exponent and repeats until $a^b > N$.

Accumulating a total into `s`

s+= len(powers) + N - 1

The term len(powers) counts how many "exponent multiples" were discovered that go beyond the usual range. The term (N - 1) counts the "regular" powers that ensures each base from 2 up to $N$ is counted correctly for exponents from 2 to $N$. Combined, this contributes to a final tally of all the distinct $a^b$.

Finally, print(s) outputs the count, which should match the number of distinct terms $\{a^b\}$ for $2 \leq a,b \leq N$.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 29

HackerRank Project Euler 29 increases the limit to 2 ≤ a,b ≤ 10⁵.

Python Source Code

N = int(input())
seen = [False]*(N+1)
s = 0
for a in range(2, N+1):
    if not seen[a]:
        b = 2 
        powers = set()
        while a**b <= N:
            seen[a**b] = True
            powers.update(p for p in range(2*b, N*b+1, b) if p > N)
            b+= 1
        s+=len(powers) + N-1
print(s)

Last Word

Nothing to see here, folks.