On Polynomial Pairs of Integers

Martianus Frederic Ezerman Division of Mathematical Sciences School of Physical and Mathematical Sciences Nanyang Technological University 21 Nanyang Link Singapore 637371

                fredezerman@ntu.edu.sg

Bertrand Meyer and Patrick Solé Telecom ParisTech 46 rue Barrault 75634 Paris Cedex 13 France

                     meyer@enst.fr
                     sole@enst.fr

Abstract

The reversal of a positive integer A is the number obtained by reading A backwards in its decimal representation. A pair (A, B) of positive integers is said to be palindromic if the reversal of the product A × B is equal to the product of the reversals of A and B. A pair (A, B) of positive integers is said to be polynomial if the product A × B can be performed without carry.

In this paper, we use polynomial pairs in constructing and in studying the properties of palindromic pairs. It is shown that polynomial pairs are always palindromic. It is further conjectured that, provided that neither A nor B is itself a palindrome, all palindromic pairs are polynomial. A connection is made with classical topics in recreational mathematics such as reversal multiplication, palindromic squares, and repunits.

1 Introduction

On March 13, 2012 the following identity appeared on K. T. Arasu’s Facebook posting^{1}:

Notice that

25986 = 213 × 122.

Now, read the expression above in reverse order and observe that

221 × 312 = 68952.

The point here is, of course, that the second equality still holds in first order arithmetic! For A ∈ ℕ let the reversal of A, denoted by A^{∗}, be the integer obtained by reading A

backwards in base 10. We say that A is a palindrome if A = A^{∗}. In this paper, we investigate how to determine which pairs (A, B) of positive integers satisfy the property

C = A × B and C^{∗} = A^{∗} × B^{∗}.  (1)

In words, the product of the reversals is the reversal of the product. We shall call such a pair a palindromic pair.

Note that there are integers C with more than one corresponding pair (A, B) satisfying Eq. (1). For example, we have

2448 = 12 × 204 = 24 × 102.

Upon reversal, one has

8442 = 21 × 402 = 42 × 201.

It is easy to see that palindromic pairs always occur in distinct pairs (A, B) and (A^{∗}, B^{∗}) unless both A and B are palindromes. The pair (12, 13), for instance, comes with the pair (21, 31) upon reversal.

The question of how to characterize palindromic pairs had appeared in Ball and Coxeter [1, p. 14] where the pair (122, 213) was given, yet this matter has hardly been looked at more closely. In this short note we introduce the notion of polynomial pairs as a tool to study palindromic pairs. We show that all the examples of palindromic pairs presented below can be explained in terms of polynomial pairs. We conjecture, but cannot yet prove that, when neither A nor B is a palindrome, all palindromic pairs (A, B) are polynomial pairs.

The concept of polynomial pairs intersects many classical topics in recreational mathematics. An interesting topic concerns the repunits which are numbers all of whose digits are 1 [2, Ch. 11]. Another topic deals with a known technique to produce palindromes usually referred to as reversal multiplication [4]. The integers A with the property that A × A^{∗} is a palindrome form sequence \underline{A062936} in the Online Encyclopedia of Integer Sequences (henceforth, OEIS) [3]. Whenever (A, A^{∗}) form a polynomial pair, we learn that reversal multiplication always produces a palindrome.

1His account has since been deactivated for personal reasons.

The material is arranged as follows. Section 2 introduces, and Section 3 develops, the concept of palindromic pairs. Section 4 explores the multiplicity of the representation of a repunit as a product of a palindromic pair of integers. Section 5 covers the special case where the two members of a palindromic pair are reversals of each other. Section 6 is dedicated to palindromes that are perfect squares. Section 7 replaces multiplication by addition in the definition of a palindromic pair. The paper ends with a summary.

2 Formalization

To formalize the problem mathematically, some notation is in order. Let

A := ∑_{i=0}^{a} a_{i}10^{i}

be an integer expressed in base 10. Its reversal is

A^{∗} := ∑_{i=0}^{a} a_{i}10^{a−i}.

