Commits

Shlomi Fish committed 89264f3

Add more to question 75.

Comments (0)

Files changed (2)

project-euler/75/75-analysis.txt

+A^2 + B^2 = C^2
+
+This already implies that C+A > B , C+B > A and A+B > C. The latter is because
+(A+B)^2 = A^2 + 2AB + B^2 > A^2+B^2 = C^2.
+
+Now, here is the modulo 2 of the results:
+
+ A | B | === | C | A+B+C
+-----------------------
+ 0   0         0 |  0
+ 1   0         1 |  0
+ 1   1         0 |  0
+-------------------------
+
+Ergo, the sum is always even.
+
+(2a+1)*(2a+1) = 4a^2+4a+1
+
+Now for mod 4:
+
+ A | B | A^2 | B^2 | === | C^2 | C | A+B+C
+------------------------------------------
+ 0   0     0     0           0 | 0 | 0
+ 1/3 0     1     0           1 | 
+ 1   1         0 |  0
+-------------------------
+

project-euler/75/75.pl

 
 my $hypotenuse_lim = int($limit/2);
 
+HYPO:
 for my $hypotenuse_length (5 .. $hypotenuse_lim)
 {
+    if ($hypotenuse_length & 0x1)
+    {
+        
+    }
+
     print "$hypotenuse_length\n" if (not $hypotenuse_length % 1_000);
     my $hypot_sq = $hypotenuse_length ** 2;
     
             my $sum = int($side2_len+$side1_len+$hypotenuse_length);
             if ($sum <= $limit)
             {
-                if (vec($verdicts, $sum, 2) != 2)
+                # Only even numbers can be sums, so we can divide the index
+                # by 2.
+                # See 75-analysis.txt
+                my $idx = ($sum>>1);
+                if (vec($verdicts, $idx, 2) != 2)
                 {
-                    vec($verdicts, $sum, 2)++;
+                    vec($verdicts, $idx, 2)++;
                 }
             }
         }
 }
 
 my $count = 0;
-foreach my $sum (12 .. $limit)
+foreach my $sum_idx ((12>>1) .. ($limit>>1))
 {
-    if (vec($verdicts, $sum, 2) == 1)
+    if (vec($verdicts, $sum_idx, 2) == 1)
     {
         $count++
     }