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?
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;
}
# vim: expandtab shiftwidth=4 ft=perl6