Define the polynomial P (A, x) := ∑_{i=0}^{a} a_{i}x^{i} ∈ ℚ[x] so that P (A, 10) = A. Then its reciprocal

P^{∗}(A, x) := ∑_{i=0}^{a} a_{i}x^{a−i} = x^{a}P (A, 1/x)

satisfies P^{∗}(A, 10) = A^{∗}. A pair (A, B) of not necessarily distinct positive integers is said to be a palindromic pair if

P^{∗}(A, 10)P^{∗}(B, 10) = P^{∗}(A × B, 10).

We shall say that the pair (A, B) is polynomial if

P (A, x)P (B, x) = P (A × B, x).

The pair (12, 21), for instance, is a polynomial pair since

P (12 × 21, x) = 2x^{2} + 5x + 2 = (x + 2)(2x + 1),

but (13, 15) is not a polynomial pair because

(x + 3)(x + 5) = x^{2} + 8x + 15 while P (13 × 15, x) = x^{2} + 9x + 5.

The following characterization of polynomial pairs will be used repeatedly.

Proposition 1. The following assertions are equivalent.

1) (A, B) is a polynomial pair.

2) The multiplication of A by B can be performed without carry.

3) The coefficients of the polynomial P (A, x)P (B, x) are bounded above by 9.

Proof. Let j be the smallest integer such that c_{j} := ∑_{j=i+k} a_{i}b_{k} > 9. Then c_{j} is the coefficient of x^{j} in P (A, x)P (B, x), while the coefficient of x^{j} in P (A×B, x) is c_{j} (mod 10) ≠ c_{j}. Thus,

1) implies 2) by contrapositive argument.

Now, assume that there is some j such that c_{j} := ∑_{j=i+k} a_{i}b_{k} > 9. Then, in the multiplication A × B, the term y := ⌊\frac{c_{j}}{10}⌋ is carried over to the coefficient of 10^{j+1}. This establishes that 2) implies 3).

Lastly, to show that 3) implies 1), we begin by substituting x = 10. Hence,

A × B = P (A, 10)P (B, 10) = ∑_{k=0}^{a+b} ( ∑_{i+j=k} a_{i}b_{j}) 10^{k}.

The coefficient of x^{k} in P (A × B, x) is ∑_{k=i+j} a_{i}b_{j}, which is assumed to be ≤ 9. This means that (A, B) is indeed a polynomial pair. The proof is therefore complete.

Polynomial pairs are palindromic pairs as the next result shows.

Proposition 2. A polynomial pair (A, B) is palindromic.

Proof. If P (A, x)P (B, x) = P (A × B, x), then, by taking reciprocals, we get

P^{∗}(A, x)P^{∗}(B, x) = P^{∗}(A × B, x).

Using x = 10 completes the proof.

This observation raises an initial question:

Problem 3. Are there palindromic pairs that are not polynomial?

Our investigation quickly reveals that the answer is yes. If we allow either A or B to be palindromes then there are palindromic pairs which are not polynomial pairs.

The test that a pair (A, B) is palindromic is done simply by checking if the definition is satisfied. We record A, B, and C whenever we have A × B = C and A^{∗} × B^{∗} = C^{∗}. We then perform a check if the multiplication of A by B can be performed without carry. The pair (A, B) that fails to pass this check is not a polynomial pair by Proposition 1. Table 1 provides the list of all such pairs (A, B) with A ≤ B and A × B = C ≤ 10^{7} generated by exhaustive search. We require A ≤ B to avoid duplication of pairing.

Table 1: Palindromic but not polynomial pairs (A, B) with A ≤ B and A × B ≤ 10^{7}

