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 4

There 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.

Pages: 1 2

7 Responses to “Lunar Arithmetic”

1.
(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 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)))

2. 57s/0/1/ ; sorry.

3. Paul said

In Python.

from itertools import zip_longest

class lunar(object):

def __init__(self, n):
self.n = n
assert isinstance(n, int)

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)  # 111112222232222211111

4. Daniel said

Here’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 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:

\$ ./a.out 357 64
357 + 64 = 367
357 * 64 = 3564

5. matthew said

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]))

# 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]
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 __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))

6. Globules said

{-# OPTIONS_GHC -fno-warn-type-defaults #-}

add :: Integral a => a -> a -> a
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 `mul`  64
print \$  64 `mul` 357
print \$   1 `mul` 357
print \$ 357 `mul`   0

-- A couple of larger numbers.
print \$ 12345678901112131415 `mul` 9876543210

\$ ./lunar
59
124
7
100
111
119
357
357
3564
3564
111
0
12345678987654333445555543210