diff options
author | Jesse Luehrs <doy@tozt.net> | 2009-05-15 10:01:55 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2009-05-15 10:01:55 -0500 |
commit | 5afab29454b75fa55cc54fc32fa39b20aea75134 (patch) | |
tree | 2b43b56ccf75b6e8526c47dff83a2df300563d32 /029-broken.pl | |
parent | fecd0fa58cc1a57de109486d3138a3f279c3b355 (diff) | |
download | projecteuler-5afab29454b75fa55cc54fc32fa39b20aea75134.tar.gz projecteuler-5afab29454b75fa55cc54fc32fa39b20aea75134.zip |
add my slow solution to 29, and my broken attempt at a faster one
Diffstat (limited to '029-broken.pl')
-rwxr-xr-x | 029-broken.pl | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/029-broken.pl b/029-broken.pl new file mode 100755 index 0000000..554da91 --- /dev/null +++ b/029-broken.pl @@ -0,0 +1,41 @@ +#!/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"; |