(A, B) A × B (A, B) A × B (A, B) A × B (A, B) A × B
(7, 88)  616 (555, 979) 543345 (737, 888) 654456 (707, 8558) 6050506
(8, 77)  (55, 9999) 549945 (777, 858) 666666 (7, 880088) 6160616
(55, 99) 5445 (99, 5555)  (969, 5335) 5169615 (8, 770077)
(7, 858) 6006 (707, 858) 606606 (575, 9119) 5243425 (77, 80008)
(77, 88) 6776 (7, 88088) 616616 (979, 5555)  (88, 70007)
(55, 999) 54945 (8, 77077)  (55, 99999) 5499945 (77, 80088) 6166776
(99, 555) (77, 8008) (99, 55555) (88, 70077)
(77, 858) 66066 (88, 7007)  (7, 858088) 6006616 (898, 7227) 6489846

In addition to providing a positive answer to Problem 3, the table reveals some interesting facts. Except for the two values of C printed in boldface, all other Cs are themselves palindromes in which case both A and B are palindromes. The pairs (7, 858088), yielding C = 6006616, and (77, 80088) and (88, 70077), giving C = 6166776, contain a palindrome A. On the other hand, up to C ≤ 10^{7}, no palindromic pairs were found, with neither A nor B being a palindrome, that was not polynomial. Computational evidence strongly suggests the following conjecture.

Conjecture 4. If (A, B) is a palindromic pair, with neither A nor B a palindrome, then (A, B) is a polynomial pair.

In attempting to answer the conjecture, we begin by establishing properties of polynomial pairs in the next section.

3 Some properties of polynomial pairs

For A ∈ ℕ, let A_{∞} denote the maximum of the coefficients of P (A, x).

Proposition 5. If (A, B) is a polynomial pair, then A_{∞}B_{∞} ≤ 9. If, moreover, A_{∞} ≥ 5, then B_{∞} = 1.

Proof. This proposition is a direct consequence of Proposition 1. Let j and l be, respectively, the smallest index such that a_{j} = A_{∞} and b_{l} = B_{∞}. Then A_{∞}B_{∞} > 9 would imply that the coefficient of x^{j+l} in the multiplication P (A, x)P (B, x) is > 9, violating Proposition 1 Part 3).

To derive a sufficient condition for (A, B) to be a palindromic pair we define the norm of an integer by the formula A_{1} = P (A, 1).

Proposition 6. For A, B ∈ ℕ, (AB)_{∞} ≤ A_{∞}B_{1}.

Proof. Write P (A, x) = ∑_{i=0}^{a} a_{i}x^{i}, and P (B, x) = ∑_{i=0}^{b} b_{i}x^{i}. Then, the coefficient of x^{k} in P (AB, x) is

∑_{i+j=k} a_{i}b_{j} ≤ A_{∞} ∑_{j=0}^{b} b_{j} = A_{∞}B_{1}.

A construction of polynomial pairs can be deduced from Proposition 6.

Proposition 7. Let A, B ∈ ℕ with A_{∞}B_{1} ≤ 9. Then (A, B) is a polynomial pair.

Proof. Combine Proposition 1 Part 3) and Proposition 6.

Table 2 list downs all polynomial pairs (A, B) with A×B = C, A ≤ B, and C ≤ C^{∗} ≤ 10^{4}. Neither A = A^{∗} nor B = B^{∗} is allowed although C = C^{∗} is allowed. For each pair, there is a corresponding pair (A^{∗}, B^{∗}) with A^{∗} × B^{∗} = C^{∗}. When C is a palindrome, it is written in bold.

Table 2: The list of polynomial pairs (A, B) with A ≤ B, neither A = A^{∗} nor B = B^{∗} is allowed, and A × B = C ≤ C^{∗} ≤ 10^{4}

