Project Euler 1 (sum of multiples of 3 or 5 under 1000)

Question

I solved this a while ago. In the moment I solved it I was learning Scheme and, well, I still am. I'm not looking at the best solution (I searched for it and coded it already, in Python), what I want is to improve this code, maintaining the same (brute) approach, so I can learn some best practices and tips in Scheme. Maybe there are some suggestions on how I wrote the routines, for example.

#lang racket
(define (check x) (or (= (modulo x 3) 0)
 (= (modulo x 5) 0)))
(define (count-check x) (if (check x)
 x
 0))
(define (sum-multiples-rec actual limit acc) (if (< actual limit)
 (sum-multiples-rec (+ actual 1) limit (+ (count-check actual) acc))
 acc))
(define (sum-multiples lower-limit upper-limit) (sum-multiples-rec lower-limit upper-limit 0))
(sum-multiples 0 1000)

• Jerry Coffin: Not sure how it happened, but it doesn't look like the code is valid right now. I believe you intended something more like: (define (sum-multiples lower-limit upper-limit) (sum-multiples-rec lower-limit upper-limit 0)).
• ArthurChamz: Yeah, that's... correct. Man, what a good starting point! =)

Answer 1

So, any time you want to write a "helper" recursive function, the standard way to write that is to use a named let. So here's how I might restructure your program (but keeping the same algorithm):

(define (sum-multiples start end)
 (let loop ((sum 0)
 (i start))
 (cond ((>= i end) sum)
 ((or (zero? (modulo i 3))
 (zero? (modulo i 5)))
 (loop (+ sum i) (add1 i)))
 (else (loop sum (add1 i))))))

Named let is a macro, which in this case expands to the same expression as:

(define (sum-multiples start end)
 ((letrec ((loop (lambda (sum i)
 (cond ((>= i end) sum)
 ((or (zero? (modulo i 3))
 (zero? (modulo i 5)))
 (loop (+ sum i) (add1 i)))
 (else (loop sum (add1 i)))))))
 loop)
 0 start))

(I've taken the liberty of using (add1 i) instead of (+ i 1) since you're using Racket.)

---

Here's a version that's even more Rackety, using for/sum to accumulate the sum rather than using a manual loop:

(define (sum-multiples start end)
 (for/sum ((i (range start end)))
 (if (or (zero? (modulo i 3))
 (zero? (modulo i 5)))
 i 0)))

• ArthurChamz: Thanks for the help, the first code is very interesting. I see in the documentation that a named let works as some sort of lambda. I still need to read a little more, though, it's rather confusing for me.
• C. K. Young: @ArthurChamz Yes, it is a kind of lambda. Let me update the post to detail how it would be expanded.
• ArthurChamz: Thanks, I still have some things to learn about Scheme, but this is an awesome start!

Answer 2

Better programming practice would be to decompose the problem in such a way that the procedures adhere to the Single Responsibility Principle. In other words, the answer should be obtained by evaluating something like

(sum (filter (multiple-of-any? 3 5) (range 0 1000)))

... which reads just like the problem to be solved.

Here's a set of functions that could achieve that. Note that, unlike the functions you've defined (check, count-check, sum-multiples-rec, sum-multiples), which are highly specific to solving Project Euler Problem 1, these functions are flexible and could likely be reused to solve other problems.

