yaworsw/euler-manager

---
:id: 150
:name: Searching a triangular array for a sub-triangle having minimum-sum
:url: https://projecteuler.net/problem=150
:content: "In a triangular array of positive and negative integers, we wish to find
  a sub-triangle such that the sum of the numbers it contains is the smallest possible.\n\nIn
  the example below, it can be easily verified that the marked triangle satisfies
  this condition having a sum of −42.\n\n ![]({{ images_dir }}/p150.gif)\n\nWe wish
  to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random
  numbers s<sub>k</sub> in the range ±2<sup>19</sup>, using a type of random number
  generator (known as a Linear Congruential Generator) as follows:\n\nt := 0  \nfor
  k = 1 up to k = 500500:  \n&nbsp; &nbsp; t := (615949\\*t + 797807) modulo 2<sup>20</sup>
  \ \n&nbsp; &nbsp; s<sub>k</sub> := t−2<sup>19</sup>\n\nThus: s<sub>1</sub> = 273519,
  s<sub>2</sub> = −153582, s<sub>3</sub> = 450905 etc\n\nOur triangular array is then
  formed using the pseudo-random numbers thus:\n\ns<sub>1</sub>  \ns<sub>2</sub>&nbsp;
  s<sub>3</sub>  \ns<sub>4</sub>&nbsp; s<sub>5</sub>&nbsp; s<sub>6</sub>&nbsp;   \ns<sub>7</sub>&nbsp;
  s<sub>8</sub>&nbsp; s<sub>9</sub>&nbsp; s<sub>10</sub>  \n...\n\nSub-triangles can
  start at any element of the array and extend down as far as we like (taking-in the
  two elements directly below it from the next row, the three elements directly below
  from the row after that, and so on).  \nThe \"sum of a sub-triangle\" is defined
  as the sum of all the elements it contains.  \nFind the smallest possible sub-triangle
  sum.\n\n"