# May 4, 2007

## 5min. fun with Euler

Project Euler is a site dedicated to Mathematics and Programming. For fun, I just registered and looked at the 152 problems (one more seems to be coming in 14 hours as announced by them) using fast forward. The problems seem very interesting. I’ve opened DrScheme and the easiest problem of all.

Easily I got the answer with:

(let loop ([n 1] [acc 0]) (cond [(>= n 1000) acc] [(or (zero? (remainder n 3)) (zero? (remainder n 5))) (loop (+ n 1) (+ acc n))] [else (loop (+ n 1) acc)])))

But then I thought… what about a one liner? Also easy.

(require (lib "compat.ss") (lib "etc.ss") (lib "list.ss")) (apply + (filter (λ (n) (or (zero? (remainder n 3)) (zero? (remainder n 5)))) (build-list 999 1+)))

Ahgr, I want to go further so I just decided to generalize it to receive any number of possible divisors and any maximum value.

(require (prefix srfi1: (lib "1.ss" "srfi"))) (define (divisors-sum max . divisors) (let loop ([n 1] [acc 0]) (cond [(>= n max) acc] [(srfi1:any (λ (div) (zero? (remainder n div))) divisors) (loop (+ n 1) (+ acc n))] [else (loop (+ n 1) acc)])))

So I decided to experiment with some numbers:

> (time (divisors-sum 100 3 5)) cpu time: 0 real time: 0 gc time: 0 2318 > (time (divisors-sum 1000 3 5)) ;; our case cpu time: 4 real time: 10 gc time: 0 233168 > (time (divisors-sum 10000 3 5)) cpu time: 24 real time: 23 gc time: 0 23331668 > (time (divisors-sum 100000 3 5)) cpu time: 224 real time: 231 gc time: 0 2333316668 > (time (divisors-sum 1000000 3 5)) cpu time: 1544 real time: 1600 gc time: 40 233333166668 > (time (divisors-sum 10000000 3 5)) cpu time: 12753 real time: 13296 gc time: 320 23333331666668

Well, what do you make up of the result? I’m quite astonished. I have not yet tried to prove it but it seems that for some reason the sum of all the numbers divisible by 3 or 5 below 10^n, for (n >= 2) is a number whose value is composed by the digits: 2 3^(n-1) 1 6^(n-2) 8 where in this case k^(n) means n repetitions of k.

The following function computes this number:

(define (divisors-sum-3-5-for-10 exp) (+ 8 (sum 1 (- exp 2) (λ (i) (* 6 (expt 10 i)))) (expt 10 (- exp 1)) (sum exp (- (* 2 exp) 2) (λ (i) (* 3 (expt 10 i)))) (* 2 (expt 10 (- (* 2 exp) 1)))))

where sum is a trivial function which may be defined as:

(define (sum init end proc) (let loop ([i init] [acc 0]) (if (> i end) acc (loop (+ i 1) (+ (proc i) acc)))))

So I conjecture that:

(= (divisors-sum-3-5-for-10 i) (divisors-sum (expt 10 i) 3 5)), for i >= 2

This is what fun is all about! :-)

Mike McNally said,

May 4, 2007 at 10:35 pm

The sum of numbers divisible by 3 less than N is 3 times the sum of the numbers 1 through N/3. That’s given by the formula (N/3)*(N/3+1)/2. Similarly for 5. Add those two together, and subtract out the similarly-computed number for 15, and you’re done – no iteration necessary.

diegoeche said,

May 5, 2007 at 2:24 am

Yep… I was thinking the same thing. You can use just a calculator to solve that

zahira said,

May 5, 2007 at 1:31 pm

i used to hate Euler’s method when i was in college… but when i read ur blog and i reckon,Euler is not that bad rite!!

Top Posts « WordPress.com said,

May 5, 2007 at 11:58 pm

[…] 5min. fun with Euler Project Euler is a site dedicated to Mathematics and Programming. For fun, I just registered and looked at the 152 […] […]

Robyn Moorcroft said,

May 19, 2007 at 4:22 pm

i love you all