Using math to determine if a number is a palindrome

Palindromes are common topic when it comes to questions or exercises in computer science. For instance, they can be found in several exercises of Project Euler.

In the English language, palindromes are used to define both symmetrical words and numbers. However, this post will focus on numbers only.

Using stringified numbers

String manipulation is very convenient when checking properties such as this. So, the most common approach is to stringify the number first.

Some languages, such as Python, are particularly flexible and allow the check to be as short as:

def is_string_palindrome(input_string):
	return input_string == input_string[::-1]

def is_number_palindrome(number):
	return is_string_palindrome(str(number))

Other languages, like C++, require a bit more of manual work. A solution would be to traverse the strings from both ends until meeting at the middle.

bool IsPalindrome(const String& s)
{
	for (int i = 0; i < s.length() / 2; ++i)
    {
    	if (s[i] != s[s.length() - 1 - i])
        	return false;
    }
    return true;
}

While using strings certainly eases the problem, allocating them is an expensive operation. There is a cheaper way to compute this.

It is possible, using math, to come to the very same conclusion in a CPU-friendly way. The approach is the same: we need to compare the nth-first and nth-last digits of the number. If they are different, the number is not a palindrome. If we run out of digits to check, we can guarantee that it is.

Defining numeric palindromes mathematically

We can define the function \( IsPalindrome(x) \) as:

\[ IsPalindrome(x) = \begin{cases} IsPalindrome(\lvert x \rvert) & \text{if x < 0}\\ True & \text{if x < 10}\\ IsPalindrome(Middle(x)) & \text{if FirstDigit(x) = LastDigit(x)}\\ False & \text{otherwise} \end{cases} \]

The first case is to allow negative numbers to be taken into account. The second is the base case of this recursive function: single-digit numbers are, by nature, symmetric.

We still need to define the other functions used by the recursive case. For reference, \( FirstDigit(x) \) and \( LastDigit(x) \) refer to the left-most and right-most digit of \( x \), respectively.

First digit of a number

Getting the left-most digit of a number is just a matter of either:

  • Looping, dividing the number by 10 each time, until the result is less than 10.
  • Dividing the number by the closest power of 10 below the number.

This is possible because dividing a number by its base results in its radix point (decimal point for base 10) moving one digit to the left. This can be generalised for any number of digits: moving it \( N \) number of places to the left is equal to dividing the number by \( 10^N \).

For instance, \( \frac{999}{10} = 99.9 \approx 9 \) and \( \frac{238}{100} = 2.38 \approx 2 \) .

In the case of the second approach, we can use the logarithm base 10 to determine the number of digits the number is made up of. In other words, its length.

\[ Length(x) = \lfloor \log_{10}(x)\rfloor + 1 \]

The reason why we use \( \lfloor \log_{10}(x)\rfloor + 1 \) instead of \( \lceil \log_{10}(x)\rceil \) is because \( \log_{10}(1) = 0\). If we try to calculate the ceiling of it, it'll stay as \( 0 \) instead of being rounded-up to \( 1 \).

With that in mind, it is possible to get the first digit with:

\[ FirstDigit(x) = \biggl\lfloor \frac{x}{10^{Length(x) - 1}} \biggr\rfloor \]

Last digit of a number

The process is analogue to the left-most digit. In this case, however, we use the remainder of the division instead of the division itself. This is a job for \( \bmod \).

Since we only care about the last digit and not the last \( N \) digits, is suffices to do this:

\[ LastDigit(x) = x \bmod 10  \]

Middle part of a number

The middle is the number without its first and last digits.

Unfortunately, this works if the middle doesn't contain any leading zeroes. If it does, then it'll be malformed for our purposes. For example: the middle of \( 10101 \) should be \( 010 \) but it is \( 10 \) instead because leading zeroes are ignored.

This problem is solved by removing any trailing digits as well. In the case of a palindrome, if those trailing digits aren't zeroes then we can rest assured that it isn't really a palindrome.

For simplicity purposes, let's focus on numbers that don't contain zeroes. We can get rid of the first digit by subtraction and then the last digit by division.

\[ Middle(x) = \frac{x - (FirstDigit(x) * 10^{Length(x) - 1})}{10} \]

For example, the middle segment of \( 321123 \) is:

\[ \begin{aligned} Middle(321123)&=\biggl\lfloor \frac{321123 - (FirstDigit(321123) * 10^{Length(321123) - 1})}{10}\biggr\rfloor \\ &=\biggl\lfloor \frac{321123 - (3 * 10^{5})}{10}\biggr\rfloor \\ &=\biggl\lfloor \frac{321123 - 300000}{10}\biggr\rfloor \\ &=\biggl\lfloor \frac{21123}{10}\biggr\rfloor \\ &=\lfloor 2112.3 \rfloor \\ &= 2112 \end{aligned} \]


Putting it all together

With all these in mind, it is possible to create an algorithm that detects if a number is a palindrome.

Note two things about this code:

  1. It handles numbers containing zeroes.
  2. It uses recursions. However, with a few changes here and there, it is possible to achieve the same with a loop.
from math import floor, log10

def get_length(number):
    # We need to use `floor(...) + 1` instead of just `ceil(...)` because
    # it breaks for 1: ceil(log10(1)) = ceil(0.0) = 0
    return floor(log10(number)) + 1

def is_palindrome(number):
    if (number < 10):
        return (number >= 0) or is_palindrome(abs(number))

    full_length = get_length(number)
    closest_power_of_10 = 10**(full_length - 1)

    leftmost_digit = number // closest_power_of_10
    rightmost_digit = number % 10

    if (leftmost_digit != rightmost_digit):
        return False

    middle = (number - (leftmost_digit * closest_power_of_10)) // 10

    if (middle != 0):
        # After removing the leading digit, we may have 1 or more zeroes.
        # Because leading zeroes are ignored, the middle value will be malformed
        # for furture checks.
        expected_length = full_length - 2
        actual_length = get_length(middle)
        if (expected_length > 0 and actual_length != expected_length):
            number_of_zeroes = expected_length - actual_length
            # Check and remove any matching 0s on the right side.
            for _ in range(number_of_zeroes):
                # The head is a 0, we expect the tail to be as well.
                if (middle % 10 != 0):
                    return False
                # Shorten the middle by discarding the tail.
                middle = middle // 10

    return is_palindrome(middle)
Determining if a number is a palindrome, in Python