docs/3._Developing_a_Program.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# [Project Euler, first problem: \"Multiples of 3 and 5\"](https://projecteuler.net/problem=1)\n",
   8     "\n",
   9     "    If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.\n",
  10     "\n",
  11     "    Find the sum of all the multiples of 3 or 5 below 1000."
  12    ]
  13   },
  14   {
  15    "cell_type": "code",
  16    "execution_count": 1,
  17    "metadata": {},
  18    "outputs": [],
  19    "source": [
  20     "from notebook_preamble import J, V, define"
  21    ]
  22   },
  23   {
  24    "cell_type": "markdown",
  25    "metadata": {},
  26    "source": [
  27     "Let's create a predicate that returns `True` if a number is a multiple of 3 or 5 and `False` otherwise."
  28    ]
  29   },
  30   {
  31    "cell_type": "code",
  32    "execution_count": 2,
  33    "metadata": {},
  34    "outputs": [],
  35    "source": [
  36     "define('P == [3 % not] dupdip 5 % not or')"
  37    ]
  38   },
  39   {
  40    "cell_type": "code",
  41    "execution_count": 3,
  42    "metadata": {},
  43    "outputs": [
  44     {
  45      "name": "stdout",
  46      "output_type": "stream",
  47      "text": [
  48       "             . 80 P\n",
  49       "          80 . P\n",
  50       "          80 . [3 % not] dupdip 5 % not or\n",
  51       "80 [3 % not] . dupdip 5 % not or\n",
  52       "          80 . 3 % not 80 5 % not or\n",
  53       "        80 3 . % not 80 5 % not or\n",
  54       "           2 . not 80 5 % not or\n",
  55       "       False . 80 5 % not or\n",
  56       "    False 80 . 5 % not or\n",
  57       "  False 80 5 . % not or\n",
  58       "     False 0 . not or\n",
  59       "  False True . or\n",
  60       "        True . \n"
  61      ]
  62     }
  63    ],
  64    "source": [
  65     "V('80 P')"
  66    ]
  67   },
  68   {
  69    "cell_type": "markdown",
  70    "metadata": {},
  71    "source": [
  72     "Given the predicate function `P` a suitable program is:\n",
  73     "\n",
  74     "    PE1 == 1000 range [P] filter sum\n",
  75     "\n",
  76     "This function generates a list of the integers from 0 to 999, filters\n",
  77     "that list by `P`, and then sums the result.\n",
  78     "\n",
  79     "Logically this is fine, but pragmatically we are doing more work than we\n",
  80     "should be; we generate one thousand integers but actually use less than\n",
  81     "half of them.  A better solution would be to generate just the multiples\n",
  82     "we want to sum, and to add them as we go rather than storing them and\n",
  83     "adding summing them at the end.\n",
  84     "\n",
  85     "At first I had the idea to use two counters and increase them by three\n",
  86     "and five, respectively.  This way we only generate the terms that we\n",
  87     "actually want to sum.  We have to proceed by incrementing the counter\n",
  88     "that is lower, or if they are equal, the three counter, and we have to\n",
  89     "take care not to double add numbers like 15 that are multiples of both\n",
  90     "three and five.\n",
  91     "\n",
  92     "This seemed a little clunky, so I tried a different approach.\n",
  93     "\n",
  94     "Consider the first few terms in the series:\n",
  95     "\n",
  96     "    3 5 6 9 10 12 15 18 20 21 ...\n",
  97     "\n",
  98     "Subtract each number from the one after it (subtracting 0 from 3):\n",
  99     "\n",
 100     "    3 5 6 9 10 12 15 18 20 21 24 25 27 30 ...\n",
 101     "    0 3 5 6  9 10 12 15 18 20 21 24 25 27 ...\n",
 102     "    -------------------------------------------\n",
 103     "    3 2 1 3  1  2  3  3  2  1  3  1  2  3 ...\n",
 104     "\n",
 105     "You get this lovely repeating palindromic sequence:\n",
 106     "\n",
 107     "    3 2 1 3 1 2 3\n",
 108     "\n",
 109     "To make a counter that increments by factors of 3 and 5 you just add\n",
 110     "these differences to the counter one-by-one in a loop.\n",
 111     "\n",
 112     "\n",
 113     "To make use of this sequence to increment a counter and sum terms as we\n",
 114     "go we need a function that will accept the sum, the counter, and the next\n",
 115     "term to add, and that adds the term to the counter and a copy of the\n",
 116     "counter to the running sum.  This function will do that:\n",
 117     "\n",
 118     "    PE1.1 == + [+] dupdip"
 119    ]
 120   },
 121   {
 122    "cell_type": "code",
 123    "execution_count": 4,
 124    "metadata": {},
 125    "outputs": [],
 126    "source": [
 127     "define('PE1.1 == + [+] dupdip')"
 128    ]
 129   },
 130   {
 131    "cell_type": "code",
 132    "execution_count": 5,
 133    "metadata": {},
 134    "outputs": [
 135     {
 136      "name": "stdout",
 137      "output_type": "stream",
 138      "text": [
 139       "        . 0 0 3 PE1.1\n",
 140       "      0 . 0 3 PE1.1\n",
 141       "    0 0 . 3 PE1.1\n",
 142       "  0 0 3 . PE1.1\n",
 143       "  0 0 3 . + [+] dupdip\n",
 144       "    0 3 . [+] dupdip\n",
 145       "0 3 [+] . dupdip\n",
 146       "    0 3 . + 3\n",
 147       "      3 . 3\n",
 148       "    3 3 . \n"
 149      ]
 150     }
 151    ],
 152    "source": [
 153     "V('0 0 3 PE1.1')"
 154    ]
 155   },
 156   {
 157    "cell_type": "code",
 158    "execution_count": 6,
 159    "metadata": {
 160     "scrolled": false
 161    },
 162    "outputs": [
 163     {
 164      "name": "stdout",
 165      "output_type": "stream",
 166      "text": [
 167       "                            . 0 0 [3 2 1 3 1 2 3] [PE1.1] step\n",
 168       "                          0 . 0 [3 2 1 3 1 2 3] [PE1.1] step\n",
 169       "                        0 0 . [3 2 1 3 1 2 3] [PE1.1] step\n",
 170       "        0 0 [3 2 1 3 1 2 3] . [PE1.1] step\n",
 171       "0 0 [3 2 1 3 1 2 3] [PE1.1] . step\n",
 172       "              0 0 3 [PE1.1] . i [2 1 3 1 2 3] [PE1.1] step\n",
 173       "                      0 0 3 . PE1.1 [2 1 3 1 2 3] [PE1.1] step\n",
 174       "                      0 0 3 . + [+] dupdip [2 1 3 1 2 3] [PE1.1] step\n",
 175       "                        0 3 . [+] dupdip [2 1 3 1 2 3] [PE1.1] step\n",
 176       "                    0 3 [+] . dupdip [2 1 3 1 2 3] [PE1.1] step\n",
 177       "                        0 3 . + 3 [2 1 3 1 2 3] [PE1.1] step\n",
 178       "                          3 . 3 [2 1 3 1 2 3] [PE1.1] step\n",
 179       "                        3 3 . [2 1 3 1 2 3] [PE1.1] step\n",
 180       "          3 3 [2 1 3 1 2 3] . [PE1.1] step\n",
 181       "  3 3 [2 1 3 1 2 3] [PE1.1] . step\n",
 182       "              3 3 2 [PE1.1] . i [1 3 1 2 3] [PE1.1] step\n",
 183       "                      3 3 2 . PE1.1 [1 3 1 2 3] [PE1.1] step\n",
 184       "                      3 3 2 . + [+] dupdip [1 3 1 2 3] [PE1.1] step\n",
 185       "                        3 5 . [+] dupdip [1 3 1 2 3] [PE1.1] step\n",
 186       "                    3 5 [+] . dupdip [1 3 1 2 3] [PE1.1] step\n",
 187       "                        3 5 . + 5 [1 3 1 2 3] [PE1.1] step\n",
 188       "                          8 . 5 [1 3 1 2 3] [PE1.1] step\n",
 189       "                        8 5 . [1 3 1 2 3] [PE1.1] step\n",
 190       "            8 5 [1 3 1 2 3] . [PE1.1] step\n",
 191       "    8 5 [1 3 1 2 3] [PE1.1] . step\n",
 192       "              8 5 1 [PE1.1] . i [3 1 2 3] [PE1.1] step\n",
 193       "                      8 5 1 . PE1.1 [3 1 2 3] [PE1.1] step\n",
 194       "                      8 5 1 . + [+] dupdip [3 1 2 3] [PE1.1] step\n",
 195       "                        8 6 . [+] dupdip [3 1 2 3] [PE1.1] step\n",
 196       "                    8 6 [+] . dupdip [3 1 2 3] [PE1.1] step\n",
 197       "                        8 6 . + 6 [3 1 2 3] [PE1.1] step\n",
 198       "                         14 . 6 [3 1 2 3] [PE1.1] step\n",
 199       "                       14 6 . [3 1 2 3] [PE1.1] step\n",
 200       "             14 6 [3 1 2 3] . [PE1.1] step\n",
 201       "     14 6 [3 1 2 3] [PE1.1] . step\n",
 202       "             14 6 3 [PE1.1] . i [1 2 3] [PE1.1] step\n",
 203       "                     14 6 3 . PE1.1 [1 2 3] [PE1.1] step\n",
 204       "                     14 6 3 . + [+] dupdip [1 2 3] [PE1.1] step\n",
 205       "                       14 9 . [+] dupdip [1 2 3] [PE1.1] step\n",
 206       "                   14 9 [+] . dupdip [1 2 3] [PE1.1] step\n",
 207       "                       14 9 . + 9 [1 2 3] [PE1.1] step\n",
 208       "                         23 . 9 [1 2 3] [PE1.1] step\n",
 209       "                       23 9 . [1 2 3] [PE1.1] step\n",
 210       "               23 9 [1 2 3] . [PE1.1] step\n",
 211       "       23 9 [1 2 3] [PE1.1] . step\n",
 212       "             23 9 1 [PE1.1] . i [2 3] [PE1.1] step\n",
 213       "                     23 9 1 . PE1.1 [2 3] [PE1.1] step\n",
 214       "                     23 9 1 . + [+] dupdip [2 3] [PE1.1] step\n",
 215       "                      23 10 . [+] dupdip [2 3] [PE1.1] step\n",
 216       "                  23 10 [+] . dupdip [2 3] [PE1.1] step\n",
 217       "                      23 10 . + 10 [2 3] [PE1.1] step\n",
 218       "                         33 . 10 [2 3] [PE1.1] step\n",
 219       "                      33 10 . [2 3] [PE1.1] step\n",
 220       "                33 10 [2 3] . [PE1.1] step\n",
 221       "        33 10 [2 3] [PE1.1] . step\n",
 222       "            33 10 2 [PE1.1] . i [3] [PE1.1] step\n",
 223       "                    33 10 2 . PE1.1 [3] [PE1.1] step\n",
 224       "                    33 10 2 . + [+] dupdip [3] [PE1.1] step\n",
 225       "                      33 12 . [+] dupdip [3] [PE1.1] step\n",
 226       "                  33 12 [+] . dupdip [3] [PE1.1] step\n",
 227       "                      33 12 . + 12 [3] [PE1.1] step\n",
 228       "                         45 . 12 [3] [PE1.1] step\n",
 229       "                      45 12 . [3] [PE1.1] step\n",
 230       "                  45 12 [3] . [PE1.1] step\n",
 231       "          45 12 [3] [PE1.1] . step\n",
 232       "            45 12 3 [PE1.1] . i\n",
 233       "                    45 12 3 . PE1.1\n",
 234       "                    45 12 3 . + [+] dupdip\n",
 235       "                      45 15 . [+] dupdip\n",
 236       "                  45 15 [+] . dupdip\n",
 237       "                      45 15 . + 15\n",
 238       "                         60 . 15\n",
 239       "                      60 15 . \n"
 240      ]
 241     }
 242    ],
 243    "source": [
 244     "V('0 0 [3 2 1 3 1 2 3] [PE1.1] step')"
 245    ]
 246   },
 247   {
 248    "cell_type": "markdown",
 249    "metadata": {},
 250    "source": [
 251     "So one `step` through all seven terms brings the counter to 15 and the total to 60."
 252    ]
 253   },
 254   {
 255    "cell_type": "code",
 256    "execution_count": 7,
 257    "metadata": {},
 258    "outputs": [
 259     {
 260      "data": {
 261       "text/plain": [
 262        "66"
 263       ]
 264      },
 265      "execution_count": 7,
 266      "metadata": {},
 267      "output_type": "execute_result"
 268     }
 269    ],
 270    "source": [
 271     "1000 / 15"
 272    ]
 273   },
 274   {
 275    "cell_type": "code",
 276    "execution_count": 8,
 277    "metadata": {},
 278    "outputs": [
 279     {
 280      "data": {
 281       "text/plain": [
 282        "990"
 283       ]
 284      },
 285      "execution_count": 8,
 286      "metadata": {},
 287      "output_type": "execute_result"
 288     }
 289    ],
 290    "source": [
 291     "66 * 15"
 292    ]
 293   },
 294   {
 295    "cell_type": "code",
 296    "execution_count": 9,
 297    "metadata": {},
 298    "outputs": [
 299     {
 300      "data": {
 301       "text/plain": [
 302        "10"
 303       ]
 304      },
 305      "execution_count": 9,
 306      "metadata": {},
 307      "output_type": "execute_result"
 308     }
 309    ],
 310    "source": [
 311     "1000 - 990"
 312    ]
 313   },
 314   {
 315    "cell_type": "markdown",
 316    "metadata": {},
 317    "source": [
 318     "We only want the terms *less than* 1000."
 319    ]
 320   },
 321   {
 322    "cell_type": "code",
 323    "execution_count": 10,
 324    "metadata": {},
 325    "outputs": [
 326     {
 327      "data": {
 328       "text/plain": [
 329        "9"
 330       ]
 331      },
 332      "execution_count": 10,
 333      "metadata": {},
 334      "output_type": "execute_result"
 335     }
 336    ],
 337    "source": [
 338     "999 - 990"
 339    ]
 340   },
 341   {
 342    "cell_type": "markdown",
 343    "metadata": {},
 344    "source": [
 345     "That means we want to run the full list of numbers sixty-six times to get to 990 and then the first four numbers 3 2 1 3 to get to 999."
 346    ]
 347   },
 348   {
 349    "cell_type": "code",
 350    "execution_count": 11,
 351    "metadata": {},
 352    "outputs": [],
 353    "source": [
 354     "define('PE1 == 0 0 66 [[3 2 1 3 1 2 3] [PE1.1] step] times [3 2 1 3] [PE1.1] step pop')"
 355    ]
 356   },
 357   {
 358    "cell_type": "code",
 359    "execution_count": 12,
 360    "metadata": {},
 361    "outputs": [
 362     {
 363      "name": "stdout",
 364      "output_type": "stream",
 365      "text": [
 366       "233168\n"
 367      ]
 368     }
 369    ],
 370    "source": [
 371     "J('PE1')"
 372    ]
 373   },
 374   {
 375    "cell_type": "markdown",
 376    "metadata": {},
 377    "source": [
 378     "This form uses no extra storage and produces no unused summands.  It's\n",
 379     "good but there's one more trick we can apply.  The list of seven terms\n",
 380     "takes up at least seven bytes.  But notice that all of the terms are less\n",
 381     "than four, and so each can fit in just two bits.  We could store all\n",
 382     "seven terms in just fourteen bits and use masking and shifts to pick out\n",
 383     "each term as we go.  This will use less space and save time loading whole\n",
 384     "integer terms from the list.\n",
 385     "\n",
 386     "        3  2  1  3  1  2  3\n",
 387     "    0b 11 10 01 11 01 10 11 == 14811"
 388    ]
 389   },
 390   {
 391    "cell_type": "code",
 392    "execution_count": 13,
 393    "metadata": {},
 394    "outputs": [
 395     {
 396      "data": {
 397       "text/plain": [
 398        "14811"
 399       ]
 400      },
 401      "execution_count": 13,
 402      "metadata": {},
 403      "output_type": "execute_result"
 404     }
 405    ],
 406    "source": [
 407     "0b11100111011011"
 408    ]
 409   },
 410   {
 411    "cell_type": "code",
 412    "execution_count": 14,
 413    "metadata": {},
 414    "outputs": [],
 415    "source": [
 416     "define('PE1.2 == [3 & PE1.1] dupdip 2 >>')"
 417    ]
 418   },
 419   {
 420    "cell_type": "code",
 421    "execution_count": 15,
 422    "metadata": {},
 423    "outputs": [
 424     {
 425      "name": "stdout",
 426      "output_type": "stream",
 427      "text": [
 428       "                      . 0 0 14811 PE1.2\n",
 429       "                    0 . 0 14811 PE1.2\n",
 430       "                  0 0 . 14811 PE1.2\n",
 431       "            0 0 14811 . PE1.2\n",
 432       "            0 0 14811 . [3 & PE1.1] dupdip 2 >>\n",
 433       "0 0 14811 [3 & PE1.1] . dupdip 2 >>\n",
 434       "            0 0 14811 . 3 & PE1.1 14811 2 >>\n",
 435       "          0 0 14811 3 . & PE1.1 14811 2 >>\n",
 436       "                0 0 3 . PE1.1 14811 2 >>\n",
 437       "                0 0 3 . + [+] dupdip 14811 2 >>\n",
 438       "                  0 3 . [+] dupdip 14811 2 >>\n",
 439       "              0 3 [+] . dupdip 14811 2 >>\n",
 440       "                  0 3 . + 3 14811 2 >>\n",
 441       "                    3 . 3 14811 2 >>\n",
 442       "                  3 3 . 14811 2 >>\n",
 443       "            3 3 14811 . 2 >>\n",
 444       "          3 3 14811 2 . >>\n",
 445       "             3 3 3702 . \n"
 446      ]
 447     }
 448    ],
 449    "source": [
 450     "V('0 0 14811 PE1.2')"
 451    ]
 452   },
 453   {
 454    "cell_type": "code",
 455    "execution_count": 16,
 456    "metadata": {},
 457    "outputs": [
 458     {
 459      "name": "stdout",
 460      "output_type": "stream",
 461      "text": [
 462       "                     . 3 3 3702 PE1.2\n",
 463       "                   3 . 3 3702 PE1.2\n",
 464       "                 3 3 . 3702 PE1.2\n",
 465       "            3 3 3702 . PE1.2\n",
 466       "            3 3 3702 . [3 & PE1.1] dupdip 2 >>\n",
 467       "3 3 3702 [3 & PE1.1] . dupdip 2 >>\n",
 468       "            3 3 3702 . 3 & PE1.1 3702 2 >>\n",
 469       "          3 3 3702 3 . & PE1.1 3702 2 >>\n",
 470       "               3 3 2 . PE1.1 3702 2 >>\n",
 471       "               3 3 2 . + [+] dupdip 3702 2 >>\n",
 472       "                 3 5 . [+] dupdip 3702 2 >>\n",
 473       "             3 5 [+] . dupdip 3702 2 >>\n",
 474       "                 3 5 . + 5 3702 2 >>\n",
 475       "                   8 . 5 3702 2 >>\n",
 476       "                 8 5 . 3702 2 >>\n",
 477       "            8 5 3702 . 2 >>\n",
 478       "          8 5 3702 2 . >>\n",
 479       "             8 5 925 . \n"
 480      ]
 481     }
 482    ],
 483    "source": [
 484     "V('3 3 3702 PE1.2')"
 485    ]
 486   },
 487   {
 488    "cell_type": "code",
 489    "execution_count": 17,
 490    "metadata": {
 491     "scrolled": true
 492    },
 493    "outputs": [
 494     {
 495      "name": "stdout",
 496      "output_type": "stream",
 497      "text": [
 498       "                      . 0 0 14811 7 [PE1.2] times pop\n",
 499       "                    0 . 0 14811 7 [PE1.2] times pop\n",
 500       "                  0 0 . 14811 7 [PE1.2] times pop\n",
 501       "            0 0 14811 . 7 [PE1.2] times pop\n",
 502       "          0 0 14811 7 . [PE1.2] times pop\n",
 503       "  0 0 14811 7 [PE1.2] . times pop\n",
 504       "    0 0 14811 [PE1.2] . i 6 [PE1.2] times pop\n",
 505       "            0 0 14811 . PE1.2 6 [PE1.2] times pop\n",
 506       "            0 0 14811 . [3 & PE1.1] dupdip 2 >> 6 [PE1.2] times pop\n",
 507       "0 0 14811 [3 & PE1.1] . dupdip 2 >> 6 [PE1.2] times pop\n",
 508       "            0 0 14811 . 3 & PE1.1 14811 2 >> 6 [PE1.2] times pop\n",
 509       "          0 0 14811 3 . & PE1.1 14811 2 >> 6 [PE1.2] times pop\n",
 510       "                0 0 3 . PE1.1 14811 2 >> 6 [PE1.2] times pop\n",
 511       "                0 0 3 . + [+] dupdip 14811 2 >> 6 [PE1.2] times pop\n",
 512       "                  0 3 . [+] dupdip 14811 2 >> 6 [PE1.2] times pop\n",
 513       "              0 3 [+] . dupdip 14811 2 >> 6 [PE1.2] times pop\n",
 514       "                  0 3 . + 3 14811 2 >> 6 [PE1.2] times pop\n",
 515       "                    3 . 3 14811 2 >> 6 [PE1.2] times pop\n",
 516       "                  3 3 . 14811 2 >> 6 [PE1.2] times pop\n",
 517       "            3 3 14811 . 2 >> 6 [PE1.2] times pop\n",
 518       "          3 3 14811 2 . >> 6 [PE1.2] times pop\n",
 519       "             3 3 3702 . 6 [PE1.2] times pop\n",
 520       "           3 3 3702 6 . [PE1.2] times pop\n",
 521       "   3 3 3702 6 [PE1.2] . times pop\n",
 522       "     3 3 3702 [PE1.2] . i 5 [PE1.2] times pop\n",
 523       "             3 3 3702 . PE1.2 5 [PE1.2] times pop\n",
 524       "             3 3 3702 . [3 & PE1.1] dupdip 2 >> 5 [PE1.2] times pop\n",
 525       " 3 3 3702 [3 & PE1.1] . dupdip 2 >> 5 [PE1.2] times pop\n",
 526       "             3 3 3702 . 3 & PE1.1 3702 2 >> 5 [PE1.2] times pop\n",
 527       "           3 3 3702 3 . & PE1.1 3702 2 >> 5 [PE1.2] times pop\n",
 528       "                3 3 2 . PE1.1 3702 2 >> 5 [PE1.2] times pop\n",
 529       "                3 3 2 . + [+] dupdip 3702 2 >> 5 [PE1.2] times pop\n",
 530       "                  3 5 . [+] dupdip 3702 2 >> 5 [PE1.2] times pop\n",
 531       "              3 5 [+] . dupdip 3702 2 >> 5 [PE1.2] times pop\n",
 532       "                  3 5 . + 5 3702 2 >> 5 [PE1.2] times pop\n",
 533       "                    8 . 5 3702 2 >> 5 [PE1.2] times pop\n",
 534       "                  8 5 . 3702 2 >> 5 [PE1.2] times pop\n",
 535       "             8 5 3702 . 2 >> 5 [PE1.2] times pop\n",
 536       "           8 5 3702 2 . >> 5 [PE1.2] times pop\n",
 537       "              8 5 925 . 5 [PE1.2] times pop\n",
 538       "            8 5 925 5 . [PE1.2] times pop\n",
 539       "    8 5 925 5 [PE1.2] . times pop\n",
 540       "      8 5 925 [PE1.2] . i 4 [PE1.2] times pop\n",
 541       "              8 5 925 . PE1.2 4 [PE1.2] times pop\n",
 542       "              8 5 925 . [3 & PE1.1] dupdip 2 >> 4 [PE1.2] times pop\n",
 543       "  8 5 925 [3 & PE1.1] . dupdip 2 >> 4 [PE1.2] times pop\n",
 544       "              8 5 925 . 3 & PE1.1 925 2 >> 4 [PE1.2] times pop\n",
 545       "            8 5 925 3 . & PE1.1 925 2 >> 4 [PE1.2] times pop\n",
 546       "                8 5 1 . PE1.1 925 2 >> 4 [PE1.2] times pop\n",
 547       "                8 5 1 . + [+] dupdip 925 2 >> 4 [PE1.2] times pop\n",
 548       "                  8 6 . [+] dupdip 925 2 >> 4 [PE1.2] times pop\n",
 549       "              8 6 [+] . dupdip 925 2 >> 4 [PE1.2] times pop\n",
 550       "                  8 6 . + 6 925 2 >> 4 [PE1.2] times pop\n",
 551       "                   14 . 6 925 2 >> 4 [PE1.2] times pop\n",
 552       "                 14 6 . 925 2 >> 4 [PE1.2] times pop\n",
 553       "             14 6 925 . 2 >> 4 [PE1.2] times pop\n",
 554       "           14 6 925 2 . >> 4 [PE1.2] times pop\n",
 555       "             14 6 231 . 4 [PE1.2] times pop\n",
 556       "           14 6 231 4 . [PE1.2] times pop\n",
 557       "   14 6 231 4 [PE1.2] . times pop\n",
 558       "     14 6 231 [PE1.2] . i 3 [PE1.2] times pop\n",
 559       "             14 6 231 . PE1.2 3 [PE1.2] times pop\n",
 560       "             14 6 231 . [3 & PE1.1] dupdip 2 >> 3 [PE1.2] times pop\n",
 561       " 14 6 231 [3 & PE1.1] . dupdip 2 >> 3 [PE1.2] times pop\n",
 562       "             14 6 231 . 3 & PE1.1 231 2 >> 3 [PE1.2] times pop\n",
 563       "           14 6 231 3 . & PE1.1 231 2 >> 3 [PE1.2] times pop\n",
 564       "               14 6 3 . PE1.1 231 2 >> 3 [PE1.2] times pop\n",
 565       "               14 6 3 . + [+] dupdip 231 2 >> 3 [PE1.2] times pop\n",
 566       "                 14 9 . [+] dupdip 231 2 >> 3 [PE1.2] times pop\n",
 567       "             14 9 [+] . dupdip 231 2 >> 3 [PE1.2] times pop\n",
 568       "                 14 9 . + 9 231 2 >> 3 [PE1.2] times pop\n",
 569       "                   23 . 9 231 2 >> 3 [PE1.2] times pop\n",
 570       "                 23 9 . 231 2 >> 3 [PE1.2] times pop\n",
 571       "             23 9 231 . 2 >> 3 [PE1.2] times pop\n",
 572       "           23 9 231 2 . >> 3 [PE1.2] times pop\n",
 573       "              23 9 57 . 3 [PE1.2] times pop\n",
 574       "            23 9 57 3 . [PE1.2] times pop\n",
 575       "    23 9 57 3 [PE1.2] . times pop\n",
 576       "      23 9 57 [PE1.2] . i 2 [PE1.2] times pop\n",
 577       "              23 9 57 . PE1.2 2 [PE1.2] times pop\n",
 578       "              23 9 57 . [3 & PE1.1] dupdip 2 >> 2 [PE1.2] times pop\n",
 579       "  23 9 57 [3 & PE1.1] . dupdip 2 >> 2 [PE1.2] times pop\n",
 580       "              23 9 57 . 3 & PE1.1 57 2 >> 2 [PE1.2] times pop\n",
 581       "            23 9 57 3 . & PE1.1 57 2 >> 2 [PE1.2] times pop\n",
 582       "               23 9 1 . PE1.1 57 2 >> 2 [PE1.2] times pop\n",
 583       "               23 9 1 . + [+] dupdip 57 2 >> 2 [PE1.2] times pop\n",
 584       "                23 10 . [+] dupdip 57 2 >> 2 [PE1.2] times pop\n",
 585       "            23 10 [+] . dupdip 57 2 >> 2 [PE1.2] times pop\n",
 586       "                23 10 . + 10 57 2 >> 2 [PE1.2] times pop\n",
 587       "                   33 . 10 57 2 >> 2 [PE1.2] times pop\n",
 588       "                33 10 . 57 2 >> 2 [PE1.2] times pop\n",
 589       "             33 10 57 . 2 >> 2 [PE1.2] times pop\n",
 590       "           33 10 57 2 . >> 2 [PE1.2] times pop\n",
 591       "             33 10 14 . 2 [PE1.2] times pop\n",
 592       "           33 10 14 2 . [PE1.2] times pop\n",
 593       "   33 10 14 2 [PE1.2] . times pop\n",
 594       "     33 10 14 [PE1.2] . i 1 [PE1.2] times pop\n",
 595       "             33 10 14 . PE1.2 1 [PE1.2] times pop\n",
 596       "             33 10 14 . [3 & PE1.1] dupdip 2 >> 1 [PE1.2] times pop\n",
 597       " 33 10 14 [3 & PE1.1] . dupdip 2 >> 1 [PE1.2] times pop\n",
 598       "             33 10 14 . 3 & PE1.1 14 2 >> 1 [PE1.2] times pop\n",
 599       "           33 10 14 3 . & PE1.1 14 2 >> 1 [PE1.2] times pop\n",
 600       "              33 10 2 . PE1.1 14 2 >> 1 [PE1.2] times pop\n",
 601       "              33 10 2 . + [+] dupdip 14 2 >> 1 [PE1.2] times pop\n",
 602       "                33 12 . [+] dupdip 14 2 >> 1 [PE1.2] times pop\n",
 603       "            33 12 [+] . dupdip 14 2 >> 1 [PE1.2] times pop\n",
 604       "                33 12 . + 12 14 2 >> 1 [PE1.2] times pop\n",
 605       "                   45 . 12 14 2 >> 1 [PE1.2] times pop\n",
 606       "                45 12 . 14 2 >> 1 [PE1.2] times pop\n",
 607       "             45 12 14 . 2 >> 1 [PE1.2] times pop\n",
 608       "           45 12 14 2 . >> 1 [PE1.2] times pop\n",
 609       "              45 12 3 . 1 [PE1.2] times pop\n",
 610       "            45 12 3 1 . [PE1.2] times pop\n",
 611       "    45 12 3 1 [PE1.2] . times pop\n",
 612       "      45 12 3 [PE1.2] . i pop\n",
 613       "              45 12 3 . PE1.2 pop\n",
 614       "              45 12 3 . [3 & PE1.1] dupdip 2 >> pop\n",
 615       "  45 12 3 [3 & PE1.1] . dupdip 2 >> pop\n",
 616       "              45 12 3 . 3 & PE1.1 3 2 >> pop\n",
 617       "            45 12 3 3 . & PE1.1 3 2 >> pop\n",
 618       "              45 12 3 . PE1.1 3 2 >> pop\n",
 619       "              45 12 3 . + [+] dupdip 3 2 >> pop\n",
 620       "                45 15 . [+] dupdip 3 2 >> pop\n",
 621       "            45 15 [+] . dupdip 3 2 >> pop\n",
 622       "                45 15 . + 15 3 2 >> pop\n",
 623       "                   60 . 15 3 2 >> pop\n",
 624       "                60 15 . 3 2 >> pop\n",
 625       "              60 15 3 . 2 >> pop\n",
 626       "            60 15 3 2 . >> pop\n",
 627       "              60 15 0 . pop\n",
 628       "                60 15 . \n"
 629      ]
 630     }
 631    ],
 632    "source": [
 633     "V('0 0 14811 7 [PE1.2] times pop')"
 634    ]
 635   },
 636   {
 637    "cell_type": "markdown",
 638    "metadata": {},
 639    "source": [
 640     "And so we have at last:"
 641    ]
 642   },
 643   {
 644    "cell_type": "code",
 645    "execution_count": 18,
 646    "metadata": {},
 647    "outputs": [],
 648    "source": [
 649     "define('PE1 == 0 0 66 [14811 7 [PE1.2] times pop] times 14811 4 [PE1.2] times popop')"
 650    ]
 651   },
 652   {
 653    "cell_type": "code",
 654    "execution_count": 19,
 655    "metadata": {
 656     "scrolled": true
 657    },
 658    "outputs": [
 659     {
 660      "name": "stdout",
 661      "output_type": "stream",
 662      "text": [
 663       "233168\n"
 664      ]
 665     }
 666    ],
 667    "source": [
 668     "J('PE1')"
 669    ]
 670   },
 671   {
 672    "cell_type": "markdown",
 673    "metadata": {},
 674    "source": [
 675     "Let's refactor.\n",
 676     "\n",
 677     "      14811 7 [PE1.2] times pop\n",
 678     "      14811 4 [PE1.2] times pop\n",
 679     "      14811 n [PE1.2] times pop\n",
 680     "    n 14811 swap [PE1.2] times pop"
 681    ]
 682   },
 683   {
 684    "cell_type": "code",
 685    "execution_count": 20,
 686    "metadata": {},
 687    "outputs": [],
 688    "source": [
 689     "define('PE1.3 == 14811 swap [PE1.2] times pop')"
 690    ]
 691   },
 692   {
 693    "cell_type": "markdown",
 694    "metadata": {},
 695    "source": [
 696     "Now we can simplify the definition above:"
 697    ]
 698   },
 699   {
 700    "cell_type": "code",
 701    "execution_count": 21,
 702    "metadata": {},
 703    "outputs": [],
 704    "source": [
 705     "define('PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop')"
 706    ]
 707   },
 708   {
 709    "cell_type": "code",
 710    "execution_count": 22,
 711    "metadata": {
 712     "scrolled": true
 713    },
 714    "outputs": [
 715     {
 716      "name": "stdout",
 717      "output_type": "stream",
 718      "text": [
 719       "233168\n"
 720      ]
 721     }
 722    ],
 723    "source": [
 724     "J('PE1')"
 725    ]
 726   },
 727   {
 728    "cell_type": "markdown",
 729    "metadata": {},
 730    "source": [
 731     "Here's our joy program all in one place.  It doesn't make so much sense, but if you have read through the above description of how it was derived I hope it's clear.\n",
 732     "\n",
 733     "    PE1.1 == + [+] dupdip\n",
 734     "    PE1.2 == [3 & PE1.1] dupdip 2 >>\n",
 735     "    PE1.3 == 14811 swap [PE1.2] times pop\n",
 736     "    PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop"
 737    ]
 738   },
 739   {
 740    "cell_type": "markdown",
 741    "metadata": {},
 742    "source": [
 743     "# Generator Version\n",
 744     "It's a little clunky iterating sixty-six times though the seven numbers then four more.  In the _Generator Programs_ notebook we derive a generator that can be repeatedly driven by the `x` combinator to produce a stream of the seven numbers repeating over and over again."
 745    ]
 746   },
 747   {
 748    "cell_type": "code",
 749    "execution_count": 23,
 750    "metadata": {},
 751    "outputs": [],
 752    "source": [
 753     "define('PE1.terms == [0 swap [dup [pop 14811] [] branch [3 &] dupdip 2 >>] dip rest cons]')"
 754    ]
 755   },
 756   {
 757    "cell_type": "code",
 758    "execution_count": 24,
 759    "metadata": {
 760     "scrolled": true
 761    },
 762    "outputs": [
 763     {
 764      "name": "stdout",
 765      "output_type": "stream",
 766      "text": [
 767       "3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 [0 swap [dup [pop 14811] [] branch [3 &] dupdip 2 >>] dip rest cons]\n"
 768      ]
 769     }
 770    ],
 771    "source": [
 772     "J('PE1.terms 21 [x] times')"
 773    ]
 774   },
 775   {
 776    "cell_type": "markdown",
 777    "metadata": {},
 778    "source": [
 779     "We know from above that we need sixty-six times seven then four more terms to reach up to but not over one thousand."
 780    ]
 781   },
 782   {
 783    "cell_type": "code",
 784    "execution_count": 25,
 785    "metadata": {},
 786    "outputs": [
 787     {
 788      "name": "stdout",
 789      "output_type": "stream",
 790      "text": [
 791       "466\n"
 792      ]
 793     }
 794    ],
 795    "source": [
 796     "J('7 66 * 4 +')"
 797    ]
 798   },
 799   {
 800    "cell_type": "markdown",
 801    "metadata": {},
 802    "source": [
 803     "### Here they are..."
 804    ]
 805   },
 806   {
 807    "cell_type": "code",
 808    "execution_count": 26,
 809    "metadata": {
 810     "scrolled": true
 811    },
 812    "outputs": [
 813     {
 814      "name": "stdout",
 815      "output_type": "stream",
 816      "text": [
 817       "3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 2 1 3\n"
 818      ]
 819     }
 820    ],
 821    "source": [
 822     "J('PE1.terms 466 [x] times pop')"
 823    ]
 824   },
 825   {
 826    "cell_type": "markdown",
 827    "metadata": {},
 828    "source": [
 829     "### ...and they do sum to 999."
 830    ]
 831   },
 832   {
 833    "cell_type": "code",
 834    "execution_count": 27,
 835    "metadata": {
 836     "scrolled": true
 837    },
 838    "outputs": [
 839     {
 840      "name": "stdout",
 841      "output_type": "stream",
 842      "text": [
 843       "999\n"
 844      ]
 845     }
 846    ],
 847    "source": [
 848     "J('[PE1.terms 466 [x] times pop] run sum')"
 849    ]
 850   },
 851   {
 852    "cell_type": "markdown",
 853    "metadata": {},
 854    "source": [
 855     "Now we can use `PE1.1` to accumulate the terms as we go, and then `pop` the generator and the counter from the stack when we're done, leaving just the sum."
 856    ]
 857   },
 858   {
 859    "cell_type": "code",
 860    "execution_count": 28,
 861    "metadata": {
 862     "scrolled": true
 863    },
 864    "outputs": [
 865     {
 866      "name": "stdout",
 867      "output_type": "stream",
 868      "text": [
 869       "233168\n"
 870      ]
 871     }
 872    ],
 873    "source": [
 874     "J('0 0 PE1.terms 466 [x [PE1.1] dip] times popop')"
 875    ]
 876   },
 877   {
 878    "cell_type": "markdown",
 879    "metadata": {},
 880    "source": [
 881     "# A little further analysis renders iteration unnecessary.\n",
 882     "Consider finding the sum of the positive integers less than or equal to ten."
 883    ]
 884   },
 885   {
 886    "cell_type": "code",
 887    "execution_count": 29,
 888    "metadata": {},
 889    "outputs": [
 890     {
 891      "name": "stdout",
 892      "output_type": "stream",
 893      "text": [
 894       "55\n"
 895      ]
 896     }
 897    ],
 898    "source": [
 899     "J('[10 9 8 7 6 5 4 3 2 1] sum')"
 900    ]
 901   },
 902   {
 903    "cell_type": "markdown",
 904    "metadata": {},
 905    "source": [
 906     "Instead of summing them, [observe](https://en.wikipedia.org/wiki/File:Animated_proof_for_the_formula_giving_the_sum_of_the_first_integers_1%2B2%2B...%2Bn.gif):\n",
 907     "\n",
 908     "      10  9  8  7  6\n",
 909     "    +  1  2  3  4  5\n",
 910     "    ---- -- -- -- --\n",
 911     "      11 11 11 11 11\n",
 912     "      \n",
 913     "      11 * 5 = 55\n",
 914     "\n",
 915     "From the above example we can deduce that the sum of the first N positive integers is:\n",
 916     "\n",
 917     "    (N + 1) * N / 2 \n",
 918     "\n",
 919     "(The formula also works for odd values of N, I'll leave that to you if you want to work it out or you can take my word for it.)"
 920    ]
 921   },
 922   {
 923    "cell_type": "code",
 924    "execution_count": 30,
 925    "metadata": {},
 926    "outputs": [],
 927    "source": [
 928     "define('F == dup ++ * 2 floordiv')"
 929    ]
 930   },
 931   {
 932    "cell_type": "code",
 933    "execution_count": 31,
 934    "metadata": {},
 935    "outputs": [
 936     {
 937      "name": "stdout",
 938      "output_type": "stream",
 939      "text": [
 940       "      . 10 F\n",
 941       "   10 . F\n",
 942       "   10 . dup ++ * 2 floordiv\n",
 943       "10 10 . ++ * 2 floordiv\n",
 944       "10 11 . * 2 floordiv\n",
 945       "  110 . 2 floordiv\n",
 946       "110 2 . floordiv\n",
 947       "   55 . \n"
 948      ]
 949     }
 950    ],
 951    "source": [
 952     "V('10 F')"
 953    ]
 954   },
 955   {
 956    "cell_type": "markdown",
 957    "metadata": {},
 958    "source": [
 959     "## Generalizing to Blocks of Terms\n",
 960     "We can apply the same reasoning to the PE1 problem.\n",
 961     "\n",
 962     "Between 0 and 990 inclusive there are sixty-six \"blocks\" of seven terms each, starting with:\n",
 963     "\n",
 964     "    [3 5 6 9 10 12 15]\n",
 965     "    \n",
 966     "And ending with:\n",
 967     "\n",
 968     "    [978 980 981 984 985 987 990]\n",
 969     "    \n",
 970     "If we reverse one of these two blocks and sum pairs..."
 971    ]
 972   },
 973   {
 974    "cell_type": "code",
 975    "execution_count": 32,
 976    "metadata": {
 977     "scrolled": true
 978    },
 979    "outputs": [
 980     {
 981      "name": "stdout",
 982      "output_type": "stream",
 983      "text": [
 984       "[[978 15] [980 12] [981 10] [984 9] [985 6] [987 5] [990 3]]\n"
 985      ]
 986     }
 987    ],
 988    "source": [
 989     "J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip')"
 990    ]
 991   },
 992   {
 993    "cell_type": "code",
 994    "execution_count": 33,
 995    "metadata": {
 996     "scrolled": true
 997    },
 998    "outputs": [
 999     {
1000      "name": "stdout",
1001      "output_type": "stream",
1002      "text": [
1003       "[993 992 991 993 991 992 993]\n"
1004      ]
1005     }
1006    ],
1007    "source": [
1008     "J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map')"
1009    ]
1010   },
1011   {
1012    "cell_type": "markdown",
1013    "metadata": {},
1014    "source": [
1015     "(Interesting that the sequence of seven numbers appears again in the rightmost digit of each term.)"
1016    ]
1017   },
1018   {
1019    "cell_type": "code",
1020    "execution_count": 34,
1021    "metadata": {
1022     "scrolled": true
1023    },
1024    "outputs": [
1025     {
1026      "name": "stdout",
1027      "output_type": "stream",
1028      "text": [
1029       "6945\n"
1030      ]
1031     }
1032    ],
1033    "source": [
1034     "J('[ 3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map sum')"
1035    ]
1036   },
1037   {
1038    "cell_type": "markdown",
1039    "metadata": {},
1040    "source": [
1041     "Since there are sixty-six blocks and we are pairing them up, there must be thirty-three pairs, each of which sums to 6945.  We also have these additional unpaired terms between 990 and 1000:\n",
1042     "\n",
1043     "    993 995 996 999\n",
1044     "    \n",
1045     "So we can give the \"sum of all the multiples of 3 or 5 below 1000\" like so:"
1046    ]
1047   },
1048   {
1049    "cell_type": "code",
1050    "execution_count": 35,
1051    "metadata": {},
1052    "outputs": [
1053     {
1054      "name": "stdout",
1055      "output_type": "stream",
1056      "text": [
1057       "233168\n"
1058      ]
1059     }
1060    ],
1061    "source": [
1062     "J('6945 33 * [993 995 996 999] cons sum')"
1063    ]
1064   },
1065   {
1066    "cell_type": "markdown",
1067    "metadata": {},
1068    "source": [
1069     "It's worth noting, I think, that this same reasoning holds for any two numbers $n$ and $m$ the multiples of which we hope to sum.  The multiples would have a cycle of differences of length $k$ and so we could compute the sum of $Nk$ multiples as above.\n",
1070     "\n",
1071     "The sequence of differences will always be a palidrome.  Consider an interval spanning the least common multiple of $n$ and $m$:\n",
1072     "\n",
1073     "    |   |   |   |   |   |   |   |\n",
1074     "    |      |      |      |      |\n",
1075     "    \n",
1076     "Here we have 4 and 7, and you can read off the sequence of differences directly from the diagram: 4 3 1 4 2 2 4 1 3 4.\n",
1077     "    \n",
1078     "Geometrically, the actual values of $n$ and $m$ and their *lcm* don't matter, the pattern they make will always be symmetrical around its midpoint.  The same reasoning holds for multiples of more than two numbers."
1079    ]
1080   },
1081   {
1082    "cell_type": "markdown",
1083    "metadata": {},
1084    "source": [
1085     "# The Simplest Program"
1086    ]
1087   },
1088   {
1089    "cell_type": "markdown",
1090    "metadata": {},
1091    "source": [
1092     "Of course, the simplest joy program for the first Project Euler problem is just:\n",
1093     "\n",
1094     "    PE1 == 233168\n",
1095     "\n",
1096     "Fin."
1097    ]
1098   }
1099  ],
1100  "metadata": {
1101   "kernelspec": {
1102    "display_name": "Python 2",
1103    "language": "python",
1104    "name": "python2"
1105   },
1106   "language_info": {
1107    "codemirror_mode": {
1108     "name": "ipython",
1109     "version": 2
1110    },
1111    "file_extension": ".py",
1112    "mimetype": "text/x-python",
1113    "name": "python",
1114    "nbconvert_exporter": "python",
1115    "pygments_lexer": "ipython2",
1116    "version": "2.7.12"
1117   }
1118  },
1119  "nbformat": 4,
1120  "nbformat_minor": 2
1121 }