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