Commits

Shlomi Fish committed 772e6d1

Some major optimisations that allow us to solve it quickly.

Still the initial problem.

What we did was treat every addend separately, and also trim
dead ends.

  • Participants
  • Parent commits 0e8edc6

Comments (0)

Files changed (1)

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

         return;
     }
 
-    my $factors = factorize($sum->denominator());
-
-    if (any { $_ > 2 && $end_at[$_] <= $start_from } @$factors)
+    if (any { $_ > 2 && $end_at[$_] <= $start_from } @{factorize($sum->denominator())})
     {
         return;
     }
 
-    my %factors_lookup = (map { $_ => 1 } @$factors);
-
     FIRST_LOOP:
     foreach my $first_idx (keys(@$to_check))
     {
         my $new_sum = ($sum + $sq_fracs[$first])->bnorm();
         if ($new_sum > $target)
         {
-            return;
+            next FIRST_LOOP;
         }
 
         my @new_factors = grep { $_ > 2 } uniq(@{ factorize($new_sum->denominator()) });
         {
             recurse(
                 $new_to_check,
-                [@$so_far, $first],
+                [sort { $a <=> $b } (@$so_far, $first)],
                 $new_sum,
             );
             next FIRST_LOOP;
 
             my %encountered_factors;
 
+            # my $sum_threshold = $target - $remaining_sums[$new_to_check->[0]];
+            my $sum_threshold = $target;
+
             my $iter_factors_recurse = sub {
-                my ($masks) = @_;
-                my $idx = @$masks;
+                my ($idx, $factor_idx, $factors_href, $new_new_sum) = @_;
 
+                if ($new_new_sum > $sum_threshold)
+                {
+                    return;
+                }
                 if ($idx == @new_factors)
                 {
-                    my @factors = sort {$a <=> $b } uniq (map {
-                        my $i = $_;
-                        @{$new_factors_contains[$i]}[grep { (($masks->[$i]>>$_)&0x1) } keys(@{$new_factors_contains[$i]})]
-                        } (0 .. $#$masks));
-
+                    my @factors = sort {$a <=> $b } keys(%$factors_href);
                     if (! $encountered_factors{join(',',@factors)}++)
                     {
-                        my $new_new_sum = $new_sum;
-
-                        foreach my $f (@factors)
-                        {
-                            $new_new_sum += $sq_fracs[$new_to_check->[$f]];
-                        }
-
                         recurse([@$new_to_check[@factors_not_contains]],
-                            [sort { $a <=> $b} @$so_far, $first, @$new_to_check[@factors]],
+                            [sort { $a <=> $b } (@$so_far, $first, @factors)],
                             $new_new_sum->bnorm(),
                         );
                     }
                     return;
                 }
 
-                foreach my $new_mask (1 .. ((1 << @{$new_factors_contains[$idx]})-1))
+                if ($factor_idx == @{$new_factors_contains[$idx]})
                 {
-                    __SUB__->([@$masks, $new_mask]);
+                    if ($new_new_sum->bnorm->denominator() % $new_factors[$idx] == 0)
+                    {
+                        return;
+                    }
+                    else
+                    {
+                        return __SUB__->($idx+1, 0, $factors_href, $new_new_sum);
+                    }
                 }
 
+                my $factor = $new_to_check->[$new_factors_contains[$idx][$factor_idx]];
+
+                if (!exists($factors_href->{$factor}))
+                {
+                    __SUB__->($idx, $factor_idx+1, {%$factors_href, $factor => 1}, $new_new_sum + $sq_fracs[$factor]);
+                }
+                __SUB__->($idx, $factor_idx+1, $factors_href, $new_new_sum);
+
                 return;
             };
 
-            $iter_factors_recurse->([]);
+            $iter_factors_recurse->(0, 0, +{}, $new_sum);
         }
 
         # recurse($first+1, [@$so_far, $first], $new_sum);
     return;
 }
 
-# Filter out the large primes.
-my @init_to_check = (grep { !exists($primes_lookup{$_}) || $_ < $limit/2 } (2 .. $limit));
+# Filter out the large primes and the primes which only have 2*p in the limit
+# and their product.
+my @init_to_check = (grep { (!(exists($primes_lookup{$_}) || ((($_&0x1) == 0) && exists($primes_lookup{$_>>1})))) || $_ < $limit/3 } (2 .. $limit));
 
 recurse([@init_to_check], [], Math::BigRat->new('0/1'));