# Distinct powers

Author: Gerhard R

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-gerdr.pl

```use v6;

# compute number of unique powers a**b with bases \a in range 2..A
# and exponents \b in range 2..B

sub count-naively(Int \$A, Int \$B) {
+(2..\$A X=> 2..\$B).classify({ .key ** .value })
}

sub count-smartly(Int \$A, Int \$B) {
my (%powers, %count);

# find bases which are powers of a preceding root base
# store decomposition into base and exponent relative to root
for 2..Int(sqrt \$A) -> \$a {
next if \$a ~~ %powers;
%powers{\$a, \$a**2, \$a**3 ...^ * > \$A} = \$a X=> 1..*;
}

# count duplicates
for %powers.values -> \$p {
for 2..\$B -> \$e {
# raise to power \e
# classify by root and relative exponent
++%count{\$p.key => \$p.value * \$e}
}
}

# add +%count as one of the duplicates needs to be kept
return (\$A - 1) * (\$B - 1) + %count - [+] %count.values;
}

sub cross(@a, @b) { @a X @b }
sub dups(@a) { @a - @a.uniq }
sub count-feedly(Int \$A, Int \$B) {
2..Int(sqrt \$A) \
==> map -> \$a { (\$a, \$a**2, \$a**3 ...^ * > \$A) Z=> (\$a X 1..*).tree } \
==> reverse() \
==> hash() \
==> values() \
==> cross(2..\$B) \
==> map -> \$n, [\$r, \$e] { (\$r) => \$e * \$n } \
==> dups() \
==> ((\$A - 1) * (\$B - 1) - *)();
}

sub bench(|) {
my \$start = now;
my \$result = callsame;
my \$end = now;
return \$result, round (\$end - \$start) * 1000;
}

multi MAIN(Int \$N, Bool :\$verify, Bool :\$feeds) {
nextwith(\$N, \$N, :\$verify, :\$feeds)
}

multi MAIN(Int \$A = 100, Int \$B = 100, Bool :\$verify, Bool :\$feeds) {
&count-naively.wrap(&bench);
&count-smartly.wrap(&bench);
&count-feedly.wrap(&bench);

my (\$result, \$runtime) = (\$feeds ?? &count-feedly !! &count-smartly)(\$A, \$B);
say \$result;

printf "expected %u [%ums]\n", count-naively \$A, \$B if \$verify;
}

```