C (A, B) C (A, B) C (A, B) C (A, B) C (A, B)
144 (12, 12) 1356 (12, 113) 2352 (21, 112)  (24, 112) 3624 (12, 302)
156 (12, 13) 1368 (12, 114) 2369 (23, 103) 2743 (13, 211) 3648 (12, 304)
168 (12, 14) 1428 (14, 102) 2373 (21, 113) 2769 (13, 213) 3744 (12, 312)
169 (13, 13) 1456 (13, 112) 2394 (21, 114) 2772 (12, 231) 3768 (12, 314)
252 (12, 21) 1464 (12, 122) 2436 (12, 203)  (21, 132) 3864 (12, 322)
273 (13, 21) 1469 (13, 113) 2448 (12, 204) 2793 (21, 133) 3888 (12, 324)
276 (12, 23) 1476 (12, 123)  (24, 102) 2796 (12, 233) 3926 (13, 302)
288 (12, 24) 1488 (12, 124) 2556 (12, 213) 2814 (14, 201) 3984 (12, 332)
294 (14, 21) 1568 (14, 112) 2562 (21, 122) 2873 (13, 221) 4284 (21, 204)
299 (13, 23) 1584 (12, 132) 2568 (12, 214) 2892 (12, 241)  (42, 102)
384 (12, 32) 1586 (13, 122) 2576 (23, 112) 2899 (13, 223) 4386 (43, 102)
1224 (12, 102) 1596 (12, 133) 2583 (21, 123) 2954 (14, 211) 4494 (21, 214)
1236 (12, 103) 1599 (13, 123) 2599 (23, 113) 3193 (31, 103) 4669 (23, 203)
1248 (12, 104) 2142 (21, 102) 2613 (13, 201) 3264 (32, 102) 4836 (12, 403)
1326 (13, 102) 2163 (21, 103) 2639 (13, 203) 3296 (32, 103) 4899 (23, 213)
1339 (13, 103) 2184 (21, 104) 2676 (12, 223) 3468 (34, 102) 4956 (12, 413)
1344 (12, 112) 2346 (23, 102) 2688 (12, 224) 3584 (32, 112) 6496 (32, 203)

4 Integers with many polynomial pairs

From Tables 1 and 2 we notice that some C ∈ ℕ can be the product of the elements of distinct polynomial pairs. Here we give a construction to show that some numbers can be the product of the elements of an arbitrarily large number of distinct polynomial pairs.

First, let us define a repunit R(n) as the n-digit number whose digits are ones. The term, which abbreviates repeated unit, first appeared in Beiler [2, Ch. 11]. More formally,

R(n) = ∑_{i=0}^{n−1} 10^{i} = \frac{10^{n} − 1}{9}.

Sequence \underline{A004023} in the OEIS [3] records the known values of n for which R(n) is prime.

Theorem 8. The repunit R(2^{n}) is the product of n pairwise distinct positive integers. It can be expressed as the product A × B of 2^{n−1} − 1 pairwise distinct polynomial pairs (A, B).

Proof. It is clear that R(2) = 10^{1} + 1 and R(4) = R(2)(100 + 1) = (10^{1} + 1)(10^{2} + 1). Using the difference of squares, we can inductively write

R(2^{n}) = \frac{1}{9}(10^{2^{n}} − 1) = \frac{1}{9}(10^{2^{n−1}} − 1)(10^{2^{n−1}} + 1) = R(2^{n−1})(10^{2^{n−1}} + 1) = ∏_{i=0}^{n−1}(10^{2^{i}} + 1).

This establishes the first assertion. Moreover, all of the multiplications can be performed without carry since R(a)_{∞} = 1, for all integers a ≥ 1.

Since there are n distinct factors, we can group them into two disjoint nontrivial sets A and B. Let A be the product of the elements in A. Let B be defined analogously based on B. Since we want to avoid repetition, two cases based on the parity of n need to be considered.

When n = 2k + 1, the set A has j elements with 1 ≤ j ≤ k = (n − 1)/2. The remaining n − j elements not chosen for A automatically form the set B. Thus, there are ∑_{j=1}^{k} \binom{n}{j} = 2^{n−1} − 1 pairwise distinct pairs (A, B).

When n = 2k, we can do similarly for 1 ≤ |A| ≤ k − 1 but we need to treat the case of |A| = |B| = k with more care. To avoid forming repetitive pairs, we halve the count. In total, the number of pairwise distinct pairs (A, B) formed is ∑_{j=1}^{k−1} \binom{n}{j}+ \frac{1}{2} \binom{n}{k} = 2^{n−1} −1.

