### Project Euler, Problem 1 (PLT Scheme)

Nov. 21st, 2010 12:54 am**roddy**

*This is the first in a series of posts about attempting Project Euler in PLT Scheme. The posting schedule is, for the most part, every Friday. For more information, see the introductory post.*

The first problem on Project Euler is relatively simple:

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.— Project Euler

Find the sum of all the multiples of 3 or 5 below 1000.

First things first, I figure I need a function to determine if one number is a multiple of another number. Since I can't recall there being any such function built into PLT Scheme, and the manual page about numbers has nothing like it, I decide to write my own:

`(define (multiple-of? first second) (if (= 0 (modulo first second)) #T #F))`

My uninspired variable names notwithstanding, the function returns true of first%second=0, false otherwise.

Unfortunately we need to test if a number is multiple of 3

*or*5. So we could either call

*multiple-of?*twice for each, or be lazy and write a function do test against multiple multiples. (Pun fully intended.)

I'm lazy. I wrote the function.

`(define multiple-of-many? `

(lambda (test bases)

(cond

((number? bases) (multiple-of? test bases))

((or (not (list? bases)) (empty? bases) (list? (member #f (map (lambda (x) (number? x)) bases)))) #F)

((list? (member #t (map (lambda (x) (multiple-of? test x)) bases))) #T)

(else #F))))

Being primarily a Java coder, there has been many a time when I have prayed to the Java gods for a map function. Note the gratuitous use of said function in the previous example.

The first condition checks to see if we've actually passed in a list of multiple bases or just one. If it's just one, it simply calls multiple-of? and gets on with it.

The second condition validates that -- (in order) yes, the list of multiple bases is actually a list, the list is not empty, and every element in the list is a number.

The third condition actually tests the premise and tests the number against the multiple base list. This is done through a map function that calls multiple-of? against every element in the list.

And the else case is the this-is-a-multiple case. Returns automatic fail.

That's it for the helper functions. Now we need something that will iterate through the numbers 1 to 1000 and add the multiples of 3 and 5. I came up with the following:

`(define sum_all `

(lambda (current start finish bases)

(cond

( (>= start finish) current)

( (<= start 0) (sum_all 0 1 finish bases))

( (multiple-of-many? start bases) (sum_all (+ current start) (add1 start) finish bases))

( else (sum_all current (add1 start) finish bases)))))

The function takes four parameters: current, start, finish, base. "Current" holds the current sum. "Start" doesn't actually hold the first of the range, though it does initially; it actually holds the current number we're considering -- that is, if start is a multiple of 3 or 5, it is what is added to current. "End" is the target endpoint, in our case 1000. Finally, "bases" is a list of the bases we care about.

Truthfully if I hard-coded in the values of 1000 for "end" and '(3 5) for bases, we could make do with only two parameters for the function, but I tend to make my functions reusable. Who knows when I might someday need to sum the multiples of, say, 7 and 11 from 9 to 9000?

The first condition is the end-condition: if

*start*=

*end*, we've reached the end of our summation process and

*current*now holds the final sum.

The second condition is an error-checking condition: if

*start*is less than or equal to zero, re-call the sum_all function with

*start*=1 instead.

The third condition actually checks if

*start*is a multiple-of? the

*bases*. If it is, it re-calls the sum_all function with

*current=current+start*,

*start++*,

*end*, and

*bases*(with

*end*and

*bases*remaining the same).

The else condition occurs if

*start*is not a multiple-of? the

*bases*. In this case, it calls the sum_all function again and passes in

*start++*.

Finally, to run, we call:

`(sum_all 0 0 1000 '(3 5))`

The answer is

**233168**.

## Code

The code, in its entirety:

`(define (multiple-of? first second) (if (= 0 (modulo first second)) #T #F))`

(define multiple-of-many?

(lambda (test bases)

(cond

((number? bases) (multiple-of? test bases))

((or (empty? bases) (not (list? bases)) (list? (member #f (map (lambda (x) (number? x)) bases)))) #F)

((list? (member #t (map (lambda (x) (multiple-of? test x)) bases))) #T)

(else #F))))

(define sum_all

(lambda (current start finish bases)

(cond

( (>= start finish) current)

( (<= start 0) (sum_all 0 1 finish bases))

( (multiple-of-many? start bases) (sum_all (+ current start) (add1 start) finish bases))

( else (sum_all current (add1 start) finish bases)))))

**Short Form**

Alternatively, it is possible to do everything in a single function. As I mentioned before, I am primarily a Java programmer, so I like functions. But if you wanted to you could just do as follows:

`(define sum_all_short_form `

(lambda (current start finish bases)

(cond

( (or (>= start finish) (not? (list? bases)) (empty? bases) (list? (member #f (map (lambda (x) (number? x)) bases)))) current)

( (<= start 0) (sum_all 0 1 finish bases))

( (list? (member #t (map (lambda (x) (if (= 0 (modulo start x)) #T #F)) bases))) (sum_all (+ current start) (add1 start) finish bases))

( else (sum_all current (add1 start) finish bases)))))

**Short form, no error checking**

Note once more that the majority of the code is error checking. If we were to remove that, it would be even shorter:

`(define sum_all_short_form `

(lambda (current start finish bases)

(if

(list? (member #t (map (lambda (x) (if (= 0 (modulo start x)) #T #F)) bases))) (sum_all (+ current start) (add1 start) finish bases)

(sum_all current (add1 start) finish bases))))