Project Euler, Problem 29: Distinct Powers (Linear Search/Insert)

Consider all integer combinations of $a^{b}$ for $2 \leq a \leq 5$ and $2 \leq b \leq 5$ :

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

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 \leq a \leq 100

and

2 \leq b \leq 100

469 ms

The tricky part of this problem was getting JavaScript to handle 𝔹𝕀𝔾^® numbers. Thankfully the BigInt is here and it made things a bit easier. I made two helper functions to put my numbers in an array and another to check if my numbers were in the array.

I run two nested for loops and compute every power, checking and inserting as I go.

103,541