5 Reversal multiplication

A popular way to obtain palindromes is to multiply a number by its reversal. This is called reversal multiplication in [4] and the numbers that give palindromes in that way form Sequence \underline{A062936} in the OEIS [3]. This recipe always works with polynomial pairs as the next result shows.

Proposition 9. If (A, A^{∗}) is a polynomial pair, then A × A^{∗} is always a palindrome.

Proof. It suffices to confirm that P (A^{∗}, x) = P^{∗}(A, x) and that P (A, x)P^{∗}(A, x) is a selfreciprocal polynomial.

De Geest [4] observes that all elements > 3 in sequence \underline{A062936} have only the digits 0, 1, and 2. This is easy to show in the polynomial pair case, and correlates with an observation made by David Wilson \underline{A062936} on July 6, 2001 stating that said sequence includes positive integers not ending in 0 whose sum of squares of the digits is ≤ 9.

Proposition 10. If (A, A^{∗}) is a polynomial pair, then the sum of the squares of the digits of A is ≤ 9. In particular, if A > 9, we have A_{∞} ≤ 2. Conversely, if the sum of the squares of the digits of A is ≤ 9, then (A, A^{∗}) is a polynomial pair.

Proof. Write P (A, x) = ∑_{i=0}^{d} a_{i}x^{i}. By the Cauchy-Schwarz inequality, for 0 ≤ k ≤ d,

∑_{l=0}^{k} a_{l}a_{d−k+l} ≤ ∑_{i=0}^{d} a_{i}^{2}.

The left-hand side is the coefficient of x^{k} while the right-hand side is the coefficient of x^{d} in P (A × A^{∗}, x). Thus, by Proposition 9, we have

(A × A^{∗})_{∞} = ∑_{i=0}^{d} a_{i}^{2},  (2)

which is the sum of the squares of the digits of A. This establishes the first statement from which follows that if A has at least two nonzero digits, then none can be ≥ 3.

The converse follows from Eq. (2) and Proposition 1.

We have generated a list of elements A < 10^{9} of sequence \underline{A062936} and verified that the sum of the squares of the digits of A is bounded above by 9. Applying the converse part of Proposition 10, we are led to the following conjecture.

Conjecture 11. If A × A^{∗} is a palindrome, then (A, A^{∗}) is a polynomial pair.

To emphasize that we make Conjecture 11 for base b = 10 only, we observe the following counterexamples for b ≠ 10.

In base 2, we have 11 × 11 = 1001. More generally, for any integer l ≥ 2,

11 \overbrace{00 ⋯ 0}^{2l} 10101 \overbrace{00 ⋯ 0}^{2l−1} 11 × 11 \overbrace{00 ⋯ 0}^{2l−1} 10101 \overbrace{00 ⋯ 0}^{2l} 11

= 1001 × 2^{8l+12} + 10111101 × 2^{6l+7} + 1001001001 × 2^{4l+3} + 10111101 × 2^{2l+1} + 1001, (3)

which can be seen to be a palindrome. Using 2l + 1, instead of 2l − 1, also works. Our computation reveals that there are no other counterexamples with A having less than 20digit base 2 representation.

In base 4, the only counterexample with A having less than 10-digit representation is 2232213 × 3122322 = 21111033011112. The next counter example, if exists, must be a considerably large number.

Table 3 gives the counterexamples we found for base b ∈ {3, 4, 5, 7, 8, 9, 11}. We have not been able to find counterexamples in either base 6 or base 10.

Table 3: Examples of A and A × A^{∗} where (A, A^{∗}) is not a polynomial pair for A ≤ A^{∗} in bases b ∈ {3, 4, 5, 7, 8, 9, 11}. In base 11, a stands for 10

