blob: 554da91e22a379b407ac7f699ae9b7f0aa685d43 (
plain) (
tree)
|
|
#!/usr/bin/perl
use strict;
use warnings;
use Math::Factor::XS qw/factors/;
use List::MoreUtils qw/uniq/;
my $n = $ARGV[0];
my %dups;
# have to go up to $n^2-ish because, for example, 2^12 reduces to both 4^6 and
# 8^4, but neither of those reduce to each other, and if $n is 8, you'll miss
# both of them.
for my $b (2..$n**2) {
my @bfactors = factors($b);
next unless @bfactors;
for my $a (2..$n) {
for my $bfact (@bfactors) {
my ($olda, $oldb) = ($a, $b);
my ($newa, $newb) = ($a**$bfact, $b / $bfact);
next unless $newa <= $n;
next unless $newb <= $n;
($olda, $oldb, $newa, $newb) = ($newa, $newb, $olda, $oldb)
if !exists $dups{"$newa^$newb"} && exists $dups{"$olda^$oldb"};
$dups{"$olda^$oldb"}{"$newa^$newb"} = 1;
$dups{"$olda^$oldb"}{$_} = 1 for keys %{ $dups{"$newa^$newb"} };
$dups{$_}{"$olda^$oldb"} = 1 for keys %{ $dups{"$newa^$newb"} };
$dups{"$newa^$newb"}{"$olda^$oldb"} = 1;
}
}
}
my $total = ($n - 2 + 1)**2;
for my $dup (keys %dups) {
my ($a, $b) = split /\^/, $dup;
next if $a > $n or $b > $n;
$total -= grep { my ($a, $b) = split /\^/, $_; $a <= $n && $b <= $n }
keys %{ $dups{$dup} };
for my $subdup (keys %{ $dups{$dup} }) {
$dups{$subdup} = {};
}
}
print "$total\n";
|