Home > Programming > Project euler 29: Distinct powers

## Project euler 29: Distinct powers

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

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=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 ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

```def distpowers(n):
a={2} # initialize the set
d={}  # map for total number of elements for each power
s=[0 for x in range(n + 1)]
for i in range(1, 8):
for j in range(2, n + 1):
d[i]=len(a)
tot = 0
for i in range (2, n + 1):
if s[i] == 0:
prod = i
power = 0
while prod <= n:
s[prod] = 1
prod *= i
power += 1
tot += d[power]
print (tot)

if __name__ == '__main__':
distpowers(100)

```

Time complexity O(8 * n) ~ O(n)
Space complexity O(n)