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 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
40 [3 0 1 0]
means that
We need to pick the four values
Percy Ludgate chose the values
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
table (was in Ludgate’s table, arising from when multiplying ), - The largest nonzero key in the
table (was in Ludgate’s table, arising from when multiplying ).
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
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
table, corresponding to , has a largest key of and largest nonzero key of - The table corresponding to
would have a largest nonzero key of , which is smaller than . (It puts all the 0s later.) - The table corresponding to
would have a largest key of , which is smaller than . - The table corresponding to
would have a largest nonzero key of , and a largest key of . - The table corresponding to
would have a largest nonzero key of , and a largest key of .
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.