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.

Decimal Palindromes Generated from the Number 1
Decimal Palindromes Generated from the Number 1

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 264 – 1. This means that the maximum number from which you can make palindromes is less than 232. 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 1012. 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 1012:

Decimal/Binary Palindromes
Decimal Binary
010 02
110 12
310 112
510 1012
710 1112
910 10012
3310 1000012
9910 11000112
31310 1001110012
58510 10010010012
71710 10110011012
744710 11101000101112
900910 100011001100012
1535110 111011111101112
3222310 1111101110111112
3999310 10011100001110012
5323510 11001111111100112
5383510 11010010010010112
7373710 100100000000010012
58558510 100011101111011100012
175857110 1101011010101011010112
193439110 1110110000100001101112
197979110 1111000110101100011112
312921310 10111110111111011111012
507170510 100110101100011010110012
525952510 101000001000001000001012
584148510 101100100100010010011012
1350053110 1100111000000000011100112
71984891710 1010101110100000000101110101012
91037301910 1101100100001100110000100110112
93947493910 1101111111111100111111111110112
129088092110 10011001111000101000111100110012
745111154710 1101111000001111011110000011110112
1005090500110 10010101110001010010100011101010012
1846212648110 100010011000110110110110001100100012
3247929742310 111100011111110101010111111100011112
7501515105710 10001011101110100000001011101110100012
11094884901110 11001110101010001000100010101011100112
13652552563110 11111110010011000111000110010011111112

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 1012:

Decimal/Hexadecimal Palindromes
Decimal Hexadecimal
010 016
110 116
210 216
310 316
410 416
510 516
610 616
710 716
810 816
910 916
1110 B16
35310 16116
62610 27216
78710 31316
97910 3D316
199110 7C716
300310 BBB16
3959310 9AA916
4151410 A22A16
9020910 1606116
9404910 16F6116
9636910 1787116
9868910 1818116
33333310 5161516
51221510 7D0D716
66666610 A2C2A16
74994710 B717B16
84554810 CE6EC16
161216110 18998116
248584210 25EE5216
561416510 55AA5516
648784610 62FF2616
961616910 92BB2916
6743347610 404F40416
9099990910 56C8C6516
9435534910 59FBF9516
9454454910 5A2A2A516
11991991110 725D52716
16113116110 99AAA9916
19008009110 B54645B16
24109014210 E5EBE5E16
24796974210 EC7B7CE16
2689676986210 6432C234616
2858626858210 6A7DFD7A616
2877989778210 6B36A63B616
3014464410310 704C2C40716
3244292442310 78DBFBD8716
3976252679310 94208024916
4383636383410 A34D9D43A16
4596121695410 AB38083BA16
5111353111510 BE69A96EB16
5670212076510 D33B5B33D16
39018998109310 5AD9229DA516

Palindromes in Decimal and Octal

Here are all 45 decimal/octal palindromes less than 1012:

Decimal/Octal Palindromes
Decimal Octal
010 08
110 18
210 28
310 38
410 48
510 58
610 68
710 78
910 118
12110 1718
29210 4448
33310 5158
37310 5658
41410 6368
58510 11118
366310 71178
877810 211128
1313110 315138
1333110 320238
2646210 635368
2666210 640468
3010310 726278
3030310 731378
20770210 6255268
62882610 23141328
66006610 24111428
149694110 55535558
193539110 73040378
197079110 74111478
419891410 200110028
5536635510 3231513238
13053503110 7617471678
53289823510 37606606738
71984891710 52720027258
79953599710 57517715758
182033028110 154400044518
246455464210 222714172228
442499424410 407600067048
448088084410 413051503148
463733736410 424320234248
2085555580210 2333055033328
9402989204910 12744474447218
9446666644910 12776515677218
29437887349210 42212262212248
39089449809310 55403101304558

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 1012:

  • 58510 = 10010010012 = 11118
  • 71984891710 = 1010101110100000000101110101012 = 52720027258

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

  • There are no numbers less than 1039 that are multi-digit copalindromic in decimal, binary and hexadecimal.
  • The numbers 58510 and 71984891710 are the only numbers less than 1038 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 264 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.

Dingbat
RSS feed icon
RSS e-mail icon

11 comments

  1. This is a comment I received by email from Bill Beckmann:

    There are two numbers > 10 (in decimal notation) — 121 and 373 — that are “co-palindromic” or “multi-palindromic” in four bases less than or equal to 10. (If arbitrarily large bases are allowed, every number is multi-palindromic in an arbitrarily large number of bases.) 121 is palindromic when it is expressed in bases 3, 7, 8, and 10; and 373 is palindromic when expressed in bases 4, 8, 9, and 10. The only other number that I have found that is multi-palindromic in 4 bases (≤ 10) and less than one million (10^6) is 786435, and this is multi-palindromic in bases 2, 4, 7, and 8. I have found no number >10 and ≤ 2.5*10^6 that is multi-palindromic in 5 bases (≤ 10).

  2. And there are no more numbers less that 10^9 that are palindromic in 4 or more bases <= 10 than those 3.

    300 is palindromic in 11 bases <=100, and 720 in 10 different. None others with that many < 10^8

    6643 is the smallest number palindromic in bases 2 and 3 (also 9). The next are 1422773 and 5415589. These 3 are the only ones less that 10^9 which are palindromic in bases 2 and 3.

  3. How do you provide the base as 10 or 16 in isPalindrome(), because its taking 2nd parameter as unsigned char, it will give warning
    warning: multi-character character constant [-Wmultichar]
    warning: large integer implicitly truncated to unsigned type [-Woverflow]

    and your logic doesn’t work for any base other than 10.

Leave a Reply

Your email address will not be published. Required fields are marked *

(Cookies must be enabled to leave a comment...it reduces spam.)