Improving on Percy Ludgate's "Irish logarithm"

October 03, 2023

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 (a b) = f (a) + f (b)$ . For example, this rule defines $f (6)$ as $2 f (3)$ , and $f (28)$ as $2 f (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) = 3 f (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 \leq d \leq 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.