Base  A  A × A^{∗}  Base  A  A × A^{∗}
3  2  11  8  47  4444
202  112211  303  112211
2002  11022011  306  225522
20002  1100220011  333  135531
200002  110002200011  3003  11022011
201102  111221122111  3006  22055022
2000002  11000022000011  3033  12244221
20000002  1100000220000011  3116  23300332
20011002  1101211111121011  3306  24377342
200000002 110000002200000011  3333  13577531
2000000002 11000000022000000011  30003  1100220011
2000110002 11001210111101210011  30006  2200550022
4  2232213  21111033011112  30033  1211441121
5  314  242242  30303  1122332211
22033  1334334331  9  516  350053
220033  133133331331  44055  2667557662
2200033  13310333301331  440055 266255552662
2301123  14000211200041  2403555 14682744728641
22000033  1331003333001331  4400055 26620555502662
23410123  1423123003213241  11  6  33
24200303  1344343003434431  66  3993
7  4  22  77  5335
44  2662  374  161161
55  4444  419  350053
404  224422  606  336633
4004  22044022  6006  33066033
4114  23300332  21896  139a00a931
25124  1456446541  33088  1669999662
40004  2200440022  60006  3300660033
400404  222426624222  60606  3366996633
403304  223652256322  63328  4779559774
404004  222426624222  283306 156695596651
4000004  22000044000022  330088 266279972662
8  3  11  391744 15a484484a51
6  44  441739 379373373973
33  1331  600006 330006600033
36  2772  600606 333639936333

Proposition 12. There are infinitely many values of b for which the analogue of Conjecture 11 in base b is false.

Proof. First, consider the base b such that b = r^{2} − 1 for 2 ≤ r ∈ ℕ. Writing in base b, r × r = 11, and for any non-negative integer j,

r \overbrace{00 ⋯ 0}^{j+1} r × r \overbrace{00 ⋯ 0}^{j+1} r = (r × b^{j+2} + r)^{2} = (r^{2} × b^{2j+4}) + (2 × r^{2} × b^{j+2}) + r^{2}

= 11 \overbrace{00 ⋯ 0}^{j} 22 \overbrace{00 ⋯ 0}^{j} 11.

There are obviously infinitely many such bases b.

For any base b of the form b = 4k − 1,

(2k) × (2k) = 4k^{2} = (k × b) + k = kk  (4)

in base b. More generally, in the said base, one can easily verify, by using Eq. (4), that

((2k) \overbrace{00 ⋯ 0}^{j+1}(2k))^{2} = ((2k × b^{j+2}) + 2k)^{2} = (4k^{2} × b^{2j+4}) + (2 × 4k^{2} × b^{j+2}) + 4k^{2}

= kk \overbrace{00 ⋯ 0}^{j}(2k)(2k) \overbrace{00 ⋯ 0}^{j} kk.

When the base b is of the form b = 4k + 1, we can write

(2k) × (2k + 1) = k × (4k + 1) + k = (k × b) + k = kk.  (5)

Using Eq. (5), one gets

[(2k)(2k)00(2k + 1)(2k + 1)] × [(2k + 1)(2k + 1)00(2k)(2k)] = [b^{4} × 2k × (b + 1) + (2k + 1) × (b + 1)] × [b^{4} × (2k + 1) × (b + 1) + 2k × (b + 1)] = kk + [(2k)(2k) × b] + [kk × b^{2}] + [(2k)(2k + 1) × b^{4}] + [101 × b^{5}] + [(2k)(2k + 1) × b^{6}] + [kk × b^{8}] + [(2k)(2k) × b^{9}] + [kk × b^{10}] = k(3k)(3k)k(2k + 1)(2k + 1)(2k + 1)(2k + 1)k(3k)(3k)k.

In fact, one can obtain a slightly more general result since, for any non-negative integer j,

(2k)(2k) \overbrace{00 ⋯ 0}^{j+2}(2k + 1)(2k + 1) × (2k + 1)(2k + 1) \overbrace{00 ⋯ 0}^{j+2}(2k)(2k)

= k(3k)(3k)k \overbrace{00 ⋯ 0}^{j}(2k + 1)(2k + 1)(2k + 1)(2k + 1) \overbrace{00 ⋯ 0}^{j} k(3k)(3k)k.

