A Special Class of Reverse Digit Multiples

She thinks it’s all pointless, jejune artifice,

But everything rhymes in the nation of spice.

As discussed in another note, for a given base B and constant integer k there may be integers N such that kN = R_B(N), where R_B(N) signifies the number with reversed digits of N in base B. For example, with B=10 and k=4 we have 4*2178 = 8712.

For an n-digit number we can denote the digits of N (in the base B) from least to most significant as d₀, d₁, d₂, …, d_n, and we can let c₀, c₁, c₂, … c_n-1 denote the sequence of carries when multiplying N by k. We stipulate the c_-1 = c_n = 0, and for convenience we define the column vectors for matched pairs of digits and carries as follows

Then, in matrix form, the conditions on successive pairs of digits and carries from the outside inwards, as given in the previous note, can be written as

where

Since the components of C (i.e., the values of the carries) are always in the range from 0 to k-1, we can show the values of the components of D as two k x k arrays, and noting the viable solutions give integer values. For certain combinations of B and K we get a remarkably complete and orderly set of solutions.  An example is with B=29, k=5. In this case, noting that the boundary carries are [c_-1, c_n]^T = [0,0], the viable pairs of digits are those on the left hand column in the table below.

The first numbers in each pair are incremented by columns, and the second numbers are incremented by rows.  This makes it symmetrical, in the sense that every pair of digits (a,b) is symmetrical with a pair of digits (b,a).  The digits 5, 11, 17, 23 do not appear in any solution. A two digit solution is [1][6] in base 29, meaning that 5(1*29+6) = (1+6*29). The values of 1 and 6 are along the diagonal of the k x k arrays showing the components of the D vectors, so the carries in this pair are equal, [1,1]^T, and the next pair of digits needs to come from that menu. To expand to a 4-digit solution, we could select, say, the digits [9][19], giving the solution [1][9][19][6]. Since these two new digits imply the next carries [3,3]^T, we would need to select a pair of digits from the [3,3]^T menu.  Each menu has a set of repeated digits, i.e., [0][0], or [1][1], or [2][2], and so on. We could insert just one of these to make a solution with an odd number of digits. But let’s select [22][27] for the next pair of digits, so we now have constructed the 6-digit example [1][9][22][27][19][6], and since this pair came from the [4,4]^T carries, the next pair would need to come from that menu. Suppose we select [24][4], which corresponds to the [0,0]T carries, so we could choose the pair of digits [0][0] from that menu, and since it corresponds again to zero carries, we would choose [3][18] for the next pair of digits. If we stop at this point, we have a 12-digit solution

and we can directly verify that

with B=29.  One of the interesting things about this special class of solutions is that the digits evaluated modulo k+1 = 6 are precisely the sequence of carries when multiplying N by k = 5. This is a characteristic of this special class of solutions. In fact, the quotients of the digits when divided by k+1 are also the sequence of carries. As a result, both the numerator and denominator base polynomials are simple multiples of the palindromic polynomial whose coefficients are the carries. Thus the ratio above can be written as

where

The second factor has the matched coefficients 1, 3, 4, 0, 0, 3, 0, 0, 4, 3, 1, which is the sequence of carries when multiplying N by k. Since the Φ polynomials cancel out of the ratio, we must have

which implies B = k(k+1) − 1.  In this example, with k=5, we have B=29. Since the carries are always less than k, one might wonder why we don’t find some coefficients equal to k when we evaluate the digits modulo k+1, but as we noted above, the values that do not appear on any of the menus are precisely the values congruent to k modulo k+1, so we are assured the carries are always in the correct range.

Since the Φ polynomial is arbitrary (provided the coefficients are less then B), we can easily construct solutions with other B,k values with the same Φ.  For example, using the Φ polynomial above we have the following solution with B=41, k=6

Again the digits of Φ are the carries when we multiply the denominator by 6 to yield the numerator, and they are also the quotients and the remainders of the digits of the solution modulo 7.

