Vedic Divisibility
July 8, 2011
We extract into separate functions the calculation of the last digit and the number remaining after stripping the last digit:
(define (last x) (car (reverse (digits x))))
(define (but-last x)
(undigits (reverse (cdr (reverse (digits x))))))
For the calculation of the osculator we need to figure out the smallest multiple of the divisor that ends with 9. That’s easy. Since the divisor must be odd and not divisible by 5, it must end in 1, 3, 7 or 9. If it ends in 1, multiply by 9. If it ends in 3, multiply by 3. If it ends in 7, multiply by 7. And if it ends in 9, do nothing. Then the calculation of the osculator is simple:
(define (osculator n)
(define (f x) (+ (but-last (* n x)) 1))
(let ((ds (digits n)))
(case (car (reverse ds))
((1) (f 9))
((3) (f 3))
((7) (f 7))
((9) (f 1))
(else (error 'osculator "unsupported")))))
The divisibility test is recursive, reducing the size of the dividend n at each step:
(define (divisible? n d)
(let ((osc (osculator d)))
(let loop ((n n))
(let ((next (+ (but-last n) (* last n) osc))))
(if (< next n) (loop next) (zero? (modulo n d)))))))
Here are some examples:
> (divisible? 13174584 23)
#t
> (divisible? 175121 37)
#t
> (divisible? 134567 29)
#f
We used digits
and undigits
from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/qZrg7y54.
Solution in Python:
Python:
And since Remco hasn’t jumped on it yet, here’s my attempt in Haskell:
Just to be different, how about an F# version.
Line 07 above should be: