# multiple fives

Write a predicate that determines of the input integer is a multiple of five.

``` \$ cat mof.rkt
#lang racket

(define (multiple-of-5? i)

; Return true iff the given integer is a multiple of 5.

(define (powers-of-5 n)

; Return a descending list of positive powers of 5 no greater than the
; given positive integer.

; This loop iterates O(log n) times (once for each digit in n) and does a
; constant amount of work in each iteration.

(let loop ((po5 1) (po5s '()))
(let ((next-po5 (* 5 po5)))
(if (> next-po5 n)
po5s
(loop next-po5 (cons next-po5 po5s))))))

(define (remainder-mod-5 n)

; Return the remainder of dividing the given positive integer by 5.

(let ((po5s (powers-of-5 n)))
(if (null? po5s)

; The "outer loop" does O(log n) work (the length of the powers-of-5
; list).  The "inner loop" does O(1) work for each power of five.

(let loop ((n n) (po5 (car po5s)) (po5s (cdr po5s)))
(cond

((>= n po5)
(loop (- n po5) po5 po5s))

((null? po5s)
n)

(#t
(loop n (car po5s) (cdr po5s))))))))

(zero? (remainder-mod-5 (abs i))))

(define (another-multiple-of-5? i)

; Return true iff the given integer is a multiple of 5.

(define (remainder-mod-po5 n po5)

; Return the remainder of dividing the given positive integer by the given
; power of 5.

(let*

((next-po5 (* 5 po5))
(n (if (>= n next-po5) (remainder-mod-po5 n next-po5) n)))

(let loop ((n n))
(if (>= n po5)
(loop (- n po5))
n))))

(zero? (remainder-mod-po5 (abs i) 5)))

(require rackunit math/number-theory)

(define (test-it f)
(do ((i -1000 (+ 1 i))) ((> i 1000) #t)
(check-eq? (f i) (divides? 5 i))))

(test-it multiple-of-5?)
(test-it another-multiple-of-5?)

\$ racket mof.rkt
#t
#t

\$
```