Commits

Shlomi Fish  committed 45d8660

Add some faster programs.

Still not fast enough. These programs see which modulos are possible for n
to be and do stuff based on it. The euler-138-2.pl handles only the
5n^2+4n+1 case.

  • Participants
  • Parent commits fabeb68

Comments (0)

Files changed (3)

File project-euler/138/138-analysis.txt

 
 If $a$ is whole, then L^2 will have a residue of 1/4 which means L cannot be
 whole. Therefore $h$ is odd.
+
+a = n + 1/2
+L^2 = 5(n+1/2)^2 + 1/4 ± (n + 1/2) = 5n^2 + 5n + 5/4 + 1/4 ± (n + 1/2)
+    = 5n^2 + 5n + 3/2 ± (n + 1/2)
+
+Two sub-cases:
+
+1. L^2 = 5n^2 + 6n + 2 = 
+
+2. L^2 = 5n^2 + 4n + 1 = 
+

File project-euler/138/euler-138-2.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use integer;
+
+# use Math::BigInt lib => 'GMP', ':constant';
+
+sub get_valid_n_mods_for_base
+{
+    my ($base) = @_;
+
+    my %valid_L_squared_mods;
+
+    for my $L (0 .. $base-1)
+    {
+        $valid_L_squared_mods{($L * $L) % $base} = 1;
+    }
+
+    my @valid_n_mods;
+    for my $n (0 .. $base-1)
+    {
+        my $modulo = ((1 + $n * (4 + $n * 5))%$base);
+        if (exists($valid_L_squared_mods{$modulo}))
+        {
+            push @valid_n_mods, $n;
+        }
+    }
+
+    return \@valid_n_mods;
+}
+
+my $base = 95_480;
+my $count = 0;
+my $sum_L = 0;
+my $base_n = 0;
+my $valid_mods = get_valid_n_mods_for_base($base);
+my $L = 1;
+my $L_sq = 1;
+my $L_sq_delta = 1;
+
+while (1)
+{
+    foreach my $delta (@$valid_mods)
+    {
+        my $n = $base_n + $delta;
+
+        my ($prev_L, $prev_L_sq, $prev_L_sq_delta);
+        foreach my $result (1+$n*(4+5*$n))
+        {
+            while ($L_sq < $result)
+            {
+                ($prev_L, $prev_L_sq, $prev_L_sq_delta)
+                    = ($L, $L_sq, $L_sq_delta);
+                $L++;
+                $L_sq += ($L_sq_delta += 2);
+            }
+            if ($L_sq == $result)
+            {
+                $sum_L += $L;
+                $count++;
+                print "Found $L [$n] ; Sum = $sum_L ; Count = $count\n";
+            }
+            else
+            {
+                ($L, $L_sq, $L_sq_delta) =
+                    ($prev_L, $prev_L_sq, $prev_L_sq_delta);
+            }
+        }
+    }
+}
+continue
+{
+    $base_n += $base;
+}

File project-euler/138/modulos-analysis.pl

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+sub get_valid_n_mods_for_base
+{
+    my ($base) = @_;
+
+    my %valid_L_squared_mods;
+
+    for my $L (0 .. $base-1)
+    {
+        $valid_L_squared_mods{($L * $L) % $base} = 1;
+    }
+
+    my @valid_n_mods;
+    for my $n (0 .. $base-1)
+    {
+        my $modulo = ((1 + $n * (4 + $n * 5))%$base);
+        if (exists($valid_L_squared_mods{$modulo}))
+        {
+            push @valid_n_mods, $n;
+        }
+    }
+
+    return \@valid_n_mods;
+}
+
+my $min = undef;
+for my $base (reverse(2 .. 100_000))
+{
+    my $mods = get_valid_n_mods_for_base($base);
+    if (! defined $min or @$mods < $min)
+    {
+        $min = @$mods;
+        print "Num Valid 'n's for $base: $min\n";
+    }
+}