Home / Project Euler / Problem 29 - Distinct Powers

Published: March 11, 2024

Project Euler

Problem 29 - Distinct Powers

Problem

This problem comes from Project Euler 29

Problem

Consider all integer combinations of aba^b for 2≤a≤52 \leq a \leq 5 and 2≤b≤52 \leq b \leq 5

22=4,23=8,24=16,25=3232=9,33=27,34=81,35=24342=16,43=64,44=256,45=102452=25,53=125,54=625,55=3125\begin{matrix} 2^2=4, &2^3=8, &2^4=16, &2^5=32\\ 3^2=9, &3^3=27, &3^4=81, &3^5=243\\ 4^2=16, &4^3=64, &4^4=256, &4^5=1024\\ 5^2=25, &5^3=125, &5^4=625, &5^5=3125 \end{matrix}

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 aba^b for 2≤a≤1002 \leq a \leq 100 and 2≤b≤1002 \leq b \leq 100

Solution

I decided to go with the most straight-forward solution.

  1. For 2≤a≤1002 \leq a \leq 100 and 2≤b≤1002 \leq b \leq 100 , calculate aba^b
  2. Put the result into a set, so that it automatically removes duplicates
  3. Print the length of the set

Code

# Project Euler: Problem 29
# Distinct Powers

ab = set()

for a in range(2, 101):
    for b in range(2, 101):
        ab.add(a**b)

print(len(ab))