Thus, a necessary but insufficient condition for the analogue of Conjecture 11 in base b to hold is for b to be even and for b + 1 to be square-free.

Remark 13. Let (A, B) be a palindromic pair. If either A or B is itself a palindrome, then we cannot conclude immediately that (A, B) is a polynomial pair. Indeed, in many cases, for example, when A = 121 and B = A^{∗} = A, the pair (A, B) is both palindromic and polynomial. Yet, as shown by the pairs listed in Table 1, a palindromic pair may fail to be polynomial when either A or B is a palindrome.

Conjecture 11 posits that, regardless of whether A itself is a palindrome, so long as A × A^{∗} is a palindrome, then (A, A^{∗}) is polynomial. Thus, this conjecture does not follow from Conjecture 4. If, however, we add the condition that A ≠ A^{∗}, then a positive answer to Conjecture 4 settles this modified version of Conjecture 11 since, if A × A^{∗} is a palindrome, then (A, A^{∗}) is of course a palindromic pair.

Note that Proposition 12 still holds if we use the base b analogue for the modified version of Conjecture 11 using only bases b = 4k + 1 in the proof. In this case, removing all entries in Table 3 having A = A^{∗} provides analogous examples.

To end this section we prove a special case of Conjecture 11.

Proposition 14. If A is an n−digit number and A × A^{∗} is a (2n − 1)-digit palindrome then (A, A^{∗}) is a polynomial pair.

Proof. Let A be an n-digit number such that A×A^{∗} is a (2n−1)-digits palindrome, with the notation P (A, x) = ∑_{i=0}^{n−1} a_{i}x^{i}. Let c_{0}, c_{1}, …, c_{2n−2} be the digits of A × A^{∗}. We now make completely explicit how the digits are manipulated when the multiplication is performed.

Let γ_{i} be the carry that is propagated on the i-th digits and σ_{i} be the sum of the products of digits that appear in the i-th position. Hence,

γ_{0} = 0

and, for all 0 ≤ i ≤ 2n − 1,

σ_{i} = γ_{i} + ∑_{k=max(0,i+1−n)}^{min(n−1,i)} a_{k} a_{n−1−i+k},
c_{i} = σ_{i} (mod 10),
γ_{i+1} = (σ_{i} − c_{i})/10.

Note that (A, A^{∗}) is a polynomial pair if and only if γ_{i} = 0 for all i ≤ 2n − 1. We prove this fact by induction.

Since A × A^{∗} has only 2n − 1 digits, we have c_{2n−1} = 0, and thus γ_{2n−1} = 0. Suppose that for a certain integer ℓ we have proven that γ_{ℓ} = 0 and γ_{2n−ℓ−1} = 0. Since γ_{2n−ℓ−1} = 0, we must have

σ_{2n−ℓ−2} = c_{2n−ℓ−2} ≤ 9.

Now,

σ_{ℓ} = σ_{2n−2−ℓ} − γ_{2n−ℓ−2} + γ_{ℓ} = σ_{2n−ℓ−2} − γ_{2n−ℓ−2}

must be ≤ 9 too. So γ_{ℓ+1} = 0 and c_{ℓ} = σ_{ℓ}. Since A×A^{∗} is a palindrome, we have c_{ℓ} = c_{2n−ℓ−2}. So we also have σ_{2n−ℓ−2} = σ_{ℓ}. Now we can compute that

γ_{2n−ℓ−2} = σ_{2n−ℓ−2} − σ_{ℓ} + γ_{ℓ} = 0,

which concludes the induction step.

6 Squares and palindromes

In this short section we show that some results established above shed light on several connections between palindromes and squares.

There are two sequences in the OEIS [3] concerning palindromes and squares. Sequence \underline{A002779} lists palindromic perfect squares, while sequence \underline{A002778} contains integers whose squares are palindromes. The next result, which is a direct consequence of Proposition 9, gives a sufficient but not a necessary condition for an integer A to belong to sequence \underline{A002778}.

