Blog

Improving on Percy Ludgate's "Irish logarithm"

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=23305170).

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 0d9) 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:

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

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.