May 4, 2007

5min. fun with Euler

Posted in Programming, Scheme at 7:17 pm by pmatos

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! :-)

5 Comments »

  1. Mike McNally said,

    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.

  2. diegoeche said,

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

  3. zahira said,

    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!!

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

  5. Robyn Moorcroft said,

    i love you all


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: