Finding Numbers That Are Palindromic In Multiple Bases

A palindromic number, or number palindrome, is a number like 74347, which is the same written forward and backward.

A number can be palindromic in any base, not just decimal. For example, 101101 is a palindrome in binary. A number can also be palindromic in more than one base, like decimal 719848917, which is 101010111010000000010111010101 in binary and 5272002725 in octal.

An efficient way to find palindromes in a single base is to generate them, iterating through each integer and constructing palindromes from them. An efficient way to find numbers that are palindromic in multiple bases is to take a palindrome in one base and test if it’s a palindrome in one or more additional bases.

In this article, I’ll show you C code I wrote that finds multi-base numeric palindromes. I used this code to generate tables of numbers that are palindromic in decimal and binary, decimal and hexadecimal, and decimal and octal. I also used this code to solve Euler problem 36, which asks for the sum of all numbers, less than one million, that are palindromic in decimal and binary.

Checking Whether a Number is a Palindrome

In general, a palindrome can be any string of characters; for example, “j4$4j”, “radar”, and “9009”. The algorithm to check whether a string is palindromic is simple: just reverse the string and compare it to itself.

If you’re interested only in number palindromes, you can use a more efficient, numeric algorithm instead of a string-based one. Here’s how it works:

1. Convert the integer to be checked from a string to numeric binary; for example, using strtol(), scanf(), or simply, a compiler constant.
2. Isolate the digits of the numeric binary value by repeatedly dividing it by the number’s base.
3. Construct, from the isolated digits, a new numeric binary integer that represents the original number written in reverse.
4. Compare the original number to the reversed number — if they are equal, the number is a palindrome.

Here is a C function that implements steps 2 through 4 (step 1, the conversion of the string to numeric binary, is done outside this function, if necessary) — it is my implementation of an algorithm that appears several places on the Web (for example, at stackoverflow.com):

int isPalindrome(unsigned long long number, unsigned char base)
{
 unsigned long long forward = number;
 unsigned long long reversed = 0;
 unsigned char digit;

 while (number > 0)
 {
  digit = number % base;
  reversed = reversed * base + digit;
  number = number / base;
 }
 return (forward == reversed);
}

This function combines two base conversion algorithms: the numeric binary integer to string algorithm and the string to numeric binary integer algorithm. The “numeric to string” algorithm isolates digits of a binary integer and appends them to a string, from least to most significant digit. The “string to numeric” algorithm isolates digits of a string and sums their place values in a binary integer, from most to least significant digit. If you fuse the two together, pipelining the digits from the “numeric to string” algorithm to the “string to numeric” algorithm, you reverse the original number — without requiring an intermediate string!

Single-digit numbers, including 0, are trivially palindromic, so this function will classify them as such.

Generating Number Palindromes

For any positive integer in base b, b+1 palindromes can be made from it. For example, the following 11 decimal palindromes can be made from the number 1: 11, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191. There is one even length palindrome, and b odd length palindromes — one per base b digit.

Here is a C function that generates palindromes in this manner:

void makePalindromes(
       unsigned long long number,
       unsigned char base,
       unsigned long long* palindromes)
{
 /* Returns an array of size base+1 palindrome numbers (one even
    length palindrome followed by 'base' odd length palindromes) */
 
 unsigned long long upper = number;
 unsigned long long lower = 0;
 unsigned char digit;
 unsigned int i;
 unsigned long long power = 1;

 /* Form upper and lower portions of the new palindromes */
 while (number > 0)
 {
  upper = upper * base;  /* Shift left for each digit */
  digit = number % base;
  lower = lower * base + digit;
  number = number / base;
  power*=base;
 }

 /* Construct the even length palindrome */
 palindromes[0] = upper + lower;

 /* Construct the odd length palindromes */
 palindromes[1] = upper * base + lower; /* Middle digit: 0 */
 for (i=1; i<base; i++)
 {
  palindromes[i+1] = palindromes[1] + i*power;/* Middle digit: i */
 }
}

The core of palindrome creation is the same as palindrome checking: a number must be reversed. However, instead of comparing the reversed number to the original, the reversed number is “concatenated” to the original. Mathematically, the original number is shifted left by a power of the base, becoming the upper portion of the palindrome; the reversed number is then added in to become the lower portion.

This function generates palindromes out of numeric order — odd length palindromes are one digit longer than their corresponding even length ones. And, perhaps not intuitively, it will make single-digit palindromes — all of them — when called with the number 0. This is despite the algorithm’s “upper/lower portion” and “even/odd length” concepts not fitting single-digit numbers — the computations work out regardless. There’s one catch though: 0 is generated twice.

Be aware that, as unsigned long longs, palindromes cannot exceed 2⁶⁴ – 1. This means that the maximum number from which you can make palindromes is less than 2³². How much less depends on the base of the number.

Finding Multi-Base Palindromes

You can combine the functions makePalindromes() and isPalindrome() to make an efficient search for palindromes in multiple bases. This function does so for two bases:

