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:

- Convert the integer to be checked from a string to numeric binary; for example, using strtol(), scanf(), or simply, a compiler constant.
- Isolate the digits of the numeric binary value by repeatedly dividing it by the number’s base.
- Construct, from the isolated digits, a new numeric binary integer that represents the original number written in reverse.
- 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):

intisPalindrome(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

**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!**

*string to numeric binary integer*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:

voidmakePalindromes( 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^{64} – 1. This means that the maximum number from which you can make palindromes is less than 2^{32}. 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:

voidfind_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^{12}. 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^{12}:

Decimal | Binary |
---|---|

0_{10} |
0_{2} |

1_{10} |
1_{2} |

3_{10} |
11_{2} |

5_{10} |
101_{2} |

7_{10} |
111_{2} |

9_{10} |
1001_{2} |

33_{10} |
100001_{2} |

99_{10} |
1100011_{2} |

313_{10} |
100111001_{2} |

585_{10} |
1001001001_{2} |

717_{10} |
1011001101_{2} |

7447_{10} |
1110100010111_{2} |

9009_{10} |
10001100110001_{2} |

15351_{10} |
11101111110111_{2} |

32223_{10} |
111110111011111_{2} |

39993_{10} |
1001110000111001_{2} |

53235_{10} |
1100111111110011_{2} |

53835_{10} |
1101001001001011_{2} |

73737_{10} |
10010000000001001_{2} |

585585_{10} |
10001110111101110001_{2} |

1758571_{10} |
110101101010101101011_{2} |

1934391_{10} |
111011000010000110111_{2} |

1979791_{10} |
111100011010110001111_{2} |

3129213_{10} |
1011111011111101111101_{2} |

5071705_{10} |
10011010110001101011001_{2} |

5259525_{10} |
10100000100000100000101_{2} |

5841485_{10} |
10110010010001001001101_{2} |

13500531_{10} |
110011100000000001110011_{2} |

719848917_{10} |
101010111010000000010111010101_{2} |

910373019_{10} |
110110010000110011000010011011_{2} |

939474939_{10} |
110111111111110011111111111011_{2} |

1290880921_{10} |
1001100111100010100011110011001_{2} |

7451111547_{10} |
110111100000111101111000001111011_{2} |

10050905001_{10} |
1001010111000101001010001110101001_{2} |

18462126481_{10} |
10001001100011011011011000110010001_{2} |

32479297423_{10} |
11110001111111010101011111110001111_{2} |

75015151057_{10} |
1000101110111010000000101110111010001_{2} |

110948849011_{10} |
1100111010101000100010001010101110011_{2} |

136525525631_{10} |
1111111001001100011100011001001111111_{2} |

** 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^{12}:

Decimal | Hexadecimal |
---|---|

0_{10} |
0_{16} |

1_{10} |
1_{16} |

2_{10} |
2_{16} |

3_{10} |
3_{16} |

4_{10} |
4_{16} |

5_{10} |
5_{16} |

6_{10} |
6_{16} |

7_{10} |
7_{16} |

8_{10} |
8_{16} |

9_{10} |
9_{16} |

11_{10} |
B_{16} |

353_{10} |
161_{16} |

626_{10} |
272_{16} |

787_{10} |
313_{16} |

979_{10} |
3D3_{16} |

1991_{10} |
7C7_{16} |

3003_{10} |
BBB_{16} |

39593_{10} |
9AA9_{16} |

41514_{10} |
A22A_{16} |

90209_{10} |
16061_{16} |

94049_{10} |
16F61_{16} |

96369_{10} |
17871_{16} |

98689_{10} |
18181_{16} |

333333_{10} |
51615_{16} |

512215_{10} |
7D0D7_{16} |

666666_{10} |
A2C2A_{16} |

749947_{10} |
B717B_{16} |

845548_{10} |
CE6EC_{16} |

1612161_{10} |
189981_{16} |

2485842_{10} |
25EE52_{16} |

5614165_{10} |
55AA55_{16} |

6487846_{10} |
62FF26_{16} |

9616169_{10} |
92BB29_{16} |

67433476_{10} |
404F404_{16} |

90999909_{10} |
56C8C65_{16} |

94355349_{10} |
59FBF95_{16} |

94544549_{10} |
5A2A2A5_{16} |

119919911_{10} |
725D527_{16} |

161131161_{10} |
99AAA99_{16} |

190080091_{10} |
B54645B_{16} |

241090142_{10} |
E5EBE5E_{16} |

247969742_{10} |
EC7B7CE_{16} |

26896769862_{10} |
6432C2346_{16} |

28586268582_{10} |
6A7DFD7A6_{16} |

28779897782_{10} |
6B36A63B6_{16} |

30144644103_{10} |
704C2C407_{16} |

32442924423_{10} |
78DBFBD87_{16} |

39762526793_{10} |
942080249_{16} |

43836363834_{10} |
A34D9D43A_{16} |

45961216954_{10} |
AB38083BA_{16} |

51113531115_{10} |
BE69A96EB_{16} |

56702120765_{10} |
D33B5B33D_{16} |

390189981093_{10} |
5AD9229DA5_{16} |

### Palindromes in Decimal and Octal

Here are all 45 decimal/octal palindromes less than 10^{12}:

Decimal | Octal |
---|---|

0_{10} |
0_{8} |

1_{10} |
1_{8} |

2_{10} |
2_{8} |

3_{10} |
3_{8} |

4_{10} |
4_{8} |

5_{10} |
5_{8} |

6_{10} |
6_{8} |

7_{10} |
7_{8} |

9_{10} |
11_{8} |

121_{10} |
171_{8} |

292_{10} |
444_{8} |

333_{10} |
515_{8} |

373_{10} |
565_{8} |

414_{10} |
636_{8} |

585_{10} |
1111_{8} |

3663_{10} |
7117_{8} |

8778_{10} |
21112_{8} |

13131_{10} |
31513_{8} |

13331_{10} |
32023_{8} |

26462_{10} |
63536_{8} |

26662_{10} |
64046_{8} |

30103_{10} |
72627_{8} |

30303_{10} |
73137_{8} |

207702_{10} |
625526_{8} |

628826_{10} |
2314132_{8} |

660066_{10} |
2411142_{8} |

1496941_{10} |
5553555_{8} |

1935391_{10} |
7304037_{8} |

1970791_{10} |
7411147_{8} |

4198914_{10} |
20011002_{8} |

55366355_{10} |
323151323_{8} |

130535031_{10} |
761747167_{8} |

532898235_{10} |
3760660673_{8} |

719848917_{10} |
5272002725_{8} |

799535997_{10} |
5751771575_{8} |

1820330281_{10} |
15440004451_{8} |

2464554642_{10} |
22271417222_{8} |

4424994244_{10} |
40760006704_{8} |

4480880844_{10} |
41305150314_{8} |

4637337364_{10} |
42432023424_{8} |

20855555802_{10} |
233305503332_{8} |

94029892049_{10} |
1274447444721_{8} |

94466666449_{10} |
1277651567721_{8} |

294378873492_{10} |
4221226221224_{8} |

390894498093_{10} |
5540310130455_{8} |

### 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^{12}:

- 585
_{10}= 1001001001_{2}= 1111_{8} - 719848917
_{10}= 101010111010000000010111010101_{2}= 5272002725_{8}

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

**There are no numbers less than 10**^{39}that are multi-digit copalindromic in decimal, binary and hexadecimal.- The numbers 585
_{10}and 719848917_{10}are thenumbers less than 10*only*^{38}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^{64} 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.

As a result of this work, I got credit for correcting errors in the

On-Line Encyclopedia of Integer Sequences: Sloane’s A029804, “Numbers that are palindromic in bases 8 and 10”.Aren’t your binary palindromes lacking? Like. 1111, 10101, etc.

CAM,

“Lacking” in what sense?

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).

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.

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.

@Ajay,

Please elaborate on why my “logic doesn’t work for any base other than 10”. It worked for me (when I ran it six years ago).

Its working fine, i was making mistake while passing values to your function

What is palindome of Greater than 11 less than 50?

What is first three digits palindrome?

@Alan Deslate,

I need more information: for example, what base(s)?