(define (sum list)
 (if (eq? list '())
 0
 (+ (car list) (sum (cdr list)))))
(define (range min max)
 (if (= min max) 
 '()
 (cons min (range (+ min 1) max))))
(define (filter pred? list)
 (cond ((eq? list '()) list)
 ((pred? (car list)) (cons (car list) (filter pred? (cdr list))))
 (else (filter pred? (cdr list)))))
(define (multiple-of-any? . divisors)
 (lambda (n) (cond ((eq? divisors '()) #f)
 ((= 0 (modulo n (car divisors))) #t)
 (else ((apply multiple-of-any? (cdr divisors)) n)))))

• C. K. Young: In the name of library reuse, I recommend using SRFI 1 for range (called iota in SRFI 1) and filter. sum is easily defined using (apply + lst) or (reduce + 0 lst) (reduce is in SRFI 1). This way, you can get rid of all the manual loops.
• C. K. Young: And of course, instead of the manual loop in multiple-of-any?, simply use SRFI 1's any. Also, since this is a Racket question, you can load SRFI 1 using (require srfi/1).
• ArthurChamz: Mmm, it is much more flexible than my approach. What does '() mean, which I see many times in the code? There are some things I don't get about the code, but this is used many times...
• C. K. Young: @ArthurChamz '() is an expression that returns the literal datum for an empty list, in the same way that '(foo) is an expression that returns the literal datum for a list that contains the symbol foo as its sole element. There are other expressions that also return an empty list, such as (list), but '() is the most common way to write it in Scheme.
• C. K. Young: @200_success Sure it works: (define (multiple-of-any? . divisors) (lambda (n) (any (lambda (i) (zero? (modulo n i))) divisors)))

Answer 3

As noted in the comment, your code currently looks like it has a (admittedly fairly minor) problem. In sum-multiples, you try to pass actual and limit as parameters to sum-multiples-rec, but those names aren't bound to anything at that point. You need/want something more like:

(define (sum-multiples lower-limit upper-limit) 
 (sum-multiples-rec lower-limit upper-limit 0))

As far as style goes, the main thing I'd change would be to write your ancillary functions inside of sum-multiples. Right now, sum-multiples-rec, count-check and check are all "publicly" visible, but they're unlikely to be of any use except to count-multiples. As such, they should really be "hidden" inside it.

As such, your code could end up something like this:

(define (sum-multiples lower-limit upper-limit) 
 (define (sum-multiples-rec actual limit acc)
 (define (count-check x) 
 (define (check x) (or (= (modulo x 3) 0)
 (= (modulo x 5) 0)))
 (if (check x) 
 x 
 0))
 (if (< actual limit)
 (sum-multiples-rec (+ actual 1) limit (+ (count-check actual) acc))
 acc)) 
 (sum-multiples-rec lower-limit upper-limit 0))

[Indentation probably open to improvement]

So, check is only defined/visible inside of count-check. count-check (in turn) is only defined/visible inside of sum-multiples-rec, and sum-multiples-rec is only defined/visible inside of sum-multiples. If (for example) you try to execute something like (check 3) outside of sum-multiples, you'll get an error like:

check: undefined; cannot reference an identifier before its definition

This is pretty much the same general idea as (for example) a class in something like Java or C++ making as many if its members private as possible. Limiting the visibility of names dramatically reduces the chances of a name collision that could result in your calling entirely the wrong function. This is particularly important with names like check that could mean all sorts of different things under different circumstances.

Of course, much like with those other languages, this sort of discipline becomes much more important for larger programs. For a really tiny program, it's not all that big of a deal.

• ArthurChamz: Again, thanks for pointing out the mistake. I didn't know how to "encapsulate" functions in Scheme, thank you very much!

Answer 4

The approach you have taken is to check each number between 0 and 1000 to see if it is a multiple of either 3 or 5, and if so, add it to the accumulator.

A more straightforward solution is to use the Inclusion-Exclusion Principle. Add the multiples of 3 and the multiples of 5. Since the multiples of 15 are double-counted, subtract the multiples of 15.

(define (sum list)
 (if (eq? list '())
 0
 (+ (car list) (sum (cdr list)))))
(define (multiples min max step)
 (if (>= min max)
 '()
 (cons min (multiples (+ min step) max step))))
(- (+ (sum (multiples 0 1000 3))
 (sum (multiples 0 1000 5)))
 (sum (multiples 0 1000 15)))

• C. K. Young: Here, of course, multiples can be replaced by SRFI 1's iota too. :-)