## Lunar Arithmetic

### January 22, 2019

We represent lunar number as lists of digits, least significant digit first. Here are conversions to and from lunar representation:

(define (terran->lunar n) (reverse (digits n))) (define (lunar->terran xs) (undigits (reverse xs)))

Addition is easy enough; it’s just `map max`

over the two lists. We need a specialized version of `map`

to substitute leading zeroes where one number is shorter than the other:

(define (plus xs ys) (define (map0 f xs ys) (let loop ((xs xs) (ys ys) (zs (list))) (cond ((and (null? xs) (null? ys)) (reverse zs)) ((null? xs) (loop xs (cdr ys) (cons (f 0 (car ys)) zs))) ((null? ys) (loop (cdr xs) ys (cons (f (car xs) 0) zs))) (else (loop (cdr xs) (cdr ys) (cons (f (car xs) (car ys)) zs)))))) (map0 max xs ys))

Multiplication is a little bit harder. It’s essentially `map min`

, but we have to then add the partial results, remembering to shift the implied zeroes:

(define (times xs ys) (define (times-one m xs) (map (lambda (x) (min m x)) xs)) (let loop ((ys ys) (0s (list)) (zs (list))) (if (null? ys) zs (loop (cdr ys) (cons 0 0s) (plus (times-one (car ys) (append 0s xs)) zs)))))

Note that `0s`

(that’s zero ess) is a valid symbol in Scheme; you may need to spell it zeroes in other languages. Here are our sample problems:

> (lunar->terran (plus (terran->lunar 357) (terran->lunar 64))) 367 > (lunar->terran (times (terran->lunar 357) (terran->lunar 64))) 3564

You can run the program at https://ideone.com/ExyYk0. Be sure to watch the video.

57s/0/1/ ; sorry.

In Python.

Here’s a solution in C.

Example Usage:

Here’s another Python solution, I nicked a few bits of Paul’s solution, including use of zip_longest, which I didn’t know about. The Lunar class internally uses the list of digits representation. It’s fun to implement the Sieve of Eratosthenes too:

A Haskell version.

And apparently, there are applications: https://twitter.com/numberphile/status/1348613413619040256