29 - Distinct Powers

Problem

Consider all integer combinations of $a^b$ for $2 \le a \le 5$ and $2 \le b \le 5$:

$$ \begin{array}{rl@{\qquad}rl@{\qquad}rl@{\qquad}rl} 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{array} $$

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 \le a \le 100$ and $2 \le b \le 100$?

Easy for Uiua

Uiua is extremely handy for this problem. For the example, notice that this is a table of powers defined by two ranges from $2-5.$ We can visualize this with bw join on a table.

    ⇡₂5 ⇡₂5
[2 3 4 5]
[2 3 4 5]

    ⊞˜⊂ ⇡₂5 ⇡₂5
╭─
╷ 2 2  2 3  2 4  2 5
╷ 3 2  3 3  3 4  3 5
  4 2  4 3  4 4  4 5
  5 2  5 3  5 4  5 5
                     ╯

To get the same representation, we use backward on join. You can try skipping it to see what happens.

So, we see that the arguments at each table element are the base and the power. Instead of bw couple, the table function can simply be pow. Let's trans it to match the problem example.

    ⍉ ⊞ⁿ ⇡₂5 ⇡₂5
╭─
╷  4   8  16   32
   9  27  81  243
  16  64 256 1024
  25 125 625 3125
                  ╯

Yup. That matches perfectly.

At this point, we would simply deshape to flatten the results into an array, dedup to remove duplicates and then count them up with len.

# Deshape
    ♭ ⍉ ⊞ⁿ ⇡₂5 ⇡₂5
[4 8 16 32 9 27 81 243 16 64 256 1024 25 125 625 3125]
# Dedup
    ◴ ♭ ⍉ ⊞ⁿ ⇡₂5 ⇡₂5
[4 8 16 32 9 27 81 243 64 256 1024 25 125 625 3125]
# Count
    ⧻ ◴ ♭ ⍉ ⊞ⁿ ⇡₂5 ⇡₂5
15

And that agrees with the example.

Cleanup

We can modify table with self to skip creating two ranges.

    ⧻◴♭⍉ ˙⊞ⁿ ⇡₂5
15

And trans was just for show.

    ⧻◴♭ ˙⊞ⁿ ⇡₂5
15

Solution

We simply extend the range to $100$ from our example program.

    ⧻◴♭ ˙⊞ⁿ ⇡₂100
9183

Fast?

    ⊙◌⍜now(⧻◴♭ ˙⊞ⁿ ⇡₂100)
0.0046732425689697266

Yuss, 4 milliseconds. As expected for simple calculations.