# HG changeset patch # User Shlomi Fish # Date 1372954257 -10800 # Node ID 7cc6d7ad35ad692b824600a5531b7150e6ce1cca # Parent 408ff3d8ed668c15aa8ac7089fa5e12d62ac9138 Start experimenting with the factor elimination. diff --git a/project-euler/152/euler-152.pl b/project-euler/152/euler-152.pl --- a/project-euler/152/euler-152.pl +++ b/project-euler/152/euler-152.pl @@ -3,10 +3,13 @@ use strict; use warnings; +use v5.16; + use Math::BigRat only => 'GMP'; -use List::MoreUtils qw(any); +use List::MoreUtils qw(any uniq); -sub sq_frac + +sub slow_sq_frac { my (\$n) = @_; @@ -57,13 +60,15 @@ } my \$target = Math::BigRat->new('1/2'); -my \$limit = 80; +my \$limit = 35; my \$found_count = 0; # We exclude 2 because the target is divided by it. my @primes = (grep { is_prime(\$_) } (3 .. \$limit)); +my @sq_fracs = (map { \$_ ? slow_sq_frac(\$_) : \$_ } (0 .. \$limit)); + my %primes_lookup = (map { \$_ => 1 } @primes); my @remaining_sums; @@ -72,7 +77,7 @@ for my \$n (reverse(2 .. \$limit)) { - \$remaining_sums[\$n] = \$remaining_sums[\$n+1] + sq_frac(\$n); + \$remaining_sums[\$n] = \$remaining_sums[\$n+1] + \$sq_fracs[\$n]; } my @end_at; @@ -84,9 +89,9 @@ sub recurse { - my (\$start_from, \$so_far, \$sum) = @_; + my (\$to_check, \$so_far, \$sum) = @_; - # print "Checking: Start=\$start_from ; \$sum+[@\$so_far]\n"; + print "Checking: Start=@\$to_check ; \$sum+[@\$so_far]\n"; if (\$sum == \$target) { @@ -96,6 +101,13 @@ return; } + if (! @\$to_check) + { + return; + } + + my \$start_from = \$to_check->[0]; + if (\$sum + \$remaining_sums[\$start_from] < \$target) { # print "Remaining sum prune\n"; @@ -104,59 +116,85 @@ my \$factors = factorize(\$sum->denominator()); - if (any { \$end_at[\$_] <= \$start_from } @\$factors) + if (any { \$_ > 2 && \$end_at[\$_] <= \$start_from } @\$factors) { return; } + my %factors_lookup = (map { \$_ => 1 } @\$factors); + FIRST_LOOP: - foreach my \$first (\$start_from .. \$limit) + foreach my \$first_idx (keys(@\$to_check)) { - my \$new_sum = (\$sum + sq_frac(\$first))->bnorm(); + my \$first = \$to_check->[\$first_idx]; + my \$new_sum = (\$sum + \$sq_fracs[\$first])->bnorm(); if (\$new_sum > \$target) { return; } - if (\$primes_lookup{\$first}) - { - # It can never be balanced. - if (\$first > \$limit/2) + my @new_factors = uniq(grep { !exists(\$factors_lookup{\$_})} @{ factorize(\$new_sum->denominator()) }); + + my \$new_to_check = [@\$to_check[\$first_idx+1..\$#\$to_check]]; + my @new_factors_contains = (map { + my \$new_factor = \$_; + [ + grep + { \$new_to_check->[\$_] % \$new_factor == 0 } + keys @\$new_to_check + ] + } + @new_factors + ); + my %new_factors_contains_lookup = + (map { map { \$_ => 1 } @\$_ } @new_factors_contains); + + my @factors_not_contains = (grep + { !exists(\$new_factors_contains_lookup{\$_}) } + keys @\$new_to_check + ); + + my \$iter_factors_recurse = sub { + my (\$masks) = @_; + my \$idx = @\$masks; + if (\$idx == @new_factors) { - next FIRST_LOOP; + my @factors = sort {\$a <=> \$b } uniq (map { + my \$i = \$_; + grep { ((\$masks->[\$i]>>\$_)&0x1) } @{\$new_factors_contains[\$i]} + } (0 .. \$#\$masks)); + + 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]], + [@\$so_far, @\$new_to_check[@factors]], + \$new_new_sum->bnorm(), + ); + return; + } + foreach my \$new_mask (1 .. ((1 << @{\$new_factors_contains[\$idx]})-1)) + { + __SUB__->([@\$masks, \$new_mask]); } -=begin removed - my \$test_sum = \$new_sum->copy(); - my \$first_product = \$first*2; + return; + }; - while( - (\$test_sum->denominator() % \$first == 0) - ) - { - \$test_sum += Math::BigRat->new( - '1/' . (\$first_product * \$first_product) - ); + \$iter_factors_recurse->([]); - if (\$test_sum > \$target) - { - next FIRST_LOOP; - } - if ((\$first_product += \$first) > \$limit) - { - next FIRST_LOOP; - } - } -=end removed - -=cut - } - recurse(\$first+1, [@\$so_far, \$first], \$new_sum); + # recurse(\$first+1, [@\$so_far, \$first], \$new_sum); } return; } -recurse(2, [], Math::BigRat->new('0/1')); +# Filter out the large primes. +my @init_to_check = (grep { !exists(\$primes_lookup{\$_}) || \$_ < \$limit/2 } (2 .. \$limit)); +recurse([@init_to_check], [], Math::BigRat->new('0/1')); +