Commits

Shlomi Fish  committed fd48922

Add to Calc.pl.

  • Participants
  • Parent commits f221579

Comments (0)

Files changed (2)

File project-euler/148/Calc.pl

 my $power = $B;
 my $old_tri_id = 'Triangle[None]';
 my $old_tri_sum = 0;
-while ($power < 1_000_000_000)
+
+my @stack = ();
+
+my $LIMIT = 1_000_000_000;
+while ($power < $LIMIT)
 {
     my $next_power = $power * $B;
     my $p_1 = $power - 1;
     my $right_tri_id = qq#\\|Triangle[$start .. $end]#;
     print qq#$right_tri_id = $start*($start+1)/2 Ys ==> $right_tri_sum\n\n#;
 
+    IMPROPER_TRI:
     for my $h (2 .. $B-1)
     {
-        print qq#  ==> ImproperTriangle[1 .. @{[$power]}*$h] == ImproperTriangle[1 .. @{[$power*$h]}] = $old_tri_id * (@{[join('+',1..$h)]}) + $right_tri_id * (@{[join('+',1..$h-1)]}) = @{[$old_tri_sum*$h*($h+1)/2 + $right_tri_sum*$h*($h-1)/2]}\n\n#
+        my $improper_tri_sum = $old_tri_sum*$h*($h+1)/2 + $right_tri_sum*$h*($h-1)/2;
+        print qq#    ==> ImproperTriangle[1 .. @{[$power]}*$h] == ImproperTriangle[1 .. @{[$power*$h]}] = $old_tri_id * (@{[join('+',1..$h)]}) + $right_tri_id * (@{[join('+',1..$h-1)]}) = $improper_tri_sum\n\n#;
+
+        if ($power * $h + $power > $LIMIT)
+        {
+            for my $sub_h (1 .. $B-1)
+            {
+                my $num_tris = $h+1;
+                my $num_right_tris = $h;
+
+                my $num_sub_tris_per_tri = (1+$sub_h)*$sub_h/2;
+                my $num_sub_right_tris_per_tri = ($sub_h-1)*$sub_h/2;
+
+                my $height = $sub_h*$stack[-1]{power};
+                my $added_diff = $num_tris *
+                    ($num_sub_right_tris_per_tri * $stack[-1]{right_tri_sum} +
+                        $num_sub_tris_per_tri * $stack[-1]{tri_sum}
+                    )
+                    +
+                    $num_right_tris * (($p_1 + ($p_1-$height))*$height/2)
+                    ;
+                print qq#       ==> ImproperImproperTriangle[1 .. @{[$power * $h + $height]}] = @{[$improper_tri_sum + $added_diff]}\n\n#;
+
+            }
+            last IMPROPER_TRI;
+        }
     }
 
     my $tri_id = qq#Triangle[1 .. $next_power]#;
     my $tri_sum = $B*($B-1)/2*$right_tri_sum + $B*($B+1)/2*$old_tri_sum;
     print qq#$tri_id = (1+2+3+4+5+6) * $right_tri_id + (1+2+3+4+5+6+7) * $old_tri_id = $tri_sum\n\n#;
 
+    push @stack, { power => $power, tri_sum => $old_tri_sum, tri_id => $old_tri_id, right_tri_id => $right_tri_id, right_tri_sum => $right_tri_sum};
+
     $power = $next_power;
     $old_tri_id = $tri_id;
     $old_tri_sum = $tri_sum;

File project-euler/148/calc-num-Y-in-row-ORIG-2.pl

 
 For d_len >= 2
 
-big_Y_num[n+x*B] = B * ( Power[d_len] - B - total_mod[d_len-1] - x*B ) + (B*(B-1))/2 = 
+big_Y_num[n+x*B] = B * ( Power[d_len] - B - total_mod[d_len-1] - x*B ) + (B*(B-1))/2 =
 big_Y_total
 
 =head1 Old Analysis
     my $sum = 0;
 
     my $n;
-    foreach my $d (1 .. $limit)
+    foreach my $d (847_425_747/7 .. $limit)
     {
         $n = $d * $B + 1;
         $sum += calc_num_Y_in_7_consecutive_rows($n);