https://blog.plover.com/math/irish-logarithm.html
The Universe of Discourse
Mark Dominus (Tao Sun, 01 Oct 2023
Min Xiu )
mjd@pobox.com The Irish logarithm
[TOP] The Wikipedia article on "Irish logarithm" presents
this rather weird little algorithm, invented by
About me Percy Ludgate. Suppose you want to multiply !!a!!
and !!b!!, where both are single-digit numbers !!
RSS Atom 0<=a,b<=9!!.
12 recent entries Normally you would just look it up on a
multiplication table, but please bear with me for a
The Irish bit.
logarithm
Horizontal and To use Ludgate's algorithm you need a different
vertical little table:
complexity
The Killer Whale $$ \begin{array}{rl} T_1 = & \begin{array}
Dagger {cccccccccc} \tiny\color{gray}{0} & \tiny\color
My favorite {gray}{1} & \tiny\color{gray}{2} & \tiny\color
luxurious office {gray}{3} & \tiny\color{gray}{4} & \tiny\color
equipment is {gray}{5} & \tiny\color{gray}{6} & \tiny\color
low-tech {gray}{7} & \tiny\color{gray}{8} & \tiny\color
Mystery of the {gray}{9} \\ 50 & 0 & 1 & 7 & 2 & 23 & 8 & 33 & 3 &
missing skin tone 14 \\ \end{array} \end{array} $$
Math SE report
2023-06: and a different bigger one:
funky-looking
Hasse diagrams, $$ \begin{array}{rl} T_2 = & % \left( \begin{array}
and what is a {rrrrrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4,
polynomial & 8, & 16, & 32, & 64, & 3, & 6, & 12, \\ {\tiny\
anyway? color{gray}{10}} & 24, & 48, & 0, & 0, & 9, & 18, &
Ganto's axe does 36, & 72, & 0, & 0, \\ {\tiny\color{gray}{20}} & 0,
have & 27, & 54, & 5, & 10, & 20, & 40, & 0, & 81, & 0,
computational \\ {\tiny\color{gray}{30}} & 15, & 30, & 0, & 7, &
content 14, & 28, & 56, & 45, & 0, & 0, \\ {\tiny\color
No plan survives {gray}{40}} & 21, & 42, & 0, & 0, & 0, & 0, & 25, &
contact with the 63, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0,
enemy & 0, & 0, & 0, & 0, & 35, & 0, & 0, & 0, \\ {\tiny\
Three words, color{gray}{60}} & 0, & 0, & 0, & 0, & 0, & 0, & 49
three lies \hphantom{,} \end{array} % \right) \end{array} $$
Worst waterfall
in the U.S. and I've formatted !!T_2!! in rows for easier reading,
Doug Burgum pays but it's really just a zero-indexed list of !!101!!
me $19 numbers. So for example !!T_2(23)!! is !!5!!.
Computational
content of The tiny gray numbers in the margin are not part of
Ganto's axe the table, they are counting the elements so that
Can you identify it is easy to find element !!23!!.
this language?
Ludgate's algorithm is simply:
Archive:
$$ ab = T_2(T_1(a) + T_1(b)) $$
2023: JFMAMJ
JASO Let's see an example. Say we want to multiply !!
2022: JFMAMJ 4x7!!. We first look up !!4!! and !!7!! in !!T_1!!,
JASOND and get !!2!! and !!33!!, which we add, getting !!
2021: JFMAMJ 35!!. Then !!T_2(35)!! is !!28!!, which is the
JASOND correct answer.
2020: JFMAMJ
JASOND This isn't useful for paper-and-pencil calculation,
2019: JFMAMJ because it only works for products up to !!9x9!!,
JASOND and an ordinary multiplication table is easier to
2018: JFMAMJ use and remember. But Ludgate invented this for use
JASOND in a mechanical computing engine, for which it is
2017: JFMAMJ much better-suited.
JASOND
2016: JFMAMJ The table lookups are mechanically very easy. They
JASOND are simple one-dimensional lookups: to find !!T_1
2015: JFMAMJ (6)!! you just look at entry !!6!! in the !!T_1!!
JASOND table, which can be implemented as a series of ten
2014: JFMAMJ metal rods of different lengths, or something like
JASOND that. Looking things up in a multiplication table
2013: JFMAMJ is harder because it is two-dimensional.
JASOND
2012: JFMAMJ The single addition in Ludgate's algorithm can also
JASOND be performed mechanically: to add !!T_1(a)!! and !!
2011: JFMAMJ T_1(b)!!, you have some thingy that slides up by !!
JASOND T_1(a)!! units, and then by !!T_1(b)!! more, and
2010: JFMAMJ then wherever it ends up is used to index into !!
JASOND T_2!! to get the answer. The !!T_2!! table doesn't
2009: JFMAMJ have to be calculated on the fly, it can be made up
JASOND ahead of time, and machined from brass or
2008: JFMAMJ something, and incorporated directly into the
JASOND machine. (It's tempting to say "hardcoded".)
2007: JFMAMJ
JASOND The tables look a little uncouth at first but it is
2006: JFMAMJ not hard to figure out what is going on. First off,
JASOND !!T_1!! is the inverse of !!T_2!! in the sense that
2005: OND $$T_2(T_1(n)) = n\tag{$\color{darkgreen}{\
spadesuit}$}$$
----------------- whenever !!n!! is in range -- that is when !!0<= n <=
Subtopics: 9!!.
Mathematics 229 !!T_2!! is more complex. We must construct it so
Programming 96 that
Language 91
Miscellaneous 66 $$T_2(T_1(a) + T_1(b)) = ab.\tag{$\color{purple}{\
Book 48 clubsuit}$}$$
Tech 47
Haskell 33 for all !!a!! and !!b!! of interest, which means
Oops 30 that !!0\le a, b\le 9!!.
Etymology 30
Unix 27 If you look over the table you should see that the
Cosmic Call 25 entry !!n!! is often followed by !!2n!!. That is,
Math SE 21 !!T_2(i+1) = 2T_2(i)!!, at least some of the time.
Physics 21 And in fact, this is true in all the cases we care
Law 21 about, where !!2n = ab!! for some single digits !!
Perl 17 a, b!!.
Biology 15
The second row could just as well have started with
[mjd-univer] !!24, 48, 96, 192!!, but Ludgate doesn't need the
Higher-Order Perl !!96, 192!! entries, so he made them zero, which
Blosxom really means "I don't care". This will be important
later.
Comments disabled
The algorithm says that if we want to compute !!
2n!!, we should compute $$ \begin{align} 2n & = T_2
(T_1(2) + T_1(n)) && \text{Because $\color{purple}
{\clubsuit}$} \\ & = T_2(1 + T_1(n)) \\ & = 2T_2
(T_1(n)) && \text{Because moving one space right
doubles the value}\\ & = 2n && \text{Because $\
color{darkgreen}{\spadesuit}$} \end{align} $$
when !!0<=n<=9!!.
I formatted !!T_2!! in rows of !!10!! because that
makes it easy to look up examples like !!T_2(35) =
28!!, and because that's how Wikipedia did it. But
this is very misleading, and not just because it
makes !!T_2!! appear to be a !!10x10!! table when
it's really a vector. !!T_2!! is actually more like
a compressed version of a !!7x4x3x3!! table.
Let's reformat the table so that the rows have
length !!7!! instead of !!10!!:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
5, & 10, & 20, & 40, & 0, \\ {\tiny\color{gray}
{28}} & 81, & 0, & 15, & 30, & 0, & 7, & 14, \\ {\
tiny\color{gray}{35}} & 28, & 56, & 45, & 0, & 0, &
21, & 42, \\ {\tiny\color{gray}{42}} & 0, & 0, & 0,
& 0, & 25, & 63, & 0, \\ {\tiny\color{gray}{49}} &
0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{56}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{63}} & 0, & 0, & 0, & 49 \\ \end
{array} $$
We have already seen that moving one column right
usually multiplies the entry by !!2!!. Similarly,
moving down by one row is seen to triple the !!
T_2!! value -- not always, but in all the cases of
interest. Since the rows have length !!7!!, moving
down one row from !!T_2(i)!! gets you to !!T_2
(i+7)!!, and this is why !!T_1(3) = 7!!: to compute
!!3n!!, one does:
$$ \begin{align} 3n & = T_2(T_1(3) + T_1(n)) && \
text{Because $\color{purple}{\clubsuit}$} \\ & =
T_2(7 + T_1(n)) \\ & = 4T_2(T_1(n)) && \text
{Because moving down triples the value}\\ & = 3n &&
\text{Because $\color{darkgreen}{\spadesuit}$} \end
{align} $$
Now here is where it gets clever. It would be
straightforward easy to build !!T_2!! as a stack of
!!5x7!! tables, with each layer in the stack having
entries quintuple the layer above, like this:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} &
81, & 0, & 0, & 0, & 0, & 0, & 0, \\ \\ {\tiny\
color{gray}{35}} & 5, & 10, & 20, & 40, & 0, & 0, &
0, \\ {\tiny\color{gray}{42}} & 15, & 30, & 0, & 0,
& 0, & 0, & 0, \\ {\tiny\color{gray}{49}} & 45, &
0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}
{56}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\
color{gray}{63}} & 0, & 0, & 0, & 0, & 0, & 0, & 0,
\\ \\ {\tiny\color{gray}{70}} & 25, & 0, & 0, & 0,
& 0, & 0, & 0, \\ {\tiny\color{gray}{77}} & 0, & 0,
& 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{84}}
& 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{91}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{98}} & 0, & 0, & 0, & 0, & 0, &
0, & 0, \\ \end{array} $$
This works, if we make !!T_1(5)!! the correct
offset, which is !!7*5 = 35!!. But it wastes space,
and the larger !!T_2!! is, the more complicated and
expensive is the brass thingy that encodes it. The
last six entries of the each layer in the stack are
don't-cares, so we can just omit them:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} &
81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20,
& 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} &
15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\
tiny\color{gray}{58}} & 25, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{65}} & 0, & 0, & 0, &
0, & 0, & 0, & 0, \\ {\tiny\color{gray}{72}} & 0, &
0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}
{79}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\
color{gray}{86}} & 0\hphantom{,} \\ \end{array} $$
And to compensate we make !!T_1(5) = 29!! instead
of !!35!!: you now move down one layer in the stack
by skipping !!29!! entries forward, instead of !!
35!!.
The table is still missing all the multiples of !!
7!!, but we can repeat the process. The previous
version of !!T_2!! can now be thought of as a !!
29x3!! table, and we can stack another !!29x3!!
table below it, with all the entries in the new
layer being !!7!! times the original one:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} &
81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20,
& 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} &
15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\
tiny\color{gray}{58}} & 25, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{65}} & 0, & 0, & 0, &
0, & 0, & 0, & 0, \\ {\tiny\color{gray}{72}} & 0, &
0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}
{79}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\
color{gray}{86}} & 0, \\ \\ \hline \\ {\tiny\color
{gray}{87}} & 7, & 14, & 28, & 56, & 0, & 0, & 0, \
\ {\tiny\color{gray}{94}} & 21, & 42, & 0, & 0, &
0, & 0, & 0, \\ {\tiny\color{gray}{101}} & 63, & 0,
& 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}
{108}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny
\color{gray}{115}} & 0, \\ \\ {\tiny\color{gray}
{116}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\
tiny\color{gray}{123}} & 0, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{130}} & 0, & 0, & 0,
& 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{137}} &
0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{144}} & 0, \\ \\ {\tiny\color{gray}{145}} &
0, & 0, & 0, & 0, & 0, & 0, & \ldots \\ \\ \hline \
\ {\tiny\color{gray}{174}} & 49\hphantom{,} \\ \end
{array} $$
Each layer in the stack has !!29*3 = 87!! entries,
so we could take !!T_1(7) = 87!! and it would work,
but the last !!28!! entries in every layer are
zero, so we can discard those and reduce the layers
to !!59!! entries each.
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} &
81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20,
& 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} &
15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\
tiny\color{gray}{58}} & 25, \\ \\ \hline \\ {\tiny\
color{gray}{59}} & 7, & 14, & 28, & 56, & 0, & 0, &
0, \\ {\tiny\color{gray}{66}} & 21, & 42, & 0, & 0,
& 0, & 0, & 0, \\ {\tiny\color{gray}{73}} & 63, &
0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}
{80}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\
color{gray}{87}} & 0, \\ \\ {\tiny\color{gray}{88}}
& 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{95}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{102}} & 0, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{109}} & 0, & 0, & 0,
& 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{116}} &
0, \\ \\ {\tiny\color{gray}{117}} & 0, \\ \\ \hline
\\ {\tiny\color{gray}{118}} & 49\hphantom{,} \\ \
end{array} $$
Doing this has reduced the layers from !!87!! to !!
59!! elements each, but Ludgate has another trick
up his sleeve. The last few numbers in the top
layer are !!45, 25,!! and a lot of zeroes. If he
could somehow finesse !!45!! and !!25!!, he could
trim the top two layers all the way back to only 38
entries each:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} &
81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20,
& 40, & 80, & 0, & 0, \\ {\tiny\color{gray}{36}} &
15, & 30, \\ \\ \hline \\ {\tiny\color{gray}{38}} &
7, & 14, & 28, & 56, & 0, & 0, & 0, \\ {\tiny\color
{gray}{45}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\
{\tiny\color{gray}{52}} & 63, & 0, & 0, & 0, & 0, &
0, & 0, \\ {\tiny\color{gray}{59}} & 0, & 0, & 0, &
0, & 0, & 0, & 0, \\ {\tiny\color{gray}{66}} & 0, \
\ \\ {\tiny\color{gray}{67}} & 35, & 70, & 0, & 0,
& 0, & 0, & 0, \\ {\tiny\color{gray}{74}} & 0, & 0,
\\ \hline \\ {\tiny\color{gray}{76}} & 49\hphantom
{,} \\ \end{array} $$
We're now missing !!25!! and we need to put it
back. Fortunately the place we want to put it is !!
T_1(5) + T_1(5) = 29+29 = 58!!, and that slot
contains a zero anyway. And similarly we want to
put !!45!! at position !!14+29 = 43!!, also empty:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} &
81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20,
& 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} &
15, & 30, \\ \\ \hline \\ {\tiny\color{gray}{38}} &
7, & 14, & 28, & 56, & 0, & \color{purple}{45}, &
0, \\ {\tiny\color{gray}{45}} & 21, & 42, & 0, & 0,
& 0, & 0, & 0, \\ {\tiny\color{gray}{52}} & 63, &
0, & 0, & 0, & 0, & 0, & \color{purple}{25}, \\ {\
tiny\color{gray}{59}} & 0, & 0, & 0, & 0, & 0, & 0,
& 0, \\ {\tiny\color{gray}{66}} & 0, \\ \\ {\tiny\
color{gray}{67}} & 35, & 0, & 0, & 0, & 0, & 0, &
0, \\ {\tiny\color{gray}{74}} & 0, & 0, \\ \\ \
hline \\ {\tiny\color{gray}{76}} & 49\hphantom{,} \
\ \end{array} $$
The arithmetic pattern is no longer as obvious, but
property !!\color{purple}{\clubsuit}!! still holds
We're not done yet! The table still has a lot of
zeroes we can squeeze out. If we change !!T_1(5)!!
from !!29!! to !!23!!, the !!5,10,20,40!! group
will slide backward to just after the !!54!!, and
the !!15, 30!! will move to the row below that.
We will also have to move the other multiples of !!
5!!. The !!5!! itself moved back by six entries,
and so did everything after that in the table,
including the !!35!! (from position !!32+29!! to !!
32+23!!) and the !!45!! (from position !!14+29!! to
!!14+23!!) so those are still in the right places.
Note that this means that !!7!! has moved from
position !!38!! to position !!32!!, so we now have
!!T_1(7) = 32!!.
But the !!25!! is giving us trouble. It needed to
move back twice as far as the others, from !!29+29
= 58!! to !!23+23 = 46!!, and unfortunately it now
collides with !!63!! which is currently at position
!!7+7+32 = 46!!.
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
\color{purple}{5}, & \color{purple}{10}, & \color
{purple}{20}, & \color{purple}{40}, & 0, \\ {\tiny\
color{gray}{28}} & 81, & 0, & \color{purple}{15} &
\color{purple}{30}, \\ \\ \hline \\ {\tiny\color
{gray}{32}} & 7, & 14, & 28, & 56, & 0, & \color
{darkgreen}{45}, & 0, \\ {\tiny\color{gray}{39}} &
21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color
{gray}{46}} & {63\atop\color{darkred}{?25?}} & 0, &
0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{53}} &
0, & 0, & \color{darkgreen}{35}, & 0, & 0, & 0, &
0, \\ {\tiny\color{gray}{60}} & 0, & 0, & 0, & 0, \
\ \\ \hline \\ {\tiny\color{gray}{64}} & 49\
hphantom{,} \\ \end{array} $$
We need another tweak to fix !!25!!. !!7!! is
currently at position !!32!!. We can't move !!7!!
any farther back to the left without causing more
collisions. But we can move it forward, and if we
move it forward by one space, the !!63!! will move
up one space also and the collision with !!25!!
will be solved. So we insert a zero between !!30!!
and !!7!!, which moves up !!7!! from position !!
32!! to !!33!!:
$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} &
1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color
{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\
{\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0,
& 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, &
5, & 10, & 20, & 40, & 0, \\ {\tiny\color{gray}
{28}} & 81, & 0, & 15 & 30, \\ \\ \hline \\ {\tiny\
color{gray}{32}} & \color{purple}{0}, & \color
{darkgreen}{7}, & \color{darkgreen}{14}, & \color
{darkgreen}{28}, & \color{darkgreen}{56}, & 45, &
0, \\ {\tiny\color{gray}{39}} & 0, & \color
{darkgreen}{21}, & \color{darkgreen}{42}, & 0, & 0,
& 0, & 0, \\ {\tiny\color{gray}{46}} & 25,& \color
{darkgreen}{63}, & 0, & 0, & 0, & 0, & 0, \\ {\tiny
\color{gray}{53}} & 0, & 0, & 0, & \color
{darkgreen}{35}, & 0, & 0, & 0, \\ {\tiny\color
{gray}{60}} & 0, & 0, & 0, & 0, \\ \\ \hline \\ {\
tiny\color{gray}{64}} & \color{purple}{0}, & \color
{purple}{0}, & \color{darkgreen}{49}\hphantom{,} \\
\end{array} $$
All the other multiples of !!7!! moved up by one
space, but not the non-multiples !!25!! and !!45!!.
Also !!49!! had to move up by two, but that's no
problem at all, since it was at the end of the
table and has all the space it needs.
And now we are done! This is exactly Ludgate's
table, which has the property that
$$T_2(p + 7q + 23r + 33s) = 2^p3^q5^r7^s$$
whenever !!2^p3^q5^r7^s = ab!! for some !!
0<=a,b<=9!!. Moving right by one space multiplies the
!!T_2!! entry by !!2!!, at least for the entries we
care about. Moving right by seven spaces multiplies
the entry by !!3!!. To multiply by !!5!! or !!7!!
we move right by or !!23!! or by !!33!!,
respectively.
These are exactly the values in the !!T_1!! table:
$$\begin{align} T_1(2) & = 1\\ T_1(3) & = 7\\ T_1
(5) & = 23\\ T_1(7) & = 33 \end{align}$$
The rest of the !!T_1!! table can be obtained by
remembering !!\color{darkgreen}{\spadesuit}!!, that
!!T_2(T_1(n)) = n!!, so for example !!T_1(6) = 8!!
because !!T_2(8) = 6!!. Or we can get !!T_1(6)!! by
multiplication, using !!\color{purple}{\
clubsuit}!!: multiplying by !!6!! is the same as
multiplying by !!2!! and then by !!3!!, which means
you move right by !!1!! and then by !!7!!, for a
total of !!8!!. Here's !!T_1!! again for reference:
$$ \begin{array}{rl} T_1 = & \begin{array}
{cccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9
\\ \hline 50 & 0 & 1 & 7 & 2 & 23 & 8 & 33 & 3 & 14
\\ \end{array} \end{array} $$
(Actually I left out a detail: !!T_1(0) = 50!!.
Ludgate wants !!T_2(T_1(0) + T_1(b)) = 0!! for all
!!b!!. So we need !!T_2(T_1(0) + k) = 0!! for each
!!k!! in !!T_1!!. !!T_1(0) = 50!! is the smallest
value that works. This is rather painful, because
it means that the !!66!!-item table aboveis not
sufficient. Ludgate has to extend !!T_2!! all the
way out to !!101!! items in order to handle the
seemingly trivial case of !!0\cdot 0 = T_2(50 +
50)!!. But the last 35 entries are all zeroes, so
the the brass widget probably doesn't have to be
too much more complicated.)
Wasn't that fun? A sort of mathematical engineering
or a kind that is not been really useful for at
least fifty years.
But actually that was not what I planned to write
about! (Did you guess that was coming?) I thought I
was going to write this bit as a brief introduction
to something else, but the brief introduction
turned out to be 2500 words and a dozen complicated
tables.
We can only hope that part 2 is forthcoming. I
promise nothing.
[Other articles in category /math] permanent link