Commits

Shlomi Fish committed 318d863

More progress, but not cigar.

Comments (0)

Files changed (4)

project-euler/126/euler-126-take3.pl

 use strict;
 use warnings;
 
+use IO::Handle;
+
 use integer;
 
 use List::MoreUtils qw(any all);
 
+STDOUT->autoflush(1);
+
 my @C;
 
 # Matches $X,$Y,$Z (where $X >= $Y >= $Z) to the cuboid array and maximal 
         : ($old_n+($x_lim+$y_lim+$z_lim)*4 + (($depth > 1) ? 8*($depth-2) : 0))
     );
 
-=begin foo
-    my $new_layer_count = 0;
-
-    my $calc_dist = sub {
-        my ($x, $x_lim) = @_;
-
-        return
-            (($x < 0) ? abs($x) : ($x >= $x_lim) ? ($x-($x_lim-1)) : 0);
-    };
-
-    foreach my $x (-$depth .. $x_lim+$depth-1)
-    {
-        my $dist_x = $calc_dist->($x,$x_lim);
-
-        foreach my $y (-$depth .. $y_lim + $depth-1)
-        {
-            my $dist_y = $calc_dist->($y,$y_lim);
-
-            foreach my $z (-$depth .. $z_lim + $depth-1)
-            {
-                my $dist_z = $calc_dist->($z, $z_lim);
-
-                if ($dist_x+$dist_y+$dist_z == $depth)
-                {
-                    $new_layer_count++;
-                }
-            }
-        }
-    }
-
-    if ($new_layer_count != $expected_new_layer_count)
-    {
-       die "\$new_layer_count != \$expected_new_layer_count ==
-        $new_layer_count != $expected_new_layer_count for depth $depth
-            and ($x_lim,$y_lim,$z_lim).";
-    }
-
-=end foo
-
-=cut
-
     $cuboids{$key} = {d => ($depth+1), n => $new_layer_count};
 
     if ((++$C[$new_layer_count]) > $max_C_n)

project-euler/132/132-2.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt 'lib' => 'GMP', ':constant';
+
+use List::Util qw(reduce min);
+
+my @divisors;
+
+foreach my $power_of_2 (0 .. 9)
+{
+    foreach my $power_of_5 (0 .. 9)
+    {
+        my $num_digits = 2 ** $power_of_2 * 5 ** $power_of_5;
+        push @divisors, +{ l => $num_digits+1, n => 
+            sub { return ("1" . "0" x ($num_digits-1) . "1") },
+        };
+
+        push @divisors, +{ l => $num_digits*4+1, n =>
+            sub { return (("1" . "0" x ($num_digits-1)) x 4 . "1") },
+        };
+    }
+}
+
+@divisors = sort { $a->{l} <=> $b->{l} } @divisors;
+
+my %factors;
+foreach my $div (@divisors)
+{
+    my $n = $div->{n}->();
+    
+    print "Checking $n\n";
+    my $factor_string = `factor "$n"`;
+    
+    $factor_string =~ s{\A[^:]*:\s*}{}ms;
+    
+    foreach my $f (split(/\s+/, $factor_string))
+    {
+        $factors{$f}++;
+    }
+    my @factors_sorted = sort { $a <=> $b } keys(%factors);
+    print "Num found factors: ", scalar(@factors_sorted), "\n";
+    print "Factors == @factors_sorted\n";
+    print "Sum first 40:", (reduce { $a + $b } 0, 0, @factors_sorted[0 .. min($#factors_sorted .. 39)]), "\n";
+}

project-euler/132/132-planning.txt

+The Problem:
+------------
+
+A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.
+
+For example, R(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.
+
+Find the sum of the first forty prime factors of R(10^9).
+
+Analysis:
+---------
+
+R(2*n) = R(n) * (10^n+1)
+
+So for example
+
+* 1111 = 11 * 101
+
+* 111111 = 111 * 1001
+
+R(4*n) = R(2*n) * (10^(2n)+1) = R(n) * (10^n+1) * (10^(2n)+1)
+
+R(5*n) = R(n) * (1 + 10^n + 10^(2n) + 10^(3n) + 10^(4n))
+
+R(5*5*n) = R(5n) * (1 + 10^(5n) + 10^(2*5n) ...)
+
+R(5*5*n)

project-euler/132/132.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Math::BigInt 'lib' => 'GMP', ':constant';
+
+sub factorize
+{
+    my ($n) = @_;
+    my @ret;
+
+    my $factor = 2;
+    while ($n > 1)
+    {
+        if ($n % $factor == 0)
+        {
+            push @ret, $factor;
+            $n /= $factor;
+        }
+        else
+        {
+            $factor++;
+        }
+    }
+    return \@ret;
+}
+
+# l = len or logarithm.
+# n = a promise for the number.
+my @factors =
+(
+    +{ l => 2, n => sub { return 11; }}, 
+    (map { 
+        my $e = $_;
+        +{
+            l => ((2 ** $e)+1),
+            n => sub { return 10 ** (2 ** $e) + 1; },
+        }
+        } (1 .. 9)
+    ),
+    (map {
+        my $e = $_;
+        my $ten_e = (2**9) * (5 ** $e);
+        +{
+            l => (4*$ten_e+1),
+            n => sub { my $x = (10 ** $ten_e); return 1 + $x + ($x ** 2) + ($x ** 3) + ($x ** 4); },
+        }
+    } (1 .. 9)),
+);
+
+@factors = (sort { $a->{l} <=> $b->{l} } @factors);
+
+my @primes;
+
+my $LIMIT = 40;
+
+NON_P_FACTORS:
+foreach my $fact (@factors)
+{
+    print "$fact->{l}\n";
+    my $n = $fact->{n}->();
+
+    print "N = $n\n";
+    my $l = <STDIN>;
+    next NON_P_FACTORS;
+
+    push @primes, @{factorize($n)};
+
+    @primes = sort { $a <=> $b } @primes;
+
+    if (@primes > $LIMIT)
+    {
+        splice(@primes,$LIMIT);
+    }
+
+    if (@primes == $LIMIT)
+    {
+        my $s = 0;
+
+        foreach my $p (@primes)
+        {
+            $s += $p;
+        }
+        print "Primes [", join(',',@primes),"]\n";
+        print "Sum = $s\n";
+    }
+}