1 `Project Euler, first problem: “Multiples of 3 and 5” <https://projecteuler.net/problem=1>`__
2 =============================================================================================
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.
8 Find the sum of all the multiples of 3 or 5 below 1000.
12 from notebook_preamble import J, V, define
14 Let’s create a predicate that returns ``True`` if a number is a multiple
15 of 3 or 5 and ``False`` otherwise.
19 define('P == [3 % not] dupdip 5 % not or')
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
43 Given the predicate function ``P`` a suitable program is:
47 PE1 == 1000 range [P] filter sum
49 This function generates a list of the integers from 0 to 999, filters
50 that list by ``P``, and then sums the result.
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.
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
65 This seemed a little clunky, so I tried a different approach.
67 Consider the first few terms in the series:
71 3 5 6 9 10 12 15 18 20 21 ...
73 Subtract each number from the one after it (subtracting 0 from 3):
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 ...
82 You get this lovely repeating palindromic sequence:
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.
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:
102 define('PE1.1 == + [+] dupdip')
125 V('0 0 [3 2 1 3 1 2 3] [PE1.1] step')
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
197 45 12 3 . + [+] dupdip
205 So one ``step`` through all seven terms brings the counter to 15 and the
247 We only want the terms *less than* 1000.
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.
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')
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.
290 0b 11 10 01 11 01 10 11 == 14811
307 define('PE1.2 == [3 & PE1.1] dupdip 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 >>
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 >>
365 V('0 0 14811 7 [PE1.2] times pop')
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
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
503 And so we have at last:
507 define('PE1 == 0 0 66 [14811 7 [PE1.2] times pop] times 14811 4 [PE1.2] times popop')
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
530 define('PE1.3 == 14811 swap [PE1.2] times pop')
532 Now we can simplify the definition above:
536 define('PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop')
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
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
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.
569 define('PE1.terms == [0 swap [dup [pop 14811] [] branch [3 &] dupdip 2 >>] dip rest cons]')
573 J('PE1.terms 21 [x] times')
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]
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.
599 J('PE1.terms 466 [x] times pop')
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
607 …and they do sum to 999.
608 ~~~~~~~~~~~~~~~~~~~~~~~~
612 J('[PE1.terms 466 [x] times pop] run sum')
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.
626 J('0 0 PE1.terms 466 [x [PE1.1] dip] times popop')
634 A little further analysis renders iteration unnecessary.
635 ========================================================
637 Consider finding the sum of the positive integers less than or equal to
642 J('[10 9 8 7 6 5 4 3 2 1] sum')
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>`__:
662 From the above example we can deduce that the sum of the first N
663 positive integers is:
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.)
674 define('F == dup ++ * 2 floordiv')
685 10 . dup ++ * 2 floordiv
686 10 10 . ++ * 2 floordiv
693 Generalizing to Blocks of Terms
694 -------------------------------
696 We can apply the same reasoning to the PE1 problem.
698 Between 0 and 990 inclusive there are sixty-six “blocks” of seven terms
709 [978 980 981 984 985 987 990]
711 If we reverse one of these two blocks and sum pairs…
715 J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip')
720 [[978 15] [980 12] [981 10] [984 9] [985 6] [987 5] [990 3]]
725 J('[3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map')
730 [993 992 991 993 991 992 993]
733 (Interesting that the sequence of seven numbers appears again in the
734 rightmost digit of each term.)
738 J('[ 3 5 6 9 10 12 15] reverse [978 980 981 984 985 987 990] zip [sum] map sum')
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:
754 So we can give the “sum of all the multiples of 3 or 5 below 1000” like
759 J('6945 33 * [993 995 996 999] cons sum')
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.
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`:
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.
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
791 Of course, the simplest joy program for the first Project Euler problem