# 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. my (%mark_for, %already_done); for 2 .. sqrt($max).Int -> $i { next if %already_done{$i}; my $x = $i; my $exp = 1; while ($x <= $max) { %already_done{$x} = 1; 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;