Commits

Shlomi Fish committed 30489ec

Another optimisation - both cannot be odd.

Comments (0)

Files changed (2)

project-euler/75/75-analysis.txt

 Ergo, the sum is always even.
 
 (2a+1)*(2a+1) = 4a^2+4a+1
+(2b+1)*(2b+1) = 4b^2+4b+1
+
+[4a^2+4a+1+4b^2+4b+1] mod 4 = 2, and a square number cannot have a modulo
+of 2 when divided by 4. As a result, either one of 'a' or 'b' or both should
+be even.
 
 Now for mod 4:
 

project-euler/75/75-take2.pl

 
 my $major_side_limit = int($limit/2);
 
+my $evenness = 1;
 MAJOR_SIDE:
 for my $major_side (4 .. $major_side_limit)
 {
     {
         print "Maj=$major_side\n";
     }
+    # If the major side is odd, then the minor side cannot be odd.
+    # If they are both even, then we've already inspected ($major/2,$minor/2).
     MINOR_SIDE:
-    for my $minor_side (3 .. ($major_side - 1))
+    for my $half_minor_side (2 .. (($major_side) >> 1))
     {
+        my $minor_side = ($half_minor_side << 1)-$evenness;
         if (gcd( $major_side , $minor_side ) != 1)
         {
             next MINOR_SIDE;
         }
     }
 }
+continue
+{
+    $evenness ^= 0b1;
+}
 
 my $count = 0;
 foreach my $sum_idx ((12>>1) .. ($limit>>1))