Commits

Shlomi Fish committed 36f9aeb

Solved Euler #131.

  • Participants
  • Parent commits 5f87311

Comments (0)

Files changed (1)

File project-euler/131/euler-131.pl

 
 n^3+n^2*p = n^2(n+p).
 
-Can n > p? The number is n^2(n+p), where n+p is co-prime to n (WRONG! n can
+Can n > p? The number is n^2(n+p), where n+p is co-prime to n (WRONG! n
 may be divisible by p). So n^2 must
 be a perfect cube and so does n+p. In order for n^2 to be a cube, so does n.
-But the difference between two cubes cannot be a prime number because:
-a^3 – b^3 = (a – b)(a^2 + ab + b^2). Ergo: n <= p.
+The difference between two cubes is:
+a^3 – b^3 = (a – b)(a^2 + ab + b^2), so it can be prime only if
+a - b = 1 . Ergo: n <= p.
 
 n != p because otherwise the number will be 2n^3 which cannot be a cube.
 So n < p.
 open my $primes_fh, "primes 2 1000000|"
     or die "Cannot open primes program!";
 
+my @primes = <$primes_fh>;
+
+close($primes_fh);
+
+chomp(@primes);
+
+my %primes_map;
+@primes_map{@primes} = ((1) x @primes);
+
+my $root = 1;
+my $total_count = 0;
+
+ROOTS:
+while (1)
+{
+    my $to_check = ($root * $root + $root * ($root+1) + ($root+1) * ($root+1));
+
+    if ($to_check > 1_000_000)
+    {
+        last ROOTS;
+    }
+    if (exists($primes_map{"$to_check"}))
+    {
+        $total_count++;
+        print "Found $to_check ; Total found = $total_count\n";
+    }
+    else
+    {
+        print "$to_check is not prime.\n";
+    }
+}
+continue
+{
+    $root++;
+}
+
+__END__
 my $found_count = 0;
 
 while (my $prime = <$primes_fh>)
         if ($x->copy->broot(3)->bpow(3) == $x)
         {
             $found_count++;
-            print "Found $prime. Total: $found_count\n";
+            print "Found $prime with $n. Total: $found_count\n";
             last N_LOOP;
         }
     }