Distinct powers

Solved on Sat, 19 Dec 2020

Uploaded on Sat, 19 Dec 2020

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?

Brute-force solution


def brute():
    dist_powers = []
    for a in range(lim_bottom, (lim_up + 1)):
        for b in range(lim_bottom, (lim_up + 1)):
            power = a**b
            if power not in dist_powers:
                dist_powers.append(power)
    print(len(dist_powers))

Execution


lim_bottom = 2
lim_up = 100

brute()

#104859th

Output


brute_force: 9183