Shlomi Fish avatar Shlomi Fish committed 749a0a0

Add based on integral subset sum.

Comments (0)

Files changed (1)

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

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt (only => 'GMP', ':constant');
+
+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 = 2;
+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 = @init_to_check;
+
+sub calc_stuff
+{
+    $lcm = Math::BigInt::blcm(map { $_ * $_ } @keys);
+
+    @ints = (map { $lcm / ($_ * $_) } @keys);
+
+    $target = $lcm / 2;
+
+    return;
+}
+
+calc_stuff();
+
+# 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();
+
+print join("\n", @ints), "\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.