From 5afab29454b75fa55cc54fc32fa39b20aea75134 Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Fri, 15 May 2009 10:01:55 -0500
Subject: add my slow solution to 29, and my broken attempt at a faster one

---
 029-broken.pl | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
 create mode 100755 029-broken.pl

(limited to '029-broken.pl')

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";
-- 
cgit v1.2.3