A quick follow-up to yesterday’s post on the “Irish logarithm” of Percy Ludgate.
To recap, the idea is to pick four numbers $f(2)$, $f(3)$, $f(5)$, $f(7)$, and then for all products of nonzero one-digit numbers, define the values of $f$ with $f(ab) = f(a) + f(b)$. For example, this rule defines $f(6)$ as $2f(3)$, and $f(28)$ as $2f(2) + f(7)$. We can write the following Python code to enumerate all these consequences (using array from numpy just for the convenience of adding tuples element-wise with +):
from numpy import array
r = {} # Representation (primes' exponents)
r[2] = array([1, 0, 0, 0])
r[3] = array([0, 1, 0, 0])
r[5] = array([0, 0, 1, 0])
r[7] = array([0, 0, 0, 1])
r[9] = r[3] + r[3]
for a in range(2, 10):
for b in range(2, 10):
v = r[a] + r[b]
if a * b in r:
assert (r[a * b] == v).all()
else:
r[a * b] = v
for k in sorted(r.keys()):
print(f"{k:2} {r[k]}")
which prints the following 35 lines of output:
2 [1 0 0 0]
3 [0 1 0 0]
4 [2 0 0 0]
5 [0 0 1 0]
6 [1 1 0 0]
7 [0 0 0 1]
8 [3 0 0 0]
9 [0 2 0 0]
10 [1 0 1 0]
12 [2 1 0 0]
14 [1 0 0 1]
15 [0 1 1 0]
16 [4 0 0 0]
18 [1 2 0 0]
20 [2 0 1 0]
21 [0 1 0 1]
24 [3 1 0 0]
25 [0 0 2 0]
27 [0 3 0 0]
28 [2 0 0 1]
30 [1 1 1 0]
32 [5 0 0 0]
35 [0 0 1 1]
36 [2 2 0 0]
40 [3 0 1 0]
42 [1 1 0 1]
45 [0 2 1 0]
48 [4 1 0 0]
49 [0 0 0 2]
54 [1 3 0 0]
56 [3 0 0 1]
63 [0 2 0 1]
64 [6 0 0 0]
72 [3 2 0 0]
81 [0 4 0 0]
The four elements in the tuple are the coefficients of $f(2), f(3), f(5), f(7)$ respectively — for example the line
40 [3 0 1 0]
means that $f(40) = 3f(2) + f(5)$ (and also that $40 = 2^3 \cdot 3^0 \cdot 5^1 \cdot 7^0$).
We need to pick the four values $f(2), f(3), f(5), f(7)$ (and a fifth one, $f(0)$) such that all $35$ resulting values (and also the ten values $f(0) + f(d)$ for $0 \le d \le 9$) are all distinct from one another.
Percy Ludgate chose the values $f(2), f(3), f(5), f(7), f(0)$ (as $1, 7, 23, 33, 50$) by a greedy process to make the values of $f$ (or the keys of the $g$ table) as small as possible, as explained in the previous post.
Whenever there’s a greedy algorithm, it is natural to ask: is this optimal?
In this case, there are actually two values it makes sense to optimize:
- The largest key in the $g$ table (was $100$ in Ludgate’s table, arising from $f(0) + f(0)$ when multiplying $0 \times 0$),
- The largest nonzero key in the $g$ table (was $66$ in Ludgate’s table, arising from $f(7) + f(7)$ when multiplying $7 \times 7$).
Anyway (I’m trying not to spend too much time on this), here’s some quick-and-dirty code (quick to write, slow to run) that searches through possible values of $f(2), f(3), f(5), f(7)$ (after these are chosen, it is clearly optimal to choose $f(0)$ greedily) — append it to the code above (this could be a lot cleaner/faster and more readable, but not in a good state right now):
best_max = 10**10
best_nonzero_max = 10**10
for a in range(1, 60):
print(a)
for b in range(1, 60):
for c in range(1, 60):
for d in range(1, 60):
seen = {}
ok = True
t1 = {1: 0}
t2 = {}
for k in r:
(x, y, z, w) = r[k]
v = a * x + b * y + c * z + d * w
if v in seen:
ok = False
break
seen[v] = True
if v > best_max:
ok = False
break
if k < 10:
t1[k] = v
t2[v] = k
if not ok:
continue
e = 0
while True:
e += 1
if any(e + t1[k] in t2 for k in range(1, 10)) or 2 * e in t2:
continue
break
t1[0] = e
for x in range(10):
k = t1[0] + t1[x]
t2[k] = 0
# See if this is any better
this_max = max(t2)
this_nonzero_max = max(v for v in t2 if t2[v])
if this_max < best_max or this_nonzero_max < best_nonzero_max:
print(f"{a} {b} {c} {d} ({e}) => {this_nonzero_max} {this_max}")
best_max = min(best_max, this_max)
best_nonzero_max = min(best_nonzero_max, this_nonzero_max)
This prints:
1 7 23 33 (50) => 66 100
1 7 29 38 (48) => 76 96
1 11 16 39 (46) => 78 92
1 13 21 30 (61) => 60 122
1 15 24 34 (41) => 68 82
showing that (some results are from a slightly modified program):
- Ludgate’s $g$ table, corresponding to $1, 7, 23, 33, 50$, has a largest key of $100$ and largest nonzero key of $66$
- The table corresponding to $1, 13, 21, 30, 61$ would have a largest nonzero key of $60$, which is smaller than $66$. (It puts all the 0s later.)
- The table corresponding to $1, 15, 24, 34, 41$ would have a largest key of $82$, which is smaller than $100$.
- The table corresponding to $10, 1, 26, 33, 47$ would have a largest nonzero key of $66$, and a largest key of $94$.
- The table corresponding to $5, 1, 26, 33, 45$ would have a largest nonzero key of $66$, and a largest key of $90$.
So Ludgate’s numbers can be “improved” slightly, but of course we used a large amount of computer time to find these values, while Ludgate was designing a computer at a time when one did not exist.