docs/3._Developing_a_Program.md

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