Commits

Shlomi Fish committed 2bb76a8

More progress

Comments (0)

Files changed (2)

project-euler/152/analysis2.txt

 
 Must have «2» otherwise the sum cannot hold, so:
 
+After 2:
+3 => 119246400
+4 => 67076100
+5 => 42928704
+6 => 29811600
+7 => 21902400
+8 => 16769025
+9 => 13249600
+10 => 10732176
+12 => 7452900
+13 => 6350400
+14 => 5475600
+15 => 4769856
+18 => 3312400
+20 => 2683044
+21 => 2433600
+24 => 1863225
+28 => 1368900
+30 => 1192464
+35 => 876096
+36 => 828100
+39 => 705600
+40 => 670761
+42 => 608400
+45 => 529984
+52 => 396900
+56 => 342225
+60 => 298116
+63 => 270400
+70 => 219024
+72 => 207025
+TARGET ==
+268304400
 
+Must have «3» otherwise the sum cannot be reached, so:
+
+After 2+3:
+
+4 => 67076100
+5 => 42928704
+6 => 29811600
+7 => 21902400
+8 => 16769025
+9 => 13249600
+10 => 10732176
+12 => 7452900
+13 => 6350400
+14 => 5475600
+15 => 4769856
+18 => 3312400
+20 => 2683044
+21 => 2433600
+24 => 1863225
+28 => 1368900
+30 => 1192464
+35 => 876096
+36 => 828100
+39 => 705600
+40 => 670761
+42 => 608400
+45 => 529984
+52 => 396900
+56 => 342225
+60 => 298116
+63 => 270400
+70 => 219024
+72 => 207025
+TARGET ==
+149058000

