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:: ipython3
  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:: ipython3
  18
  19     define('P [3 % not] dupdip 5 % not or')
  20
  21 .. code:: ipython3
  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:: ipython3
 101
 102     define('PE1.1 + [+] dupdip')
 103
 104 .. code:: ipython3
 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:: ipython3
 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:: ipython3
 209
 210     1000 / 15
 211
 212
 213
 214
 215 .. parsed-literal::
 216
 217     66.66666666666667
 218
 219
 220
 221 .. code:: ipython3
 222
 223     66 * 15
 224
 225
 226
 227
 228 .. parsed-literal::
 229
 230     990
 231
 232
 233
 234 .. code:: ipython3
 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:: ipython3
 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:: ipython3
 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:: ipython3
 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:: ipython3
 293
 294     0b11100111011011
 295
 296
 297
 298
 299 .. parsed-literal::
 300
 301     14811
 302
 303
 304
 305 .. code:: ipython3
 306
 307     define('PE1.2 [3 & PE1.1] dupdip 2 >>')
 308
 309 .. code:: ipython3
 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:: ipython3
 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:: ipython3
 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 6 [PE1.2] times pop
 377                 0 0 14811 • [3 & PE1.1] dupdip 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 14811 2 >> 6 [PE1.2] times pop
 380               0 0 14811 3 • & PE1.1 14811 2 >> 6 [PE1.2] times pop
 381                     0 0 3 • PE1.1 14811 2 >> 6 [PE1.2] times pop
 382                     0 0 3 • + [+] dupdip 14811 2 >> 6 [PE1.2] times pop
 383                       0 3 • [+] dupdip 14811 2 >> 6 [PE1.2] times pop
 384                   0 3 [+] • dupdip 14811 2 >> 6 [PE1.2] times pop
 385                       0 3 • + 3 14811 2 >> 6 [PE1.2] times pop
 386                         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 3702 • 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 • PE1.2 5 [PE1.2] times pop
 394                  3 3 3702 • [3 & PE1.1] dupdip 2 >> 5 [PE1.2] times pop
 395      3 3 3702 [3 & PE1.1] • dupdip 2 >> 5 [PE1.2] times pop
 396                  3 3 3702 • 3 & PE1.1 3702 2 >> 5 [PE1.2] times pop
 397                3 3 3702 3 • & PE1.1 3702 2 >> 5 [PE1.2] times pop
 398                     3 3 2 • PE1.1 3702 2 >> 5 [PE1.2] times pop
 399                     3 3 2 • + [+] dupdip 3702 2 >> 5 [PE1.2] times pop
 400                       3 5 • [+] dupdip 3702 2 >> 5 [PE1.2] times pop
 401                   3 5 [+] • dupdip 3702 2 >> 5 [PE1.2] times pop
 402                       3 5 • + 5 3702 2 >> 5 [PE1.2] times pop
 403                         8 • 5 3702 2 >> 5 [PE1.2] times pop
 404                       8 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 925 • 5 [PE1.2] times pop
 408                 8 5 925 5 • [PE1.2] times pop
 409         8 5 925 5 [PE1.2] • times pop
 410                   8 5 925 • PE1.2 4 [PE1.2] times pop
 411                   8 5 925 • [3 & PE1.1] dupdip 2 >> 4 [PE1.2] times pop
 412       8 5 925 [3 & PE1.1] • dupdip 2 >> 4 [PE1.2] times pop
 413                   8 5 925 • 3 & PE1.1 925 2 >> 4 [PE1.2] times pop
 414                 8 5 925 3 • & PE1.1 925 2 >> 4 [PE1.2] times pop
 415                     8 5 1 • PE1.1 925 2 >> 4 [PE1.2] times pop
 416                     8 5 1 • + [+] dupdip 925 2 >> 4 [PE1.2] times pop
 417                       8 6 • [+] dupdip 925 2 >> 4 [PE1.2] times pop
 418                   8 6 [+] • dupdip 925 2 >> 4 [PE1.2] times pop
 419                       8 6 • + 6 925 2 >> 4 [PE1.2] times pop
 420                        14 • 6 925 2 >> 4 [PE1.2] times pop
 421                      14 6 • 925 2 >> 4 [PE1.2] times pop
 422                  14 6 925 • 2 >> 4 [PE1.2] times pop
 423                14 6 925 2 • >> 4 [PE1.2] times pop
 424                  14 6 231 • 4 [PE1.2] times pop
 425                14 6 231 4 • [PE1.2] times pop
 426        14 6 231 4 [PE1.2] • times pop
 427                  14 6 231 • PE1.2 3 [PE1.2] times pop
 428                  14 6 231 • [3 & PE1.1] dupdip 2 >> 3 [PE1.2] times pop
 429      14 6 231 [3 & PE1.1] • dupdip 2 >> 3 [PE1.2] times pop
 430                  14 6 231 • 3 & PE1.1 231 2 >> 3 [PE1.2] times pop
 431                14 6 231 3 • & PE1.1 231 2 >> 3 [PE1.2] times pop
 432                    14 6 3 • PE1.1 231 2 >> 3 [PE1.2] times pop
 433                    14 6 3 • + [+] dupdip 231 2 >> 3 [PE1.2] times pop
 434                      14 9 • [+] dupdip 231 2 >> 3 [PE1.2] times pop
 435                  14 9 [+] • dupdip 231 2 >> 3 [PE1.2] times pop
 436                      14 9 • + 9 231 2 >> 3 [PE1.2] times pop
 437                        23 • 9 231 2 >> 3 [PE1.2] times pop
 438                      23 9 • 231 2 >> 3 [PE1.2] times pop
 439                  23 9 231 • 2 >> 3 [PE1.2] times pop
 440                23 9 231 2 • >> 3 [PE1.2] times pop
 441                   23 9 57 • 3 [PE1.2] times pop
 442                 23 9 57 3 • [PE1.2] times pop
 443         23 9 57 3 [PE1.2] • times pop
 444                   23 9 57 • PE1.2 2 [PE1.2] times pop
 445                   23 9 57 • [3 & PE1.1] dupdip 2 >> 2 [PE1.2] times pop
 446       23 9 57 [3 & PE1.1] • dupdip 2 >> 2 [PE1.2] times pop
 447                   23 9 57 • 3 & PE1.1 57 2 >> 2 [PE1.2] times pop
 448                 23 9 57 3 • & PE1.1 57 2 >> 2 [PE1.2] times pop
 449                    23 9 1 • PE1.1 57 2 >> 2 [PE1.2] times pop
 450                    23 9 1 • + [+] dupdip 57 2 >> 2 [PE1.2] times pop
 451                     23 10 • [+] dupdip 57 2 >> 2 [PE1.2] times pop
 452                 23 10 [+] • dupdip 57 2 >> 2 [PE1.2] times pop
 453                     23 10 • + 10 57 2 >> 2 [PE1.2] times pop
 454                        33 • 10 57 2 >> 2 [PE1.2] times pop
 455                     33 10 • 57 2 >> 2 [PE1.2] times pop
 456                  33 10 57 • 2 >> 2 [PE1.2] times pop
 457                33 10 57 2 • >> 2 [PE1.2] times pop
 458                  33 10 14 • 2 [PE1.2] times pop
 459                33 10 14 2 • [PE1.2] times pop
 460        33 10 14 2 [PE1.2] • times pop
 461                  33 10 14 • PE1.2 1 [PE1.2] times pop
 462                  33 10 14 • [3 & PE1.1] dupdip 2 >> 1 [PE1.2] times pop
 463      33 10 14 [3 & PE1.1] • dupdip 2 >> 1 [PE1.2] times pop
 464                  33 10 14 • 3 & PE1.1 14 2 >> 1 [PE1.2] times pop
 465                33 10 14 3 • & PE1.1 14 2 >> 1 [PE1.2] times pop
 466                   33 10 2 • PE1.1 14 2 >> 1 [PE1.2] times pop
 467                   33 10 2 • + [+] dupdip 14 2 >> 1 [PE1.2] times pop
 468                     33 12 • [+] dupdip 14 2 >> 1 [PE1.2] times pop
 469                 33 12 [+] • dupdip 14 2 >> 1 [PE1.2] times pop
 470                     33 12 • + 12 14 2 >> 1 [PE1.2] times pop
 471                        45 • 12 14 2 >> 1 [PE1.2] times pop
 472                     45 12 • 14 2 >> 1 [PE1.2] times pop
 473                  45 12 14 • 2 >> 1 [PE1.2] times pop
 474                45 12 14 2 • >> 1 [PE1.2] times pop
 475                   45 12 3 • 1 [PE1.2] times pop
 476                 45 12 3 1 • [PE1.2] times pop
 477         45 12 3 1 [PE1.2] • times pop
 478                   45 12 3 • PE1.2 pop
 479                   45 12 3 • [3 & PE1.1] dupdip 2 >> pop
 480       45 12 3 [3 & PE1.1] • dupdip 2 >> pop
 481                   45 12 3 • 3 & PE1.1 3 2 >> pop
 482                 45 12 3 3 • & PE1.1 3 2 >> pop
 483                   45 12 3 • PE1.1 3 2 >> pop
 484                   45 12 3 • + [+] dupdip 3 2 >> pop
 485                     45 15 • [+] dupdip 3 2 >> pop
 486                 45 15 [+] • dupdip 3 2 >> pop
 487                     45 15 • + 15 3 2 >> pop
 488                        60 • 15 3 2 >> pop
 489                     60 15 • 3 2 >> pop
 490                   60 15 3 • 2 >> pop
 491                 60 15 3 2 • >> pop
 492                   60 15 0 • pop
 493                     60 15 •
 494
 495
 496 And so we have at last:
 497
 498 .. code:: ipython3
 499
 500     define('PE1 0 0 66 [14811 7 [PE1.2] times pop] times 14811 4 [PE1.2] times popop')
 501
 502 .. code:: ipython3
 503
 504     J('PE1')
 505
 506
 507 .. parsed-literal::
 508
 509     233168
 510
 511
 512 Let's refactor.
 513
 514 ::
 515
 516       14811 7 [PE1.2] times pop
 517       14811 4 [PE1.2] times pop
 518       14811 n [PE1.2] times pop
 519     n 14811 swap [PE1.2] times pop
 520
 521 .. code:: ipython3
 522
 523     define('PE1.3 14811 swap [PE1.2] times pop')
 524
 525 Now we can simplify the definition above:
 526
 527 .. code:: ipython3
 528
 529     define('PE1 0 0 66 [7 PE1.3] times 4 PE1.3 pop')
 530
 531 .. code:: ipython3
 532
 533     J('PE1')
 534
 535
 536 .. parsed-literal::
 537
 538     233168
 539
 540
 541 Here's our joy program all in one place. It doesn't make so much sense,
 542 but if you have read through the above description of how it was derived
 543 I hope it's clear.
 544
 545 ::
 546
 547     PE1.1 == + [+] dupdip
 548     PE1.2 == [3 & PE1.1] dupdip 2 >>
 549     PE1.3 == 14811 swap [PE1.2] times pop
 550     PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop
 551
 552 Generator Version
 553 =================
 554
 555 It's a little clunky iterating sixty-six times though the seven numbers
 556 then four more. In the *Generator Programs* notebook we derive a
 557 generator that can be repeatedly driven by the ``x`` combinator to
 558 produce a stream of the seven numbers repeating over and over again.
 559
 560 .. code:: ipython3
 561
 562     define('PE1.terms [0 swap [dup [pop 14811] [] branch [3 &] dupdip 2 >>] dip rest cons]')
 563
 564 .. code:: ipython3
 565
 566     J('PE1.terms 21 [x] times')
 567
 568
 569 .. parsed-literal::
 570
 571     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]
 572
 573
 574 We know from above that we need sixty-six times seven then four more
 575 terms to reach up to but not over one thousand.
 576
 577 .. code:: ipython3
 578
 579     J('7 66 * 4 +')
 580
 581
 582 .. parsed-literal::
 583
 584     466
 585
 586
 587 Here they are...
 588 ~~~~~~~~~~~~~~~~
 589
 590 .. code:: ipython3
 591
 592     J('PE1.terms 466 [x] times pop')
 593
 594
 595 .. parsed-literal::
 596
 597     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
 598
 599
 600 ...and they do sum to 999.
 601 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 602
 603 .. code:: ipython3
 604
 605     J('[PE1.terms 466 [x] times pop] run sum')
 606
 607
 608 .. parsed-literal::
 609
 610     999
 611
 612
 613 Now we can use ``PE1.1`` to accumulate the terms as we go, and then
 614 ``pop`` the generator and the counter from the stack when we're done,
 615 leaving just the sum.
 616
 617 .. code:: ipython3
 618
 619     J('0 0 PE1.terms 466 [x [PE1.1] dip] times popop')
 620
 621
 622 .. parsed-literal::
 623
 624     233168
 625
 626
 627 A little further analysis renders iteration unnecessary.
 628 ========================================================
 629
 630 Consider finding the sum of the positive integers less than or equal to
 631 ten.
 632
 633 .. code:: ipython3
 634
 635     J('[10 9 8 7 6 5 4 3 2 1] sum')
 636
 637
 638 .. parsed-literal::
 639
 640     55
 641
 642
 643 Instead of summing them,
 644 `observe <https://en.wikipedia.org/wiki/File:Animated_proof_for_the_formula_giving_the_sum_of_the_first_integers_1%2B2%2B...%2Bn.gif>`__:
 645
 646 ::
 647
 648       10  9  8  7  6
 649     +  1  2  3  4  5
 650     ---- -- -- -- --
 651       11 11 11 11 11
 652
 653       11 * 5 = 55
 654
 655 From the above example we can deduce that the sum of the first N
 656 positive integers is:
 657
 658 ::
 659
 660     (N + 1) * N / 2
 661
 662 (The formula also works for odd values of N, I'll leave that to you if
 663 you want to work it out or you can take my word for it.)
 664
 665 .. code:: ipython3
 666
 667     define('F dup ++ * 2 floordiv')
 668
 669 .. code:: ipython3
 670
 671     V('10 F')
 672
 673
 674 .. parsed-literal::
 675
 676           • 10 F
 677        10 • F
 678        10 • dup ++ * 2 floordiv
 679     10 10 • ++ * 2 floordiv
 680     10 11 • * 2 floordiv
 681       110 • 2 floordiv
 682     110 2 • floordiv
 683        55 •
 684
 685
 686 Generalizing to Blocks of Terms
 687 -------------------------------
 688
 689 We can apply the same reasoning to the PE1 problem.
 690
 691 Between 0 and 990 inclusive there are sixty-six "blocks" of seven terms
 692 each, starting with:
 693
 694 ::
 695
 696     [3 5 6 9 10 12 15]
 697
 698 And ending with:
 699
 700 ::
 701
 702     [978 980 981 984 985 987 990]
 703
 704 If we reverse one of these two blocks and sum pairs...
 705
 706 .. code:: ipython3
 707
 708     J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip')
 709
 710
 711 .. parsed-literal::
 712
 713     [[978 15] [980 12] [981 10] [984 9] [985 6] [987 5] [990 3]]
 714
 715
 716 .. code:: ipython3
 717
 718     J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map')
 719
 720
 721 .. parsed-literal::
 722
 723     [993 992 991 993 991 992 993]
 724
 725
 726 (Interesting that the sequence of seven numbers appears again in the
 727 rightmost digit of each term.)
 728
 729 .. code:: ipython3
 730
 731     J('[ 3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map sum')
 732
 733
 734 .. parsed-literal::
 735
 736     6945
 737
 738
 739 Since there are sixty-six blocks and we are pairing them up, there must
 740 be thirty-three pairs, each of which sums to 6945. We also have these
 741 additional unpaired terms between 990 and 1000:
 742
 743 ::
 744
 745     993 995 996 999
 746
 747 So we can give the "sum of all the multiples of 3 or 5 below 1000" like
 748 so:
 749
 750 .. code:: ipython3
 751
 752     J('6945 33 * [993 995 996 999] cons sum')
 753
 754
 755 .. parsed-literal::
 756
 757     233168
 758
 759
 760 It's worth noting, I think, that this same reasoning holds for any two
 761 numbers :math:`n` and :math:`m` the multiples of which we hope to sum.
 762 The multiples would have a cycle of differences of length :math:`k` and
 763 so we could compute the sum of :math:`Nk` multiples as above.
 764
 765 The sequence of differences will always be a palidrome. Consider an
 766 interval spanning the least common multiple of :math:`n` and :math:`m`:
 767
 768 ::
 769
 770     |   |   |   |   |   |   |   |
 771     |      |      |      |      |
 772
 773 Here we have 4 and 7, and you can read off the sequence of differences
 774 directly from the diagram: 4 3 1 4 2 2 4 1 3 4.
 775
 776 Geometrically, the actual values of :math:`n` and :math:`m` and their
 777 *lcm* don't matter, the pattern they make will always be symmetrical
 778 around its midpoint. The same reasoning holds for multiples of more than
 779 two numbers.
 780
 781 The Simplest Program
 782 ====================
 783
 784 Of course, the simplest joy program for the first Project Euler problem
 785 is just:
 786
 787 ::
 788
 789     PE1 == 233168
 790
 791 Fin.