docs/3._Developing_a_Program.rst

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