docs/sphinx_docs/_build/html/_sources/notebooks/Developing.rst.txt

   1 ***************************
   2 Developing a Program in Joy
   3 ***************************
   4
   5 As an example of developing a program in Joy let's take the first problem from the Project Euler website.
   6
   7 `Project Euler, first problem: "Multiples of 3 and 5" <https://projecteuler.net/problem=1>`__
   8 =============================================================================================
   9
  10
  11     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.
  12
  13     Find the sum of all the multiples of 3 or 5 below 1000.
  14
  15 .. code:: ipython2
  16
  17     from notebook_preamble import J, V, define
  18
  19 Sum a range filtered by a predicate
  20 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  21
  22 Let's create a predicate that returns ``True`` if a number is a multiple
  23 of 3 or 5 and ``False`` otherwise.
  24
  25 .. code:: ipython2
  26
  27     define('P == [3 % not] dupdip 5 % not or')
  28
  29 .. code:: ipython2
  30
  31     V('80 P')
  32
  33
  34 .. parsed-literal::
  35
  36                  . 80 P
  37               80 . P
  38               80 . [3 % not] dupdip 5 % not or
  39     80 [3 % not] . dupdip 5 % not or
  40               80 . 3 % not 80 5 % not or
  41             80 3 . % not 80 5 % not or
  42                2 . not 80 5 % not or
  43            False . 80 5 % not or
  44         False 80 . 5 % not or
  45       False 80 5 . % not or
  46          False 0 . not or
  47       False True . or
  48             True .
  49
  50
  51 Given the predicate function ``P`` a suitable program is:
  52
  53 ::
  54
  55     PE1 == 1000 range [P] filter sum
  56
  57 This function generates a list of the integers from 0 to 999, filters
  58 that list by ``P``, and then sums the result.
  59
  60 Logically this is fine, but pragmatically we are doing more work than we
  61 should be; we generate one thousand integers but actually use less than
  62 half of them. A better solution would be to generate just the multiples
  63 we want to sum, and to add them as we go rather than storing them and
  64 and summing them at the end.
  65
  66 Generate just the multiples
  67 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  68
  69 At first I had the idea to use two counters and increase them by three
  70 and five, respectively. This way we only generate the terms that we
  71 actually want to sum. We have to proceed by incrementing the counter
  72 that is lower, or if they are equal, the three counter, and we have to
  73 take care not to double add numbers like 15 that are multiples of both
  74 three and five.
  75
  76 This seemed a little clunky, so I tried a different approach.
  77
  78 Consider the first few terms in the series:
  79
  80 ::
  81
  82     3 5 6 9 10 12 15 18 20 21 ...
  83
  84 Subtract each number from the one after it (subtracting 0 from 3):
  85
  86 ::
  87
  88     3 5 6 9 10 12 15 18 20 21 24 25 27 30 ...
  89     0 3 5 6  9 10 12 15 18 20 21 24 25 27 ...
  90     -------------------------------------------
  91     3 2 1 3  1  2  3  3  2  1  3  1  2  3 ...
  92
  93 You get this lovely repeating palindromic sequence:
  94
  95 ::
  96
  97     3 2 1 3 1 2 3
  98
  99 To make a counter that increments by factors of 3 and 5 you just add
 100 these differences to the counter one-by-one in a loop.
 101
 102 To make use of this sequence to increment a counter and sum terms as we
 103 go we need a function that will accept the sum, the counter, and the
 104 next term to add, and that adds the term to the counter and a copy of
 105 the counter to the running sum. This function will do that:
 106
 107 ::
 108
 109     PE1.1 == + [+] dupdip
 110
 111 .. code:: ipython2
 112
 113     define('PE1.1 == + [+] dupdip')
 114
 115 .. code:: ipython2
 116
 117     V('0 0 3 PE1.1')
 118
 119
 120 .. parsed-literal::
 121
 122             . 0 0 3 PE1.1
 123           0 . 0 3 PE1.1
 124         0 0 . 3 PE1.1
 125       0 0 3 . PE1.1
 126       0 0 3 . + [+] dupdip
 127         0 3 . [+] dupdip
 128     0 3 [+] . dupdip
 129         0 3 . + 3
 130           3 . 3
 131         3 3 .
 132
 133
 134 .. code:: ipython2
 135
 136     V('0 0 [3 2 1 3 1 2 3] [PE1.1] step')
 137
 138
 139 .. parsed-literal::
 140
 141                                 . 0 0 [3 2 1 3 1 2 3] [PE1.1] step
 142                               0 . 0 [3 2 1 3 1 2 3] [PE1.1] step
 143                             0 0 . [3 2 1 3 1 2 3] [PE1.1] step
 144             0 0 [3 2 1 3 1 2 3] . [PE1.1] step
 145     0 0 [3 2 1 3 1 2 3] [PE1.1] . step
 146                   0 0 3 [PE1.1] . i [2 1 3 1 2 3] [PE1.1] step
 147                           0 0 3 . PE1.1 [2 1 3 1 2 3] [PE1.1] step
 148                           0 0 3 . + [+] dupdip [2 1 3 1 2 3] [PE1.1] step
 149                             0 3 . [+] dupdip [2 1 3 1 2 3] [PE1.1] step
 150                         0 3 [+] . dupdip [2 1 3 1 2 3] [PE1.1] step
 151                             0 3 . + 3 [2 1 3 1 2 3] [PE1.1] step
 152                               3 . 3 [2 1 3 1 2 3] [PE1.1] step
 153                             3 3 . [2 1 3 1 2 3] [PE1.1] step
 154               3 3 [2 1 3 1 2 3] . [PE1.1] step
 155       3 3 [2 1 3 1 2 3] [PE1.1] . step
 156                   3 3 2 [PE1.1] . i [1 3 1 2 3] [PE1.1] step
 157                           3 3 2 . PE1.1 [1 3 1 2 3] [PE1.1] step
 158                           3 3 2 . + [+] dupdip [1 3 1 2 3] [PE1.1] step
 159                             3 5 . [+] dupdip [1 3 1 2 3] [PE1.1] step
 160                         3 5 [+] . dupdip [1 3 1 2 3] [PE1.1] step
 161                             3 5 . + 5 [1 3 1 2 3] [PE1.1] step
 162                               8 . 5 [1 3 1 2 3] [PE1.1] step
 163                             8 5 . [1 3 1 2 3] [PE1.1] step
 164                 8 5 [1 3 1 2 3] . [PE1.1] step
 165         8 5 [1 3 1 2 3] [PE1.1] . step
 166                   8 5 1 [PE1.1] . i [3 1 2 3] [PE1.1] step
 167                           8 5 1 . PE1.1 [3 1 2 3] [PE1.1] step
 168                           8 5 1 . + [+] dupdip [3 1 2 3] [PE1.1] step
 169                             8 6 . [+] dupdip [3 1 2 3] [PE1.1] step
 170                         8 6 [+] . dupdip [3 1 2 3] [PE1.1] step
 171                             8 6 . + 6 [3 1 2 3] [PE1.1] step
 172                              14 . 6 [3 1 2 3] [PE1.1] step
 173                            14 6 . [3 1 2 3] [PE1.1] step
 174                  14 6 [3 1 2 3] . [PE1.1] step
 175          14 6 [3 1 2 3] [PE1.1] . step
 176                  14 6 3 [PE1.1] . i [1 2 3] [PE1.1] step
 177                          14 6 3 . PE1.1 [1 2 3] [PE1.1] step
 178                          14 6 3 . + [+] dupdip [1 2 3] [PE1.1] step
 179                            14 9 . [+] dupdip [1 2 3] [PE1.1] step
 180                        14 9 [+] . dupdip [1 2 3] [PE1.1] step
 181                            14 9 . + 9 [1 2 3] [PE1.1] step
 182                              23 . 9 [1 2 3] [PE1.1] step
 183                            23 9 . [1 2 3] [PE1.1] step
 184                    23 9 [1 2 3] . [PE1.1] step
 185            23 9 [1 2 3] [PE1.1] . step
 186                  23 9 1 [PE1.1] . i [2 3] [PE1.1] step
 187                          23 9 1 . PE1.1 [2 3] [PE1.1] step
 188                          23 9 1 . + [+] dupdip [2 3] [PE1.1] step
 189                           23 10 . [+] dupdip [2 3] [PE1.1] step
 190                       23 10 [+] . dupdip [2 3] [PE1.1] step
 191                           23 10 . + 10 [2 3] [PE1.1] step
 192                              33 . 10 [2 3] [PE1.1] step
 193                           33 10 . [2 3] [PE1.1] step
 194                     33 10 [2 3] . [PE1.1] step
 195             33 10 [2 3] [PE1.1] . step
 196                 33 10 2 [PE1.1] . i [3] [PE1.1] step
 197                         33 10 2 . PE1.1 [3] [PE1.1] step
 198                         33 10 2 . + [+] dupdip [3] [PE1.1] step
 199                           33 12 . [+] dupdip [3] [PE1.1] step
 200                       33 12 [+] . dupdip [3] [PE1.1] step
 201                           33 12 . + 12 [3] [PE1.1] step
 202                              45 . 12 [3] [PE1.1] step
 203                           45 12 . [3] [PE1.1] step
 204                       45 12 [3] . [PE1.1] step
 205               45 12 [3] [PE1.1] . step
 206                 45 12 3 [PE1.1] . i
 207                         45 12 3 . PE1.1
 208                         45 12 3 . + [+] dupdip
 209                           45 15 . [+] dupdip
 210                       45 15 [+] . dupdip
 211                           45 15 . + 15
 212                              60 . 15
 213                           60 15 .
 214
 215
 216 So one ``step`` through all seven terms brings the counter to 15 and the
 217 total to 60.
 218
 219 How many multiples to sum?
 220 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 221
 222 .. code:: ipython2
 223
 224     1000 / 15
 225
 226
 227
 228
 229 .. parsed-literal::
 230
 231     66
 232
 233
 234
 235 .. code:: ipython2
 236
 237     66 * 15
 238
 239
 240
 241
 242 .. parsed-literal::
 243
 244     990
 245
 246
 247
 248 .. code:: ipython2
 249
 250     1000 - 990
 251
 252
 253
 254
 255 .. parsed-literal::
 256
 257     10
 258
 259
 260
 261 We only want the terms *less than* 1000.
 262
 263 .. code:: ipython2
 264
 265     999 - 990
 266
 267
 268
 269
 270 .. parsed-literal::
 271
 272     9
 273
 274
 275
 276 That means we want to run the full list of numbers sixty-six times to
 277 get to 990 and then the first four numbers 3 2 1 3 to get to 999.
 278
 279 .. code:: ipython2
 280
 281     define('PE1 == 0 0 66 [[3 2 1 3 1 2 3] [PE1.1] step] times [3 2 1 3] [PE1.1] step pop')
 282
 283 .. code:: ipython2
 284
 285     J('PE1')
 286
 287
 288 .. parsed-literal::
 289
 290     233168
 291
 292 Packing the terms into an integer
 293 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 294
 295 This form uses no extra storage and produces no unused summands. It's
 296 good but there's one more trick we can apply. The list of seven terms
 297 takes up at least seven bytes. But notice that all of the terms are less
 298 than four, and so each can fit in just two bits. We could store all
 299 seven terms in just fourteen bits and use masking and shifts to pick out
 300 each term as we go. This will use less space and save time loading whole
 301 integer terms from the list.
 302
 303 ::
 304
 305         3  2  1  3  1  2  3
 306     0b 11 10 01 11 01 10 11 == 14811
 307
 308 .. code:: ipython2
 309
 310     0b11100111011011
 311
 312
 313
 314
 315 .. parsed-literal::
 316
 317     14811
 318
 319
 320
 321 .. code:: ipython2
 322
 323     define('PE1.2 == [3 & PE1.1] dupdip 2 >>')
 324
 325 .. code:: ipython2
 326
 327     V('0 0 14811 PE1.2')
 328
 329
 330 .. parsed-literal::
 331
 332                           . 0 0 14811 PE1.2
 333                         0 . 0 14811 PE1.2
 334                       0 0 . 14811 PE1.2
 335                 0 0 14811 . PE1.2
 336                 0 0 14811 . [3 & PE1.1] dupdip 2 >>
 337     0 0 14811 [3 & PE1.1] . dupdip 2 >>
 338                 0 0 14811 . 3 & PE1.1 14811 2 >>
 339               0 0 14811 3 . & PE1.1 14811 2 >>
 340                     0 0 3 . PE1.1 14811 2 >>
 341                     0 0 3 . + [+] dupdip 14811 2 >>
 342                       0 3 . [+] dupdip 14811 2 >>
 343                   0 3 [+] . dupdip 14811 2 >>
 344                       0 3 . + 3 14811 2 >>
 345                         3 . 3 14811 2 >>
 346                       3 3 . 14811 2 >>
 347                 3 3 14811 . 2 >>
 348               3 3 14811 2 . >>
 349                  3 3 3702 .
 350
 351
 352 .. code:: ipython2
 353
 354     V('3 3 3702 PE1.2')
 355
 356
 357 .. parsed-literal::
 358
 359                          . 3 3 3702 PE1.2
 360                        3 . 3 3702 PE1.2
 361                      3 3 . 3702 PE1.2
 362                 3 3 3702 . PE1.2
 363                 3 3 3702 . [3 & PE1.1] dupdip 2 >>
 364     3 3 3702 [3 & PE1.1] . dupdip 2 >>
 365                 3 3 3702 . 3 & PE1.1 3702 2 >>
 366               3 3 3702 3 . & PE1.1 3702 2 >>
 367                    3 3 2 . PE1.1 3702 2 >>
 368                    3 3 2 . + [+] dupdip 3702 2 >>
 369                      3 5 . [+] dupdip 3702 2 >>
 370                  3 5 [+] . dupdip 3702 2 >>
 371                      3 5 . + 5 3702 2 >>
 372                        8 . 5 3702 2 >>
 373                      8 5 . 3702 2 >>
 374                 8 5 3702 . 2 >>
 375               8 5 3702 2 . >>
 376                  8 5 925 .
 377
 378
 379 .. code:: ipython2
 380
 381     V('0 0 14811 7 [PE1.2] times pop')
 382
 383
 384 .. parsed-literal::
 385
 386                           . 0 0 14811 7 [PE1.2] times pop
 387                         0 . 0 14811 7 [PE1.2] times pop
 388                       0 0 . 14811 7 [PE1.2] times pop
 389                 0 0 14811 . 7 [PE1.2] times pop
 390               0 0 14811 7 . [PE1.2] times pop
 391       0 0 14811 7 [PE1.2] . times pop
 392         0 0 14811 [PE1.2] . i 6 [PE1.2] times pop
 393                 0 0 14811 . PE1.2 6 [PE1.2] times pop
 394                 0 0 14811 . [3 & PE1.1] dupdip 2 >> 6 [PE1.2] times pop
 395     0 0 14811 [3 & PE1.1] . dupdip 2 >> 6 [PE1.2] times pop
 396                 0 0 14811 . 3 & PE1.1 14811 2 >> 6 [PE1.2] times pop
 397               0 0 14811 3 . & PE1.1 14811 2 >> 6 [PE1.2] times pop
 398                     0 0 3 . PE1.1 14811 2 >> 6 [PE1.2] times pop
 399                     0 0 3 . + [+] dupdip 14811 2 >> 6 [PE1.2] times pop
 400                       0 3 . [+] dupdip 14811 2 >> 6 [PE1.2] times pop
 401                   0 3 [+] . dupdip 14811 2 >> 6 [PE1.2] times pop
 402                       0 3 . + 3 14811 2 >> 6 [PE1.2] times pop
 403                         3 . 3 14811 2 >> 6 [PE1.2] times pop
 404                       3 3 . 14811 2 >> 6 [PE1.2] times pop
 405                 3 3 14811 . 2 >> 6 [PE1.2] times pop
 406               3 3 14811 2 . >> 6 [PE1.2] times pop
 407                  3 3 3702 . 6 [PE1.2] times pop
 408                3 3 3702 6 . [PE1.2] times pop
 409        3 3 3702 6 [PE1.2] . times pop
 410          3 3 3702 [PE1.2] . i 5 [PE1.2] times pop
 411                  3 3 3702 . PE1.2 5 [PE1.2] times pop
 412                  3 3 3702 . [3 & PE1.1] dupdip 2 >> 5 [PE1.2] times pop
 413      3 3 3702 [3 & PE1.1] . dupdip 2 >> 5 [PE1.2] times pop
 414                  3 3 3702 . 3 & PE1.1 3702 2 >> 5 [PE1.2] times pop
 415                3 3 3702 3 . & PE1.1 3702 2 >> 5 [PE1.2] times pop
 416                     3 3 2 . PE1.1 3702 2 >> 5 [PE1.2] times pop
 417                     3 3 2 . + [+] dupdip 3702 2 >> 5 [PE1.2] times pop
 418                       3 5 . [+] dupdip 3702 2 >> 5 [PE1.2] times pop
 419                   3 5 [+] . dupdip 3702 2 >> 5 [PE1.2] times pop
 420                       3 5 . + 5 3702 2 >> 5 [PE1.2] times pop
 421                         8 . 5 3702 2 >> 5 [PE1.2] times pop
 422                       8 5 . 3702 2 >> 5 [PE1.2] times pop
 423                  8 5 3702 . 2 >> 5 [PE1.2] times pop
 424                8 5 3702 2 . >> 5 [PE1.2] times pop
 425                   8 5 925 . 5 [PE1.2] times pop
 426                 8 5 925 5 . [PE1.2] times pop
 427         8 5 925 5 [PE1.2] . times pop
 428           8 5 925 [PE1.2] . i 4 [PE1.2] times pop
 429                   8 5 925 . PE1.2 4 [PE1.2] times pop
 430                   8 5 925 . [3 & PE1.1] dupdip 2 >> 4 [PE1.2] times pop
 431       8 5 925 [3 & PE1.1] . dupdip 2 >> 4 [PE1.2] times pop
 432                   8 5 925 . 3 & PE1.1 925 2 >> 4 [PE1.2] times pop
 433                 8 5 925 3 . & PE1.1 925 2 >> 4 [PE1.2] times pop
 434                     8 5 1 . PE1.1 925 2 >> 4 [PE1.2] times pop
 435                     8 5 1 . + [+] dupdip 925 2 >> 4 [PE1.2] times pop
 436                       8 6 . [+] dupdip 925 2 >> 4 [PE1.2] times pop
 437                   8 6 [+] . dupdip 925 2 >> 4 [PE1.2] times pop
 438                       8 6 . + 6 925 2 >> 4 [PE1.2] times pop
 439                        14 . 6 925 2 >> 4 [PE1.2] times pop
 440                      14 6 . 925 2 >> 4 [PE1.2] times pop
 441                  14 6 925 . 2 >> 4 [PE1.2] times pop
 442                14 6 925 2 . >> 4 [PE1.2] times pop
 443                  14 6 231 . 4 [PE1.2] times pop
 444                14 6 231 4 . [PE1.2] times pop
 445        14 6 231 4 [PE1.2] . times pop
 446          14 6 231 [PE1.2] . i 3 [PE1.2] times pop
 447                  14 6 231 . PE1.2 3 [PE1.2] times pop
 448                  14 6 231 . [3 & PE1.1] dupdip 2 >> 3 [PE1.2] times pop
 449      14 6 231 [3 & PE1.1] . dupdip 2 >> 3 [PE1.2] times pop
 450                  14 6 231 . 3 & PE1.1 231 2 >> 3 [PE1.2] times pop
 451                14 6 231 3 . & PE1.1 231 2 >> 3 [PE1.2] times pop
 452                    14 6 3 . PE1.1 231 2 >> 3 [PE1.2] times pop
 453                    14 6 3 . + [+] dupdip 231 2 >> 3 [PE1.2] times pop
 454                      14 9 . [+] dupdip 231 2 >> 3 [PE1.2] times pop
 455                  14 9 [+] . dupdip 231 2 >> 3 [PE1.2] times pop
 456                      14 9 . + 9 231 2 >> 3 [PE1.2] times pop
 457                        23 . 9 231 2 >> 3 [PE1.2] times pop
 458                      23 9 . 231 2 >> 3 [PE1.2] times pop
 459                  23 9 231 . 2 >> 3 [PE1.2] times pop
 460                23 9 231 2 . >> 3 [PE1.2] times pop
 461                   23 9 57 . 3 [PE1.2] times pop
 462                 23 9 57 3 . [PE1.2] times pop
 463         23 9 57 3 [PE1.2] . times pop
 464           23 9 57 [PE1.2] . i 2 [PE1.2] times pop
 465                   23 9 57 . PE1.2 2 [PE1.2] times pop
 466                   23 9 57 . [3 & PE1.1] dupdip 2 >> 2 [PE1.2] times pop
 467       23 9 57 [3 & PE1.1] . dupdip 2 >> 2 [PE1.2] times pop
 468                   23 9 57 . 3 & PE1.1 57 2 >> 2 [PE1.2] times pop
 469                 23 9 57 3 . & PE1.1 57 2 >> 2 [PE1.2] times pop
 470                    23 9 1 . PE1.1 57 2 >> 2 [PE1.2] times pop
 471                    23 9 1 . + [+] dupdip 57 2 >> 2 [PE1.2] times pop
 472                     23 10 . [+] dupdip 57 2 >> 2 [PE1.2] times pop
 473                 23 10 [+] . dupdip 57 2 >> 2 [PE1.2] times pop
 474                     23 10 . + 10 57 2 >> 2 [PE1.2] times pop
 475                        33 . 10 57 2 >> 2 [PE1.2] times pop
 476                     33 10 . 57 2 >> 2 [PE1.2] times pop
 477                  33 10 57 . 2 >> 2 [PE1.2] times pop
 478                33 10 57 2 . >> 2 [PE1.2] times pop
 479                  33 10 14 . 2 [PE1.2] times pop
 480                33 10 14 2 . [PE1.2] times pop
 481        33 10 14 2 [PE1.2] . times pop
 482          33 10 14 [PE1.2] . i 1 [PE1.2] times pop
 483                  33 10 14 . PE1.2 1 [PE1.2] times pop
 484                  33 10 14 . [3 & PE1.1] dupdip 2 >> 1 [PE1.2] times pop
 485      33 10 14 [3 & PE1.1] . dupdip 2 >> 1 [PE1.2] times pop
 486                  33 10 14 . 3 & PE1.1 14 2 >> 1 [PE1.2] times pop
 487                33 10 14 3 . & PE1.1 14 2 >> 1 [PE1.2] times pop
 488                   33 10 2 . PE1.1 14 2 >> 1 [PE1.2] times pop
 489                   33 10 2 . + [+] dupdip 14 2 >> 1 [PE1.2] times pop
 490                     33 12 . [+] dupdip 14 2 >> 1 [PE1.2] times pop
 491                 33 12 [+] . dupdip 14 2 >> 1 [PE1.2] times pop
 492                     33 12 . + 12 14 2 >> 1 [PE1.2] times pop
 493                        45 . 12 14 2 >> 1 [PE1.2] times pop
 494                     45 12 . 14 2 >> 1 [PE1.2] times pop
 495                  45 12 14 . 2 >> 1 [PE1.2] times pop
 496                45 12 14 2 . >> 1 [PE1.2] times pop
 497                   45 12 3 . 1 [PE1.2] times pop
 498                 45 12 3 1 . [PE1.2] times pop
 499         45 12 3 1 [PE1.2] . times pop
 500           45 12 3 [PE1.2] . i pop
 501                   45 12 3 . PE1.2 pop
 502                   45 12 3 . [3 & PE1.1] dupdip 2 >> pop
 503       45 12 3 [3 & PE1.1] . dupdip 2 >> pop
 504                   45 12 3 . 3 & PE1.1 3 2 >> pop
 505                 45 12 3 3 . & PE1.1 3 2 >> pop
 506                   45 12 3 . PE1.1 3 2 >> pop
 507                   45 12 3 . + [+] dupdip 3 2 >> pop
 508                     45 15 . [+] dupdip 3 2 >> pop
 509                 45 15 [+] . dupdip 3 2 >> pop
 510                     45 15 . + 15 3 2 >> pop
 511                        60 . 15 3 2 >> pop
 512                     60 15 . 3 2 >> pop
 513                   60 15 3 . 2 >> pop
 514                 60 15 3 2 . >> pop
 515                   60 15 0 . pop
 516                     60 15 .
 517
 518
 519 And so we have at last:
 520
 521 .. code:: ipython2
 522
 523     define('PE1 == 0 0 66 [14811 7 [PE1.2] times pop] times 14811 4 [PE1.2] times popop')
 524
 525 .. code:: ipython2
 526
 527     J('PE1')
 528
 529
 530 .. parsed-literal::
 531
 532     233168
 533
 534
 535 Let's refactor
 536 ^^^^^^^^^^^^^^^
 537
 538 ::
 539
 540       14811 7 [PE1.2] times pop
 541       14811 4 [PE1.2] times pop
 542       14811 n [PE1.2] times pop
 543     n 14811 swap [PE1.2] times pop
 544
 545 .. code:: ipython2
 546
 547     define('PE1.3 == 14811 swap [PE1.2] times pop')
 548
 549 Now we can simplify the definition above:
 550
 551 .. code:: ipython2
 552
 553     define('PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop')
 554
 555 .. code:: ipython2
 556
 557     J('PE1')
 558
 559
 560 .. parsed-literal::
 561
 562     233168
 563
 564
 565 Here's our joy program all in one place. It doesn't make so much sense,
 566 but if you have read through the above description of how it was derived
 567 I hope it's clear.
 568
 569 ::
 570
 571     PE1.1 == + [+] dupdip
 572     PE1.2 == [3 & PE1.1] dupdip 2 >>
 573     PE1.3 == 14811 swap [PE1.2] times pop
 574     PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop
 575
 576 Generator Version
 577 =================
 578
 579 It's a little clunky iterating sixty-six times though the seven numbers
 580 then four more. In the *Generator Programs* notebook we derive a
 581 generator that can be repeatedly driven by the ``x`` combinator to
 582 produce a stream of the seven numbers repeating over and over again.
 583
 584 .. code:: ipython2
 585
 586     define('PE1.terms == [0 swap [dup [pop 14811] [] branch [3 &] dupdip 2 >>] dip rest cons]')
 587
 588 .. code:: ipython2
 589
 590     J('PE1.terms 21 [x] times')
 591
 592
 593 .. parsed-literal::
 594
 595     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]
 596
 597
 598 We know from above that we need sixty-six times seven then four more
 599 terms to reach up to but not over one thousand.
 600
 601 .. code:: ipython2
 602
 603     J('7 66 * 4 +')
 604
 605
 606 .. parsed-literal::
 607
 608     466
 609
 610
 611 Here they are...
 612 ~~~~~~~~~~~~~~~~
 613
 614 .. code:: ipython2
 615
 616     J('PE1.terms 466 [x] times pop')
 617
 618
 619 .. parsed-literal::
 620
 621     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
 622
 623
 624 ...and they do sum to 999.
 625 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 626
 627 .. code:: ipython2
 628
 629     J('[PE1.terms 466 [x] times pop] run sum')
 630
 631
 632 .. parsed-literal::
 633
 634     999
 635
 636
 637 Now we can use ``PE1.1`` to accumulate the terms as we go, and then
 638 ``pop`` the generator and the counter from the stack when we're done,
 639 leaving just the sum.
 640
 641 .. code:: ipython2
 642
 643     J('0 0 PE1.terms 466 [x [PE1.1] dip] times popop')
 644
 645
 646 .. parsed-literal::
 647
 648     233168
 649
 650
 651 A little further analysis renders iteration unnecessary.
 652 ========================================================
 653
 654 Consider finding the sum of the positive integers less than or equal to
 655 ten.
 656
 657 .. code:: ipython2
 658
 659     J('[10 9 8 7 6 5 4 3 2 1] sum')
 660
 661
 662 .. parsed-literal::
 663
 664     55
 665
 666
 667 Instead of summing them,
 668 `observe <https://en.wikipedia.org/wiki/File:Animated_proof_for_the_formula_giving_the_sum_of_the_first_integers_1%2B2%2B...%2Bn.gif>`__:
 669
 670 ::
 671
 672       10  9  8  7  6
 673     +  1  2  3  4  5
 674     ---- -- -- -- --
 675       11 11 11 11 11
 676
 677       11 * 5 = 55
 678
 679 From the above example we can deduce that the sum of the first N
 680 positive integers is:
 681
 682 ::
 683
 684     (N + 1) * N / 2
 685
 686 (The formula also works for odd values of N, I'll leave that to you if
 687 you want to work it out or you can take my word for it.)
 688
 689 .. code:: ipython2
 690
 691     define('F == dup ++ * 2 floordiv')
 692
 693 .. code:: ipython2
 694
 695     V('10 F')
 696
 697
 698 .. parsed-literal::
 699
 700           . 10 F
 701        10 . F
 702        10 . dup ++ * 2 floordiv
 703     10 10 . ++ * 2 floordiv
 704     10 11 . * 2 floordiv
 705       110 . 2 floordiv
 706     110 2 . floordiv
 707        55 .
 708
 709
 710 Generalizing to Blocks of Terms
 711 -------------------------------
 712
 713 We can apply the same reasoning to the PE1 problem.
 714
 715 Between 0 and 990 inclusive there are sixty-six "blocks" of seven terms
 716 each, starting with:
 717
 718 ::
 719
 720     [3 5 6 9 10 12 15]
 721
 722 And ending with:
 723
 724 ::
 725
 726     [978 980 981 984 985 987 990]
 727
 728 If we reverse one of these two blocks and sum pairs...
 729
 730 .. code:: ipython2
 731
 732     J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip')
 733
 734
 735 .. parsed-literal::
 736
 737     [[978 15] [980 12] [981 10] [984 9] [985 6] [987 5] [990 3]]
 738
 739
 740 .. code:: ipython2
 741
 742     J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map')
 743
 744
 745 .. parsed-literal::
 746
 747     [993 992 991 993 991 992 993]
 748
 749
 750 (Interesting that the sequence of seven numbers appears again in the
 751 rightmost digit of each term.)
 752
 753 .. code:: ipython2
 754
 755     J('[ 3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map sum')
 756
 757
 758 .. parsed-literal::
 759
 760     6945
 761
 762
 763 Since there are sixty-six blocks and we are pairing them up, there must
 764 be thirty-three pairs, each of which sums to 6945. We also have these
 765 additional unpaired terms between 990 and 1000:
 766
 767 ::
 768
 769     993 995 996 999
 770
 771 So we can give the "sum of all the multiples of 3 or 5 below 1000" like
 772 so:
 773
 774 .. code:: ipython2
 775
 776     J('6945 33 * [993 995 996 999] cons sum')
 777
 778
 779 .. parsed-literal::
 780
 781     233168
 782
 783
 784 It's worth noting, I think, that this same reasoning holds for any two
 785 numbers :math:`n` and :math:`m` the multiples of which we hope to sum.
 786 The multiples would have a cycle of differences of length :math:`k` and
 787 so we could compute the sum of :math:`Nk` multiples as above.
 788
 789 The sequence of differences will always be a palidrome. Consider an
 790 interval spanning the least common multiple of :math:`n` and :math:`m`:
 791
 792 ::
 793
 794     |   |   |   |   |   |   |   |
 795     |      |      |      |      |
 796
 797 Here we have 4 and 7, and you can read off the sequence of differences
 798 directly from the diagram: 4 3 1 4 2 2 4 1 3 4.
 799
 800 Geometrically, the actual values of :math:`n` and :math:`m` and their
 801 *lcm* don't matter, the pattern they make will always be symmetrical
 802 around its midpoint. The same reasoning holds for multiples of more than
 803 two numbers.
 804
 805 The Simplest Program
 806 ====================
 807
 808 Of course, the simplest joy program for the first Project Euler problem
 809 is just:
 810
 811 ::
 812
 813     PE1 == 233168
 814
 815 Fin.