Proposition 15. If (A, A) is a polynomial pair with A a palindrome, then A^{2} is a palindrome.

Each entry of sequence \underline{A156317} in the OEIS [3] is a perfect square that forms either an equal or a larger perfect square when reversed. Here is a technique to produce examples of such integers.

Proposition 16. If (A, A) is a polynomial pair then so is (A^{∗}, A^{∗}). Moreover, (A^{2})^{∗} = (A^{∗})^{2}.

Proof. It suffices to verify that P ((A^{2})^{∗}, x) = P^{∗}(A^{2}, x) = (P^{∗}(A, x))^{2} = (P (A^{∗}, x))^{2}.

7 Additive pairs

It is natural to consider as well the additive analogue of polynomial pairs. The pair (A, B) of positive integers is said to be an additive pair if

P (A, x) + P (B, x) = P (A + B, x).

The counterpart of Proposition 1 can then be established.

Proposition 17. The following assertions are equivalent.

1) The pair (A, B) is an additive pair.

2) The addition of A by B can be performed without carry.

3) The coefficients of the polynomial P (A, x) + P (B, x) are bounded above by 9.

Proof. We use the same representation of P (A, x) and P (B, x) as in the proof of Proposition 6. Let j be the smallest integer such that c_{j} = a_{j} + b_{j} > 9. Then c_{j} is the coefficient of x^{j} in P (A, x) + P (B, x) while c_{j} (mod 10) ≠ c_{j} is the coefficient of x^{j} in P (A + B, x). By contrapositive argument, 1) implies 2).

It is clear by definition of polynomial addition that 2) implies 3). To verify that 3) implies 1) note that for 0 ≤ j ≤ max(a, b) we have c_{j} = a_{j} + b_{j} ≤ 9, which leads immediately to the desired conclusion since c_{j} is the coefficient of x^{j} in both P (A + B, x) and P (A, x) + P (B, x).

A sufficient condition for (A, B) to be an additive pair is A_{∞} + B_{∞} ≤ 9. Additive pairs can be used to generates palindromes.

Proposition 18. If (A, A^{∗}) is an additive pair, then A + A^{∗} is a palindrome.

Proof. It is straightforward to verify that P (A^{∗}, x) = P^{∗}(A, x) and that P (A + A^{∗}, x) = P (A, x) + P^{∗}(A, x) is a self-reciprocal polynomial.

There are, however, integers A such that A + A^{∗} is a palindrome yet (A, A^{∗}) is not an additive pair. The numbers 56 and 506 are some easy examples of such A.

8 Summary

In this note we have shown how to use polynomial pairs to study the properties of palindromic pairs. Furthermore, a large number of palindromic pairs can be constructed by using polynomial pairs. Connections to well-known numbers and integer sequences in the OEIS have also been explicated.

It is of interest to either find counterexamples to or to prove the validity of the conjectures mentioned here for future investigations. As an added incentive, we offer a ripe durian for a correct proof of, or a valid counterexample to, any of the conjectures.

9 Acknowledgment

The authors thank Abdul Qatawneh for helpful discussions, and the anonymous referees for their comments and suggestions.

References

[1] W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 2007.

[2] A. H. Beiler, Recreations in the Theory of Numbers: The Queen of Mathematics Entertains, Dover, 1966.

[3] N. J. A. Sloane, The online encyclopedia of integer sequences, 2015. Available at

   http://oeis.org.

[4] P. de Geest, Palindromic products of integers and their reversals,

   http://www.worldofnumbers.com/reversal.htm.

2010 Mathematics Subject Classification: Primary 11B75; Secondary 97A20. Keywords: number reversal, palindrome, palindromic pair, polynomial pair, repunit.

(Concerned with sequences \underline{A002778}, \underline{A002779}, \underline{A004023}, \underline{A062936}, and \underline{A156317}.)

Received October 29 2012; revised version received August 5 2014; February 14 2015. Published in Journal of Integer Sequences, February 14 2015.

Return to Journal of Integer Sequences home page.