We have examples of this “complete” structure for any B,k such that B = k(k+1) – 1. Thus with k = 2 or 3 we have the examples

As suggested by Young (1992) and Sloane (2014), it’s sometimes convenient to depict the possible solutions of reverse digit multiples as graphs, with each node of the graph corresponding to a pair of carries, and with the digit pairs shown as transitions from one node to another. To illustrate, the figure below gives a depiction of the case B=11, k=3.

There are also similar structures that  involve increments larger than 1, as shown be the following examples.

In these special cases the solutions are all along the diagonal of the k x k arrays, so we can identify each carry index by the respective row, but in the general case, the menu items would include the relevant carry pair along with each digit pair on the menus. This directs us to the next menu when we select a digit pair from the current menu.

We can parameterize all these “complete” solutions in terms of the ratio k and a skip parameter ε, that signifies the increment in the table of digit pairs. We will find that, in general, the base B is related of k and ε by

The simplest case is with ε = 0, in which case B = k. For example, with k = 4 and ε = 0 we have the solution with the graph shown below.

As can be seen, in this ε = 0 case the digit pairs are precisely the destination and source carry indices, e.g., the arrow from State 1 to State 3 is assigned the digit pair 3,1. A table of the digit pairs for each transition is shown below.

For a ε = 0 graph the ratio property is trivial, because the sequence of digits in the numerator (the first digits in each pair) around any suitable loop beginning and ending at state [0,0] is the same as the sequence of digits in the denominator, but shifted by one place. We can arbitrarily choose this string, but it always gives a ratio of the form string0/0string, meaning the numerator is just B (=k) times the denominator. For non-zero values of ε, the results are less trivial, because we are restricted to subsets of the base-B digits for each successive choice of digits.

The general rule for constructing the table of digit pairs for a complete solution is to begin with 0,0 in the upper left and increment the first digit row-wise (and the second digit column-wise) by ε, except when advancing to the next row (column), in which case increment by ε+1. So, for example, with ε=1 and k=4 the complete solution occurs with B=19 and has the digit table

Opposite digit pairs are complementary, e.g., the pair 1,5 and 17,13 sum component-wise to 18,18. In general, for any such “complete solution”, letting s denote the source index for [s,s] and d denote the destination index for [d,d], the transition digit pair α,β is given by

For example, in the above table with ε=1, k=4, the transition digits from [2,2] to [1,1] are α=7, β=11.  The “opposite” transition to s,d is s’ = (k−1−s), d’ = (k−1−d), so the complementarity of opposite digit pairs can be seen from

and similarly for β + β’.

An interesting aspect of these complete solutions is that the graph gives two-way connections between every pair of the “diagonal” states (including self-connections), so we can choose arbitrary paths, and in this way we can encode arbitrary information into solutions. For example, we can map the alphabet into the diagonal states of a graph with B=755, k=27, ε=1, and generate solutions that encode any textual content, such as

This is a perfect reverse digit multiple, but it contains some additional structure, seen most clearly by writing the digits modulo k+1 = 28. The numerator digits, modulo 28, are 0, 19, 8, 1, 11, … and so on. These, as discussed previously, are precisely the sequence of carries when multiplying N by k. If we associate the 0 residue class with a space, and the residue classes 1 through 26 with the letters A through Z of the alphabet, the above ratio appears as

This shows how, in theory, we could encode the entire works of Shakespeare into a reverse digit multiple ratio. As always (for this special class of solutions), the numerator and denominator can be factored and the ratio written as

where

One of the interesting things about this subject is that the reversal requirement leads to the basic elements being pairs of digits working inwards from opposite ends of the number. This implies distant correlations, even though there is a large amount of freedom in the sequence of digits. Indeed we could randomly select from each “menu” at each stage of the process, so the values themselves are unpredictable but the correlations are necessarily maintained to arrive at any self-consistent string. The string is extended, not at either end, but from the middle.

Return to MathPages Main Menu