Last week, in a blog post titled Finding Patterns, I introduced a puzzle. I asked my teenager to solve it using only a pen/pencil and paper.

The Puzzle

Two integers differ by 22. Each, when multiplied by its successor, yields an eight-digit palindrome. What is the smaller of the two?

Three Steps

Using a collaborative effort between human and machine, we can achieve more, while having fun solving problems and finding new patterns. Let’s try this in three steps. Step (I) is purely human effort. Step (II) is all brute power of the machine. Step (III) is a middle ground, a collaborative effort.

Step I: Human Effort

This section features human effort alone, without the use of the internet, or a computer program. To get started, we have to translate the puzzle from English to the language of Mathematics.

Translation

• Let p and q be the two integers with q > p
• We are told p + 22 = q (p being smaller of the two)
• The successor of p is (p+1) and that of q is (q+1)
• Let the two palindromes be P = abcddcba and Q = wxyzzyxw
• Finding p is our objective

Given these facts, we can write them as math equations:

abcddcba and wxyzzyxw are the two palindromes with each letter denoting a digit — each different or with some overlap, we don’t know.

The Basics

At the risk of losing a few readers, I will try to be as accommodating as possible. If you know this already, you may skip to Spotting Patterns section.

• Integers are whole numbers, or counting numbers. Although not explicitly spelled out, this puzzle involves positive integers.

-7, -8, -67 are a few negative integers56, 117, 2938 are a few positive integers

• Palindrome is a number that reads the same forwards and backwards.

25744752, 5665, 77, 8 are integers that are palindromes

• A successor to an integer is one that follows immediately after. Referred together, the two are consecutive integers.

7 is the successor to 6.
28 is a successor to 27.

Decimal Expansion

Any integer (in base-ten system or the decimal system) can be expressed as a sum of powers of 10. For example, the decimal expansion of 5665 is

Prime Factors

Any integer can be expressed as a product of its prime factors. A prime number is divisible by 1 and itself. 2 is an even prime. The rest of them are odd.

Prime factors of 5665 are 5, 11 and 103 because 5665 = 5 x 11 x 103

Spotting Patterns

(I) Test of divisibility by 11

A test of divisibility by 11 is interesting. For any integer, reading left to right, take the sums of alternate digits in that number. You must end up with two sums.

If the sums differ by a multiple of 11, the number is divisible by 11.

EXAMPLE: Take the number 947683 for instanceAlternate digits are S = {9, 7, 8} and T = {4, 6, 3}The sum of S = 9 + 7 + 8 = 24 The sum of T = 4 + 6 + 3 = 13Their difference is (T - S) = (13 - 24) = 11 x (-1), divisible by 11Therefore 947683 is divisible by 11
In fact, 947683 = 86153 x 11

(II) Consecutive integers

Even integers are divisible by 2. Odd integers are not. Two additional interesting facts about a pair of consecutive integers are:

1) One of them is odd, and the other even. Their product is even
2) They share no prime factors. Their highest common factor is 1

(III) Perfect squares

Two consecutive integers are of the form {2k, 2k+1} where k = {0, 1, 2, 3, …} A perfect square must be of the form {(2k)², (2k+1)²} = {4k², 4k(k+1) + 1}.

A perfect square is exactly divisible by 4, OR It leaves 1 as remainder when divided by 4

(IV) Perfect square ending in 5

A curious fact about perfect squares ending in 5 is that the penultimate digit is always 2! If a number ends in 5, it’s square will always end in 25.

EXAMPLES: Say you want to find 45². The only arithmetic we need is 4x5 = 20. Then attach 25 to it. The answer is 20|25!45² = 4(4+1)| 25 = 2025 Other examples:
75² = 7(7+1)| 25 = 5625
115² = 11(12+1)| 25 = 13225(10a+5)² = 100a² + 100a + 25 = 100a(a+1) + 25

If you look at the decimal expansion of a square ending in 5, this pattern is easy to spot. Notice that no matter what ‘a’ is, the result will end in 25. Also the other digits in the number are just product of two consecutive numbers (a) (a+1) shifted left by two digits to make way for 25!

(V) Quadratic discriminant

In a quadratic equation ax²+ bx + c = 0, the discriminant (Greek symbol Delta) given by Δ= ⎷(b²- 4ac) must be a perfect square. We want the solutions of x to be whole numbers!

Δ is a perfect square for a quadratic equation with integral solutions

(VI) Palindrome with even number of digits

There are four pairs of integers that make up each palindrome. Let’s look at the decimal expansion of P for instance.

Each term is divisible by 11. Notice how each digit is paired with another identical digit in a different location such that their sum {10000001, 100001, 1001, 11} is divisible by 11. P and Q must therefore, be divisible by 11. We can extend this to any palindrome with even number of digits. Using modular arithmetic and congruence relations, we can show they are divisible by 11. It is a unique pattern!

A palindrome that has an even number of digits is divisible by 11

Detective Work

Let’s start with digits {a, w} that can assume any of the values {0,1,2,...9}. But can they? Not really, because we have some enticing clues!

