Commits

Shlomi Fish committed 5ea826c

Some bug fixes.

However, now it takes too much time and finds too many combinations.

  • Participants
  • Parent commits e45f0bd

Comments (0)

Files changed (1)

File project-euler/152/euler-152-take2.pl

     {
         print "Processing $p\n";
         my @products = (map { $p * $_ } (1 .. int($limit/$p)));
+        my @sq = (map { $_ * $_ } @products);
 
-        my $lcm = Math::BigInt::blcm(map { $_ * $_ } @products);
+        my $lcm = Math::BigInt::blcm(@sq);
         print "LCM=$lcm\n";
-        my $mod = $lcm / $p;
+        my $bef_mod = $lcm;
+        while ($bef_mod % $p == 0)
+        {
+            $bef_mod /= $p;
+        }
 
-        my @numers = map { $lcm / $_ } @products;
+        my $mod = $lcm / $bef_mod;
+
+        my @numers = map { $lcm / $_ } @sq;
         my @combos;
 
         my @rev_sums;
             }
         }
 
+        my $half_lcmed_limit = ($lcm>>1);
+
         my $recurse = sub {
             my ($i, $sum, $combo_so_far) = @_;
             # print "Combo=@$combo_so_far\n";
-            if ($i == @products)
+            if ($i == @sq)
             {
                 return;
             }
                 push @combos, $combo_so_far;
                 return;
             }
-            if ($rev_sums[$i+1] < $mod-$m)
+            if ($rev_sums[$i+1] < $mod-$m or $sum >= $half_lcmed_limit)
             {
                 # print "Flavoo = {$i}\n";
                 return;