We are asked to find numbers that are integer multiples of their reversals, which I call palintiples. Of course, all the palindromic numbers are a trivial example, but if we disregard the unit multiples, the field is narrowed considerably.

Rouse Ball (*Mathematical_recreations_and_essays*) originated the
problem, and G. H. Hardy (*A_mathematician's_apology*) used the result
that 9801 and 8712 are the only four-digit palintiples as an example
of a theorem that is not ``serious*. Martin Beech ( The_mathema-
tical_gazette, Vol 74, #467, pp 50-51, March '90) observed that
989*01 and 879*12 are palintiples, an observation he ``confirmed* on
a hand calculator, and conjectured that these are all that exist.

I confirm that Beech's numbers are palintiples, I will show that they are not all of the palintiples. I will show that the palintiples do not form a regular language. And then I will prove that I have found all the palintiples, by describing the them with a generalized form of regular expression. The results become more interesting in other bases.

First, I have a more reasonable method of confirming that these

- numbers are palintiples
Proof: First, letting "9*" and "0*" refer an arbitrary string of nines and a string of zeroes of the same length, I note that

879*12 = 879*00 + 12 = (880*00 - 100) + 12 = 880*00 - 88 219*78 = 219*00 + 78 = (220*00 - 100) + 78 = 220*00 - 22

989*01 = 989*00 + 1 = (990*00 - 100) + 1 = 990*00 - 99 109*89 = 109*00 + 89 = (110*00 - 100) + 89 = 110*00 - 11

It is obvious that 4x(220*00 - 22) = 880*00 - 88 and that 9x(110*00 - 11) = 990*00 - 99. QED.

Now, to show that these palintiples are not all that exist, let us
take the (infinite) language L__[4__?] = (879*12 + 0*), and let Pal(L__[4__?])
refer to the set of palindromes over the alphabet L__[4__?]. It is
immediate that the numbers in Pal(L__[4__?]) are palintiples. For
instance,

8712 000 87912 879999912 879999912 87912 000 8712

= 4 x 2178 000 21978 219999978 219999978 21978 000 2178

(where I have inserted spaces to enhance readability) is a palintiple.
Similarly, taking L__[9__?] = (989*01 + 0*), the numbers in Pal(L__[9__?]) are
palintiples. We exclude numbers starting with zeroes.

The reason these do not form a regular language is that the sub-palintiples on the left end of the number must be the same (in

- reverse order) as the sub-palintiples on the right end of the number
8712 8712 87999912 = 4 x 2178 2178 21999978

is not a palintiple, because 8712 8712 87999912 is not the reverse of
2178 2178 21999978. The pumping lemma can be used to prove that
Pal(L__[4__?])+Pal(L__[9__?]) is not a regular language, just as in the familiar
proof that the palindromes over a non-singleton alphabet do not form a
regular language.

Now to characterize all the palintiples, let N be a palintiple, N=CxR(N), where R(.) signifies reversal, and C>1 is an integer. (I use "x" for multiplication, to avoid confusion with the Kleene star "*", which signifies the concatenated closure.) If D is a digit of N, let D' refer to the corresponding digit of R(N). Since N=CxR(N), D+10T = CxD'+S, where S is the carry in to the position occupied by D' when R(N) is multiplied by C, and T is the carry out of that position. Similarly, D'+10T'=CxD+S', where S', T' are carries in and out of the position occupied by D when R(N) is multiplied by C.

Since D and D' are so closely related, I will use the symbol D:D' to
refer to a digit D on the left side of a string with a corresponding
digit D' on the right side of the string. More formally, an
expression "x__[1__?]:y__[1__?] x__[2__?]:y__[2__?] ... x__[n__?]:y__[n__?] w" will refer to a
string "x__[1__?] x__[2__?] ... x__[n__?] w y__[n__?] ... y__[2__?] y__[1__?]", where the x__[i__?] and
y__[i__?] are digits and w is a string of zero or one digits. So 989901
may be written as 9:1 8:0 9:9 and 87912 may be written as 8:2 7:1 9.
Thus Pal(L__[4__?])+Pal(L__[9__?]) (omitting numbers with leading zeroes) can be
represented as

(8:2 7:1 9:9* 1:7 2:8 0:0*)*

(0:0* + 0 + 8:2 7:1 ( 9:9* + 9:9* 9))

(9:1 8:0 9:9* 0:8 1:9 0:0*)*

(0:0* + 0 + 9:1 8:0 ( 9:9* + 9:9* 9)). (1)

For each pair of digits D:D', there are a very limited--and often empty--set of quadruples S,T,S',T' of digits that satisfy the equations

D +10T =CxD'+S D'+10T'=CxD +S', (2)

yet such a quadruple must exist for "D:D'" to appear in a palintiple
with multiplier C. Furthermore, the S and T' of one D:D' must be T
and S', respectively, of the next pair of digits that appear. This
enables us to construct a finite state machine to recognize those
palintiples. The states __[X#Y__?] refer to a pair of carries in D and D',
and we allow a transition from state __[T#S'__?] to state __[S#T'__?] on input
symbol D:D' exactly when equations (2) are satisfied. Special
transitions for a single-digit input symbol (the central digit of
odd-length palintiples) and the criteria for the initial and the
accepting states are left as exercises. The finite state machines
thus formed are

State Symbol New Symbol New Symbol New

Accept? State State State

-->

[0#0? Y 8:2[0#3? 0:0[0#0? 0[A?

[0#3? N 7:1[3#3?[3#3? Y 1:7[3#0? 9:9[3#3? 9[A?[3#0? N 2:8[0#0?

[A? Y

for constant C=4, and

State Symbol New Symbol New Symbol New

Accept? State State State

-->

[0#0? Y 1:9[0#8? 0:0[0#0? 0[A?

[0#8? N 8:0[8#8?[8#8? Y 0:8[8#0? 9:9[8#8? 9[A?[8#0? N 9:1[0#0?

[A? Y

for constant C=9, and the finite state machines for other constants accept only strings of zeroes. It is not hard to verify that the proposed regular expression (1) represents the union of the languages accepted by these machines, omitting the empty string and strings beginning with zero.

I have written a computer program that constructs finite state machines for recognizing palintiples for various bases and constants. I found that base 10 is actually an unusually boring base for this problem. For instance, the machine for base 8, constant C=5 is

State Symbol New Symbol New Symbol New

Accept? State State State

-->

[0#0? Y 0:0[0#0? 5:1[0#3? 0[A?

[0#3? N 1:0[1#1? 6:1[1#4?[1#1? Y 0:1[3#0? 5:2[3#3?[3#0? N 1:5[0#0? 6:6[0#3? 6[A?[3#3? Y 2:5[1#1? 7:6[1#4?[1#4? N 1:1[4#1? 6:2[4#4? 1[A?[4#4? Y 2:6[4#1? 7:7[4#4?] 7[A?[4#1? N 1:6[3#0? 6:7[3#3?[A?] Y

for which I invite masochists to write the regular expression. If anyone wants more, I should remark that the base 29 machine for constant C=18 has 71 states!

By the way, I did not find any way of predicting the size or form of the machines for the various bases, except that the machines for C=B-1 all seem to be isomorphic to each other. If anyone investigates the general behavior, I would be most happy to hear about it.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil
May, 1992
__[ A preliminary version of this message appeared in April, 1991.__?]
================================================================
Dan