Project Euler, Problem 29: Distinct Powers (Binary 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

The tricky part of this problem was getting JavaScript to handle 𝔹𝕀𝔾^® numbers. Thankfully the BigInt is here and it made things a lot easier. I made two helper functions: one to put my numbers in an array and another to trim extra numbers after the fact.

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

A major breakthrough on bringing the speed down for this problem was using a binary search for inserting the numbers into the array. Another was trimming the array of extra numbers instead of searching for duplicates before inserting. Using a binary search before the fact only cost me about 1ms though.

103,541