Commits

Shlomi Fish committed 108d0a2

More, but still too slow.

Comments (0)

Files changed (1)

project-euler/152/euler-152.pl

 
 use Math::BigRat only => 'GMP';
 
+sub sq_frac
+{
+    my ($n) = @_;
+
+    return Math::BigRat->new('1/' . ($n*$n));
+}
+
 sub is_prime
 {
     my ($n) = @_;
 
 my %primes_lookup = (map { $_ => 1 } @primes);
 
+my @remaining_sums;
+
+$remaining_sums[81] = 0;
+
+for my $n (reverse(2 .. 80))
+{
+    $remaining_sums[$n] = $remaining_sums[$n+1] + sq_frac($n);
+}
+
 sub recurse
 {
     my ($start_from, $so_far, $sum) = @_;
 
-    # print "Checking: Start=$start_from ; $sum+[@$so_far]\n";
+    print "Checking: Start=$start_from ; $sum+[@$so_far]\n";
 
     if ($sum == $target)
     {
         return;
     }
 
+    if ($sum + $remaining_sums[$start_from] < $target)
+    {
+        return;
+    }
+
     FIRST_LOOP:
     foreach my $first ($start_from .. $limit)
     {
-        my $new_sum = $sum + Math::BigRat->new('1/' . ($first * $first));
+        my $new_sum = $sum + sq_frac($first);
         if ($new_sum > $target)
         {
             return;
                 next FIRST_LOOP;
             }
 
+=begin removed
             my $test_sum = $new_sum->copy();
             my $first_product = $first*2;
             
                     next FIRST_LOOP;
                 }
             }
+=end removed
+
+=cut
         }
         recurse($first+1, [@$so_far, $first], $new_sum);
     }
+
+    return;
 }
 
 recurse(2, [], 0);