void find_multi_base_palindromes(
       unsigned char base1,
       unsigned char base2,
       unsigned long long max_number,
       unsigned long long* multi_base_palindromes,
       unsigned int* multi_base_count)
{
 unsigned int i;
 unsigned long long counter = 0;
 unsigned long long* base1_palindromes;
 unsigned int max_palindromes = *multi_base_count;

 base1_palindromes = (unsigned long long*)
    malloc((base1+1)*sizeof(unsigned long long));

 *multi_base_count = 0;
 while (1)
 {
  /* Construct palindromes in base1 */
  makePalindromes(counter,base1,base1_palindromes);

  if (base1_palindromes[0] > max_number)
    break; /* Quit when even palindrome exceeds max */

  /* Test if base1 palindromes are also palindromic in base2 */
  for (i=0; i <= base1; i++)
  {
   if (base1_palindromes[i] > max_number)
     break; /* Exit "for" loop if (odd) palindrome exceeds max */

   if (isPalindrome(base1_palindromes[i],base2))
   {
    if (*multi_base_count == max_palindromes)
      assert(0); /* Error: not enough room in array */
    else
    {
     multi_base_palindromes[*multi_base_count] = 
       base1_palindromes[i];
     (*multi_base_count)++;
    }
   }
  }
  counter++;
 }
}

This function constructs palindromes repeatedly, from a counter that is incremented after each iteration. Since makePalindromes() generates palindromes out of order, knowing when to stop is a little tricky. The easy stopping case is when an even length palindrome exceeds the requested maximum — no palindromes beyond that can be smaller. The more difficult case is checking the odd length palindromes. Once one of them, from a given set, exceeds the requested maximum, the rest of that set’s palindromes do not have to be checked. However, checking must proceed to the next set of palindromes.

The parameter multi_base_count is input/output. On input, it represents the maximum number of palindromes the output array can hold. On output, it holds the number of palindromes found.

Tables of Multi-Base Palindromes

Using calls to find_multi_base_palindromes(), I created tables of multi-base palindromes in the following combinations:

• Decimal and binary
• Decimal and hexadecimal
• Decimal and octal

I used additional code (not shown) to sort the palindromes, remove the duplicate 0, and print them in various bases.

Each respective table lists all copalindromic numbers less than 10¹². The list of palindromes in each table took 6 seconds or less to find — on an Intel 1.60 GHz, Core Duo T2050 processor running Windows XP.

Palindromes in Decimal and Binary

Here are all 39 decimal/binary palindromes less than 10¹²:

Observe: Palindromes in binary, except 0 itself, cannot end in 0 — leading 0s are not counted as part of a palindrome. This means that all binary palindromes are odd numbers. This also means that any number in a base copalindromic with binary is odd, and thus must start with an odd-valued digit.

I used the following call to generate the decimal/binary table:

 find_multi_base_palindromes
   (2,10,999999999999ULL,palindromes,&count); 

Swapping bases 2 and 10 gives the same results, but putting base 2 first makes it run faster. No even palindromes will be generated and thus not needlessly checked!

Palindromes in Decimal and Hexadecimal

Here are all 53 decimal/hexadecimal palindromes less than 10¹²:

Palindromes in Decimal and Octal

Here are all 45 decimal/octal palindromes less than 10¹²:

Palindromes In Decimal and Two Other Bases

I searched for palindromes in the following three-base combinations, using a modifed version of find_multi_base_palindromes() (I added a parameter called base3 and an extra palindrome check):

• Decimal, binary, and hexadecimal
• Decimal, binary, and octal
• Decimal, hexadecimal, and octal

The only combination that produced multi-digit palindromes in three bases was decimal/binary/octal. I found two less than 10¹²:

• 585₁₀ = 1001001001₂ = 1111₈
• 719848917₁₀ = 101010111010000000010111010101₂ = 5272002725₈

In addition, I used this big table of binary/decimal palindromes to determine that

• There are no numbers less than 10³⁹ that are multi-digit copalindromic in decimal, binary and hexadecimal.
• The numbers 585₁₀ and 719848917₁₀ are the only numbers less than 10³⁸ that are multi-digit copalindromic in decimal, binary and octal.

I simply converted each entry in that table to hex and octal — none, besides the two examples above, were palindromes in those bases.

(Update: I’ve written a program capable of searching beyond 2⁶⁴ for decimal/binary/hexadecimal palindromes; none have been found to date.)

Solution to Euler Problem 36

You can use the above functions to solve Euler problem 36. Here’s the code:

void euler36()
{
 unsigned int decimal_binary_count = 50; /* (Room to spare) */
 unsigned long long decimal_binary_palindromes[50]; 
 unsigned int i;
 unsigned long long sum = 0;

 find_multi_base_palindromes
   (2,10,999999,decimal_binary_palindromes,&decimal_binary_count); 

 for (i=1; i < decimal_binary_count; i++) /* i=1 skips dupe 0 */
   sum+=decimal_binary_palindromes[i];

 printf("The answer to Euler problem 36: %lld\n",sum);
}

(I won’t do all the work for you. You’ll have to at least run this code to get the answer — that or add values manually from the decimal/binary palindrome table above.)

This function runs in well under 1 second.

Application to Other Euler Problems

There are other Euler problems that involve number palindromes: Euler problem 4, Euler problem 55, and Euler problem 125. Some of the above code could be used to solve them.

On Manipulating Other Bases In Binary

The thing I find most interesting about generating and testing palindromes numerically in software is this: conceptually, we’re manipulating numbers in different bases, but in reality, we’re representing them and calculating with them in binary.