Shlomi Fish avatar Shlomi Fish committed 5ea826c

Some bug fixes.

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

Comments (0)

Files changed (1)

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;
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.