# Distinct powers

Author: Flavio Poletti

https://projecteuler.net/problem=29

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 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 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Source code: prob029-polettix.pl

```use v6;

# Range upper limit, defaults to challenge's value
my \$max = @*ARGS.shift || 100;

# Integers up to the square root of the maximum value may lead to
# colliding items in the whole list, so we have to count them
# properly in order to get rid of duplicates. For example,
#
#    2**8=256 is equal to 16**2
#
# In addition to this, some items under the square root might
# lead to another kind of duplication. For example,
#
#    2**4=16  is equal to  4**2
#
# Hence, we'll skip the latter completely in our analysis from 2
# to the square root, and count the former according to the possible
# exponents.
for 2 .. sqrt(\$max).Int -> \$i {

my \$x = \$i;
my \$exp = 1;
while (\$x <= \$max) {
for 2 .. \$max -> \$f {
%mark_for{\$i} ||= {}; # avoid autovivification for now...
%mark_for{\$i}{\$f * \$exp} = 1;
}
++\$exp;
\$x *= \$i;
}
}

# Now, every element not already considered contributes only with
# unique elements. We have to remember that ranges start from 2, so
# we have to subtract 1 from \$max
my \$count = (\$max - 1 - %already_done.keys) * (\$max - 1);

# Then, we add the unique elements from what we analysed before,
# simply counting the number of elements that could potentially collide
for %mark_for.values -> \$v {
\$count += \$v.elems;
}

\$count.say;

```