Process of Elimination

Using Pattern (II), both P and Q must be even. So they must begin (and end) with the following digits {2, 4, 6, 8}. I have excluded {0} because they cannot be zero if we want the palindromes to be eight-digits long! So we have eliminated {1, 3, 5, 7, 9}. That’s a reduction by 5/9 = 55.5%, right off the bat!

{a,w} = {2, 4, 6, 8}

P = p² + p is a quadratic equation with integer solutions. Using Pattern (V), the discriminant must be a perfect square. Comparing it with ax² + bx + c = 0 we have

a = 1, b = 1, c = -P and Δ² = (b²- 4ac) = 1 + 4P

Using Pattern (III), perfect squares are exactly divisible by 4 or leave a remainder 1 when divided by 4. We also know a set of rightmost digits of P and Q. Let’s check what the rightmost digits of 1 + 4P are.

P = {2bcddcb2, 4bcddcb4, 6bcddcb6, 8bcddcb8}Δ²= 1 + 4 {2bcddcb2, 4bcddcb4, 6bcddcb6, 8bcddcb8}Δ² ends in digits {9, 7, 5, 3}There aren't any perfect squares that end in 7 or 3 because they are neither divisible by 4 nor leave a remainder 1 when divided by 4. We can apply the same logic to Q

P cannot be { 4bcddcb4, 8bcddcb8}. And Q cannot be {4xyzzyz4, 8xyzzyx4}. Using this pattern, we managed to cut the possibilities in half again!

{a,w} = {2, 6}

Since the palindrome has eight-digits, both p and q must be four-digit numbers. Starting with {a} = {6} for P, we can show {w} = {0} for Q, which is a contradiction! Let’s understand how.

Follow along using Table 1. Take row #5 for instance, where {a,w} = {6}. Two consecutive numbers (p, p+1) can end in (…2, …3) or (…7, …8) if the last digit of P is required to be 6. The leading dots denote digits we don’t yet know.

Since q = p + 22, the digit endings for (q, q+1) will either be (…4, …5) or (…9, …0). Neither of those pairs, when multiplied give us a,w = {6} for Q. Using this logic, all pairs except the rows in green can be ruled out. {a, w} cannot be {6}.

We did it again, cut the solution space in half!

When {a, w } = {2}, p ends in digits {1, 6}

{a,w} = {2} which implies the following P = 2bcddcb2 and p = { ...1, ...6 } Q = 2xyzzyx2 and q = { ...3, ...8 }

We know the largest and smallest eight-digit palindromes that begin (and end) with 2. They are bound by P(min, max) = {20000002, 29999992}. We can find out the leading (i.e, first) digit of p using an approximation that doesn’t alter its rightmost digit.

If p² + p = P, approximately p² ~ P and p ~ ⎷P

p is in the range p(min, max) = { ⎷20000002, ⎷29999992 } ~ [4500, 5500 )

I have used Pattern (IV) — technically we don’t need a calculator because 5500² =55² x 10⁴ = 30250000 and similarly 4500² = 45² x 10⁴ = 20250000

The first digit two digits of p are in this set {45, 46, 47,…, 53, 54}. Notice I have excluded 55 because 55² > 29999992 and included 45 because 45² > 20000002. We can write this more compactly:

p = {4mn1, 4mn6, 5st1, 5st6} m = {5,6,7,8,9} and s={0,1,2,3,4}

Using the Pattern (II) and (VI), {2, 11} are the prime factors of P = p (p+1) and Q = q(q+1). But p cannot have both 2 and 11 as its prime factors. That’s because they are consecutive, their highest common (prime) factor is 1. So we have to distribute {2, 11} between {p, p+1}.

Case 1: p is odd

If p is odd, 11 is its prime factor. In that case, p+1 is even and divisible by 2

p = {4mn1} m = {5,6,7,8,9} or p = {5st1} s={0,1,2,3,4}

Consider p = 45n1 {m=5}: Apply the test of divisibility by 11. n + 4 = 5 + 1, which gives us n = 2. For the rest of {m, n} and {s,t} we can tabulate possible values of p. If n > 9, we discard the number because n is a digit!

Case 2: p is even

If p is even it is divisible by 2. In that case, p+1 is odd and 11, its factor.

p = {4mn6} m = {5,6,7,8,9} or p = {5st6} s={0,1,2,3,4}

Consider p = 45n6. In this case p+1 = 45n7 is divisible by 11. n + 4 = 7+ 5, which gives us n = 8. For the rest of {m, n} and {s,t} we can tabulate possible values of p. Again, if n > 9, we discard the number because n is a digit! If p > 5470 we discard it.

Potential Suspects

Our detective work is almost complete. We are down to a short list of suspects (sixteen candidates). There could be one or more culprits that fit the pattern!

p = { 4521, 4631, 4741, 4851, 4961, 5071, 5181, 5291, 5401 }
p = { 4586, 4696, 5026, 5136, 5246, 5356, 5466 }

At this point, one could plug these numbers in a pocket calculator and check. For example, let’s test p = 4521

