Lunar Arithmetic
January 22, 2019
Over at Numberphile, Neil Sloane (yes, that Neil Sloane), talks about lunar arithmetic, an “other-worldly” way of doing simple math:
Lunar addition and multiplication work digit by digit, the same as terrestrial addition and multiplication, except that the plus and times tables are unusual. Addition is done by taking the larger of the two digits, so 1 + 3 = 3 and 7 + 4 = 7. Multiplication is done by taking the smaller of the two digits, so 1 * 3 = 1 and 7 * 4 = 4. Thus:
3 5 7 3 5 7 + 6 4 * 6 4 ------- ------- 3 6 7 3 4 4 3 5 6 ------- 3 5 6 4There are no carries. There is no subtraction or division, since the results would not be unique.
Your task is to write programs that perform lunar addition and multiplication. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
(defpackage "LUNAR" (:use) (:export "+" "*")) (defpackage "LUNAR-ARITHMETIC" (:use "COMMON-LISP")) (in-package "LUNAR-ARITHMETIC") (deftype natural () `(integer 0)) (deftype digit () `(integer 0 9)) (defun make-decimal (length &optional (default-digit 0)) (make-array length :element-type 'digti :initial-element default-digit)) (defun decimal-from-integer (n) (check-type n natural) (loop :with result := (make-decimal (if (< n 2) 1 (ceiling (log n 10)))) :while (plusp n) :for i :from 0 :for (q d) := (multiple-value-list (truncate n 10)) :do (setf (aref result i) d n q) :finally (return result))) (defun decimal-to-integer (digits) (reduce (lambda (d n) (+ (* n 10) d)) digits :initial-value 0 :from-end t)) (defun lunar:+ (&rest arguments) (cond ((null arguments) 0) ((null (rest arguments)) (first arguments)) (t (let* ((arguments (mapcar (function decimal-from-integer) arguments)) (result (make-decimal (reduce (function max) arguments :key (function length))))) (replace result (pop arguments)) (dolist (argument arguments) (map-into result (function max) result argument)) (decimal-to-integer result))))) (defun binary* (a b) (let ((result (make-decimal (1- (+ (length a) (length b)))))) (loop :for bd :across b :for start :from 0 :do (loop :for ad :across a :for i :from start :do (setf (aref result i) (max (aref result i) (min ad bd))))) result)) (defun lunar:* (&rest arguments) (if (null arguments) 0 (loop :with arguments := (mapcar (function decimal-from-integer) arguments) :while (rest arguments) :do (setf arguments (loop :for (a b) :on arguments :by (function cddr) :if b :collect (binary* a b) :else :collect a)) :finally (return (decimal-to-integer (first arguments)))))) (assert (equal (list (lunar:+ 357 64) (lunar:* 357 64) (lunar:+ 123 65400) (lunar:+ 54321 9876004 4) (lunar:* 54321 9000004 4) (lunar:* 22 54321) (lunar:* 54321 9 8 7 6 5 4) (lunar:* 54321 44) (lunar:+ 54321 9000004)) '(367 3564 65423 9876324 44321044321 222221 44321 444321 9054324)))57s/0/1/ ; sorry.
In Python.
from itertools import zip_longest class lunar(object): def __init__(self, n): self.n = n assert isinstance(n, int) def __add__(self, other): n = self.n res = [] for ni, mi in zip_longest(reversed(str(n)), reversed(str(other)), fillvalue="0"): res.append(max(ni, mi)) return lunar(int("".join(reversed(res)))) def __mul__(self, other): n = self.n res = lunar(0) for shift, mi in enumerate(reversed(str(other))): L = ["0"] * shift + [min(mi, ni) for ni in reversed(str(n))] res = res + lunar(int("".join(reversed(L)))) return res def __pow__(self, p): if p == 0: return lunar(1) if p == 1: return lunar(self.n) if p == 2: return self * self if p % 2 == 0: return self.__pow__(p // 2) ** 2 else: return self.__pow__(p // 2) ** 2 * self def __str__(self): return str(self.n) n = lunar(357) m = lunar(64) print("n * m =", n * m) # 3564 print("n + m =", n + m) # 367 print("n ** 10 =", n ** 10) # 333333333355555555557 print("12321**5 =", lunar(12321) ** 5) # 111112222232222211111Here’s a solution in C.
#include <stdlib.h> #include <stdio.h> int lunar_add(int x, int y) { int result = 0; int multiplier = 1; while (x || y) { int x0 = x % 10; x /= 10; int y0 = y % 10; y /= 10; int max = x0 > y0 ? x0 : y0; result += max * multiplier; multiplier *= 10; } return result; } int lunar_multiply(int x, int y) { int x_copy = x; int result = 0; int multiplier = 1; while (y) { int y0 = y % 10; int product = 0; int inner_multiplier = 1; while (x) { int x0 = x % 10; x /= 10; int min = x0 < y0 ? x0 : y0; product += min * inner_multiplier; inner_multiplier *= 10; } result = lunar_add(result, product * multiplier); y /= 10; multiplier *= 10; x = x_copy; } return result; } int main(int argc, char* argv[]) { if (argc != 3) { fprintf(stderr, "Usage: %s INT INT\n", argv[0]); return EXIT_FAILURE; } int x = atoi(argv[1]); int y = atoi(argv[2]); int sum = lunar_add(x, y); int product = lunar_multiply(x, y); printf("%d + %d = %d\n", x, y, sum); printf("%d * %d = %d\n", x, y, product); return EXIT_SUCCESS; }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:
from itertools import zip_longest # Basic operations on lunar numbers (digit sequences, # least significant first). def int2lunar(n): return [int(c) for c in str(n)][::-1] def lunar2int(n): return int("".join([str(d) for d in n][::-1])) def lunaradd(n,m): # Thanks to Paul for zip_longest return [max(*a) for a in zip_longest(n,m,fillvalue=0)] def lunarmul(n,m): result = [] for i,d in enumerate(n): u = [min(d,e) for e in m] result = lunaradd(result,[0]*i+u) return result # Wrap it up in a nice class class lunar(object): def __init__(self, n): if isinstance(n, int): self.n = int2lunar(n) else: self.n = n def __add__(self, other): return lunar(lunaradd(self.n,other.n)) def __mul__(self, other): return lunar(lunarmul(self.n,other.n)) def __int__(self): return lunar2int(self.n) def __str__(self): return str(int(self)) n = lunar(64) m = lunar(357) print(n+m) print(n*m) # Find the lunar primes with the lunar sieve of Eratosthenes # Note that multiplication is not monotonic, but we can # use the fact that len(n*m) = len(n)+len(m)-1 (where len(n) # is the number of digits) to terminate scan. def lunarprimes(K): N = 10**K primes = [True]*N primes[9] = False for i in range(1,N): if not primes[i]: continue for j in range(2,N): if j == 9: continue if len(lunar(i).n)+len(lunar(j).n)-1 > K: break primes[int(lunar(i)*lunar(j))] = False; return [i for i in range(1,N) if primes[i]] # [19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] print(lunarprimes(2))A Haskell version.
{-# OPTIONS_GHC -fno-warn-type-defaults #-} -- Add two numbers. add :: Integral a => a -> a -> a add 0 0 = 0 add x y = let (xq, xr) = x `quotRem` 10 (yq, yr) = y `quotRem` 10 in max xr yr + 10 * add xq yq -- Multiply a digit and a number. muld :: Integral a => a -> a -> a muld _ 0 = 0 muld d x = let (xq, xr) = x `quotRem` 10 in min d xr + 10 * muld d xq -- Multiply two numbers. mul :: Integral a => a -> a -> a mul 0 _ = 0 mul x y = let (xq, xr) = x `quotRem` 10 in muld xr y `add` (10 * mul xq y) main :: IO () main = do -- Some examples from the Numberphile video. print $ 58 `add` 19 -- 59 print $ 17 `mul` 24 -- 124 print $ 7 `mul` 7 -- 7 print $ 10 `mul` 10 -- 100 print $ 11 `mul` 11 -- 111 print $ 19 `mul` 19 -- 119 -- Variations on the Programming Praxis example. print $ 357 `add` 0 print $ 0 `add` 357 print $ 357 `mul` 64 print $ 64 `mul` 357 print $ 1 `mul` 357 print $ 357 `mul` 0 -- A couple of larger numbers. print $ 12345678901112131415 `mul` 9876543210And apparently, there are applications: https://twitter.com/numberphile/status/1348613413619040256