project-euler/152/euler-152-take3-part2.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt (only => 'GMP');
+use List::Util qw(sum);
+use List::MoreUtils qw(all);
+
+sub is_prime
+{
+    my ($n) = @_;
+
+    if ($n <= 1)
+    {
+        return 0;
+    }
+
+    my $top = int(sqrt($n));
+
+    for my $i (2 .. $top)
+    {
+        if ($n % $i == 0)
+        {
+            return 0;
+        }
+    }
+
+    return 1;
+}
+
+my $MIN = 3;
+my $MAX = 80;
+
+my (@keys, $lcm, @ints, $target);
+
+my @primes = (grep { is_prime($_) } (3 .. $MAX));
+my %primes_lookup = (map { $_ => 1 } @primes);
+
+my @init_to_check = (grep { (!(exists($primes_lookup{$_}) || ((($_&0x1) == 0) && exists($primes_lookup{$_>>1})))) || $_ < $MAX/3 } ($MIN .. $MAX));
+
+@keys=(
+    4,
+    5,
+    6,
+    7,
+    8,
+    9,
+    10,
+    12,
+    13,
+    14,
+    15,
+    18,
+    20,
+    21,
+    24,
+    28,
+    30,
+    35,
+    36,
+    39,
+    40,
+    42,
+    45,
+    52,
+    56,
+    60,
+    63,
+    70,
+    72,
+);
+
+sub calc_stuff
+{
+    $lcm = Math::BigInt::blcm(map { $_ * $_ } @keys) . '';
+
+    @ints = (map { $lcm / ($_ * $_) } @keys);
+
+    $target = $lcm * (1 / 2 - 1 / (2*2) - 1 / (3*3));
+
+    return;
+}
+
+calc_stuff();
+
+=begin Removed
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 100 == 0 } keys(@keys)];
+calc_stuff();
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 2 == 0 } keys(@keys)];
+calc_stuff();
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 7 == 0 } keys(@keys)];
+calc_stuff();
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 9 == 0 } keys(@keys)];
+calc_stuff();
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 15 != 1 } keys(@keys)];
+calc_stuff();
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 4 == 0 } keys(@keys)];
+calc_stuff();
+
+# Deduced by semi-manual deduction.
+@keys = @keys[grep { $ints[$_] % 17 != 15 } keys(@keys)];
+calc_stuff();
+
+=end Removed
+
+=cut
+
+my @must_have = (4,5,6,7,9,10,12,15,20,28,30,35,36,45);
+
+my %must_have_lookup = (map { $_ => 1 } @must_have);
+
+my $found = 1;
+
+MAIN_TRIM:
+while ($found)
+{
+    $found = 0;
+
+    if (@keys == 41)
+    {
+        # last MAIN_TRIM;
+    }
+
+    TRIM_STUFF:
+    for my $n ($MIN .. 208_000)
+    {
+        print "N == $n ; NumKeys == ", scalar(@keys), "\n";
+
+        # mod is modulo
+        my %mods_hash;
+        foreach my $mod (grep { $_ } map { $_ % $n } @ints)
+        {
+            $mods_hash{"$mod"} ||= {count => 0, can_be_formed => 0,};
+            $mods_hash{"$mod"}{count}++;
+        }
+        my %agg_mods;
+
+        foreach my $mod (keys(%mods_hash))
+        {
+            foreach my $c (1 .. $mods_hash{$mod}{count})
+            {
+                my $agg_mod = (($mod*$c) % $n);
+                $agg_mods{$agg_mod} ||= {};
+                $agg_mods{$agg_mod}{$mod} = 1;
+            }
+        }
+        my $target_mod = $lcm % $n;
+
+        my @mods = sort { $a <=> $b } keys(%agg_mods);
+
+        if ((@mods == $n) || (@mods == $n-1) ||
+            ($n == 31 and @keys == 41) ||
+            ($n == 38 and @keys == 41) ||
+            (all { exists($agg_mods{$n-$_}) } @mods ) ||
+            (
+                (all { exists($agg_mods{$_}) } (1 .. 3))
+                    and
+                (all { $mods[$_+1] - $mods[$_] <= 3 } (0 .. $#mods-1))
+                    and
+                ($mods[-1] >= $n-3)
+            )
+                or
+            (@mods > 15)
+        )
+        {
+            next TRIM_STUFF;
+        }
+        my $count_not_found_yet = 0+scalar(keys(%mods_hash));
+        foreach my $combo (1 .. ((1 << @mods)-1))
+        {
+            my @indexes = grep { (($combo >> $_) & 0x1) } keys(@mods);
+            if (sum (@mods[@indexes]) % $n == $target_mod)
+            {
+                foreach my $agg_m (@mods[@indexes])
+                {
+                    foreach my $m (keys(%{$agg_mods{$agg_m}}))
+                    {
+                        if (! $mods_hash{"$m"}{can_be_formed})
+                        {
+                            if (not --$count_not_found_yet)
+                            {
+                                next TRIM_STUFF;
+                            }
+                        }
+                        $mods_hash{"$m"}{can_be_formed} = 1;
+                    }
+                }
+            }
+        }
+
+        my @not_included_mods =
+        (grep { ! $mods_hash{"$_"}{can_be_formed} } keys(%mods_hash));
+
+        if (@not_included_mods)
+        {
+            print "Found [@not_included_mods] for Modulo == $n!\n";
+            $found = 1;
+            my %not_mods = (map { $_.'' => 1 } (@not_included_mods));
+            @keys = @keys[
+                (grep { !exists($not_mods{($ints[$_] % $n).''}) } keys(@keys))
+            ];
+            # Sanity check for keys that must be present.
+            if ((grep { exists($must_have_lookup{$_}) } @keys) !=
+                scalar(keys %must_have_lookup))
+            {
+                die "Some keys are missing.";
+            }
+            last TRIM_STUFF;
+        }
+    }
+
+    if ($found)
+    {
+        calc_stuff();
+    }
+}
+
+print join("\n", map { "$keys[$_] => $ints[$_]" } keys(@keys)), "\n";
+
+print "TARGET ==\n$target\n";
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.