p = 4521
P = p(p+1) = 4521(4522) = 20443962We can save ourselves some time with long multiplication by spotting more patterns! If we multiply the last two digits 21 x 22 = 462 Similarly the first two digits 45 x 45 = 2025Notice the first two digits of P are 20, and last two are 62Since P isn't a palindrome, there is no need to check Q. We move on.

I don’t know of any other patterns. I explored prime factors, digit endings of penultimate (tens place) digits and properties of consecutive integers and palindromes. But I ran out of ideas. I am interested in any other clever ideas to reduce the solution set further! Using simple numerical patterns for integers, we managed to reduce the solution space to scan. The bar chart shows how this reduction came about. Initial count was 9000, finally we are left with 16.

The Culprit

It turns out only p = 5291, q = 5313 have this unique property where they differ by 22 and each when multiplied by it’s successor yields an eight-digit palindrome. We have finally solved the problem by finding the values of p that have this property!

p = 5291 = (11 ⨯ 13 ⨯ 37)p+1 = 5292 = (2² ⨯ 3² ⨯ 7²)P = p(p+1) = 5291(5292) = 27999972 Bingo! a palindrome ⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤q = p + 22 = 5313 = (3 ⨯ 7 ⨯ 11 ⨯ 23)q+1 = 5314 = (2 ⨯ 2657)Q = q(q+1) = 5313(5314) = 28233282 Another palindrome!

Table 4: Candidates for palindromic product. Only p = 5291, q = 5313 fit the pattern

Step II: Computing Power

In this section, we will explore the power of gigahertz clock speed! Anyone with basic coding/programming experience can appreciate the difference in speed compared to a human with a pen/paper.

I am using a MacBook with 16 GB RAM, 2.5 GHz Intel Core i7 processor.

How Many Eight-Digit Palindromes?

For curiosity’s sake, let’s find out how many eight-digit palindromes there are. The following code snippet provides the answer. It takes ~10.0 ± 0.2 s.

Answer: There are 9000 eight-digit integer palindromes

How Fast?

This is extremely slow for a simple program. Modern laptops have processing speeds that easily exceed 10 billion steps or operations every second. A CPU clock cycle is roughly 0.3 ns (less than half a nanosecond). But to appreciate how fast the machine really operates, we need something we (as humans) can relate to.

We understand and can relate to one second (One Mississippi). Let’s say we arbitrarily assign 1 CPU cycle ( 0.3 ns) to be one second.

1 CPU cycle = (0.3 ns or 0.0000000003 s) = 1 s

Given this scale, how long is 10.0 seconds it took to generate all eight-digit palindromes?

10s / 0.0000000003 = 1056 years!

We can do a lot better at generating and counting, if we know what a palindrome looks like. And we certainly do. We know half the digits (the first four or last four), we can construct the other half. Let us use this pattern to generate and count how many eight-digit palindromes are there.

P = 11000*i - 9900* (i//10) - 990 * (i//100) - 99*(i//1000)
i = [1000, ..., 9999]

Using this pattern, we can generate and count them all in 4.0 ± 0.2 milliseconds (ms) which is a significant (three orders of magnitude) improvement!

Brute Force

We can scan all eight-digit palindromes and test for this property. Let’s find out how long it takes to generate, check and find integers that have this property. The program is shown below. It takes about (7.1 ± 0.3 ms)

Step III: Collaboration

We went through the manual exercise in Step I. We managed to cut the solution space by half, in three steps. By the time we were done, we had a handful of candidates to verify. One could use any or all of the patterns to solve the problem at hand. I have chosen to start here:

p = {4mn1, 4mn6, 5st1, 5st6} m = {5,6,7,8,9} and s={0,1,2,3,4}

Let’s code this and find out how long it takes! The code snippet is shown below. It takes (55.6 ± 9 μs) which is a thousand-fold reduction!

Now let’s compare how fast the execution is in human relatable time. Let’s recall we started with 1056 years to list all the eight-digit palindromes. If we calculate how long, we get about 2 days! That’s a remarkable reduction which went unnoticed. As humans it is hard to wrap our heads around both large and small numbers.

56 μs ~ 2 days

Collaborate, Create

Humans and machines are both powerful entities. We have evolved the capability to solve complex problems with our pattern recognition skills, capacity for abstract thought, and creative talents. If we collaborate with the machine to utilize its super-human strength and intelligence, the human-computer collaboration would make a winning combination!

References

1. Some Problems on the Prime Factors of Integers — P. Erdös, L. Selfridge, Illinois J. Math., Volume 11, Issue 3 (1967), 428–430. Link to PDF
2. Divisibility by Eleven — Mudd Math Fun Facts
3. Positive numbers k such that k*(k+1) is a palindrome. A028336 — OEIS, Patrick De Geest
4. Problem originally appeared in Mindsport, Sunday Times of India, By Mukul Sharma, Early 1990's
5. The rise of human-computer cooperation, TED Talk 2012, Shyam Sankar
6. Coding Horror blog post: The infinite space between words, 2014, Jeff Atwood

©️ Venkat Kaushik 2020. All Rights Reserved.