On palindromic numbers

Much of this is taken from my comment to a post titled Can every number be written as a palindrome in some base? on MathFour.com. The original post asks whether every number has a palindromic representation in some base.

What's a palindrome?

First, some definitions, for those who don't read the original post. A palindrome is read the same backwards and forwards. E.g.: racecar or A man, a plan, a canal: Panama. Note that only the letters are considered, not spaces or punctuation. A palindromic number has the same properties: 121 and 98,766,789 are both palindromes.

We commonly use base-10 numbers, but computers use base-2 (binary) and we encounter base-16 (hexadecimal) in computing, often to represent colors. The number of a base determines how many symbols are possible for each digit. (0-9 for base-10, 0 & 1 for base-2, 0-9 plus A-F for base-16, etc.) More to the point, it determines the value of each number-place. The first place is how many singles, the next is how many of the base value, and subsequent places are how many of increasing powers of the base value. In our everyday decimal, or base-10, numbers, this would be ones, tens (the base), hundreds (\(10^2\)), thousands (\(10^3\)), etc.

The original post asked whether all numbers could be written as a palindrome in some base, whether it be base-10 (121 for example) or another base. As it figures, every number can be written as a palindrome in the base one less than the number (\(n - 1\)) such as 3 being 11 in base-2. This is due to the definition of bases, where the first '1' is the base value (here, one less than the number) and the second '1' is the value one. In other words, \((n - 1) + 1 = n\). [Also note that in bases > \(n\) the number will be a single digit. This, too, is a palindrome, albeit a lame one.]

A limited limit

So, what's a useful limiting factor? The original post looks at those numbers which have a palindrome with a base ≤ 10; i.e., one that would be written using only the digits 0–9. For the sake of completeness, let's look at those numbers that are invalid based on that definition (the original post included too many):

Base > 10 (1–100)

Number	Base	Palindrome
19	18	[1, 1]
39	12	[3, 3]
47	46	[1, 1]
53	52	[1, 1]
58	28	[2, 2]
69	22	[3, 3]
75	14	[5, 5]
76	18	[4, 4]
79	78	[1, 1]
84	11	[7, 7]
87	28	[3, 3]
90	14	[6, 6]
94	46	[2, 2]
95	18	[5, 5]
96	11	[8, 8]

Note: The palindromes are shown as a bracketed list with the value of each place value. This is to make larger bases easily represented and readable without having to remember what 'R' means, for example (it's 27), and without having to invent single-character representations of values larger than 35.

I find this to be too arbitrary. Yes, it's easier to look & think about for us humans who're used to base-10 numbers, but where's the fun there? (Also note that none of those invalid palindromes use digits > 9, highlighting the arbitrariness of the imposed limit.)

I tend more towards general solutions to problems, so I think a more interesting question is: What is the lowest base in which \(n\) is a palindrome? (Obviously, we're omitting base-1 numbers as they are all palindromes.)

Also, since all numbers are palindromes in bases greater than \(n - 1\) (excluding base-\(n\)), why not limit "valid" palindromes to those less than \(n - 1\)? So the question becomes: Does \(n\) have a palindrome in a base less than base-\((n - 1)\)? Is there a pattern to these numbers? Do they occur more, less or equally frequent as we look at larger sets of integers?

Python to the rescue!

Of course, computers make these things so much easier to look at. I made a quick Python script to examine palindromic numbers. The benefits here are I don't have to worry about inventing a character for each digit. I can just leave the decimal value of that digit as-is and place the digits in a list. So, here are some results for integers 1–100:

The full list (1–100)

Number	Base	Palindrome
1	2	[1]
2	3	[2]
3	2	[1, 1]
4	3	[1, 1]
5	2	[1, 0, 1]
6	5	[1, 1]
7	2	[1, 1, 1]
8	3	[2, 2]
9	2	[1, 0, 0, 1]
10	3	[1, 0, 1]
11	10	[1, 1]
12	5	[2, 2]
13	3	[1, 1, 1]
14	6	[2, 2]
15	2	[1, 1, 1, 1]
16	3	[1, 2, 1]
17	2	[1, 0, 0, 0, 1]
18	5	[3, 3]
19	18	[1, 1]
20	3	[2, 0, 2]
21	2	[1, 0, 1, 0, 1]
22	10	[2, 2]
23	3	[2, 1, 2]
24	5	[4, 4]
25	4	[1, 2, 1]
26	3	[2, 2, 2]
27	2	[1, 1, 0, 1, 1]
28	3	[1, 0, 0, 1]
29	4	[1, 3, 1]
30	9	[3, 3]
31	2	[1, 1, 1, 1, 1]
32	7	[4, 4]
33	2	[1, 0, 0, 0, 0, 1]
34	4	[2, 0, 2]
35	6	[5, 5]
36	5	[1, 2, 1]
37	6	[1, 0, 1]
38	4	[2, 1, 2]
39	12	[3, 3]
40	3	[1, 1, 1, 1]
41	5	[1, 3, 1]
42	4	[2, 2, 2]
43	6	[1, 1, 1]
44	10	[4, 4]
45	2	[1, 0, 1, 1, 0, 1]
46	4	[2, 3, 2]
47	46	[1, 1]
48	7	[6, 6]
49	6	[1, 2, 1]
50	7	[1, 0, 1]
51	2	[1, 1, 0, 0, 1, 1]
52	3	[1, 2, 2, 1]
53	52	[1, 1]
54	8	[6, 6]
55	4	[3, 1, 3]
56	3	[2, 0, 0, 2]
57	5	[2, 1, 2]
58	28	[2, 2]
59	4	[3, 2, 3]
60	9	[6, 6]
61	6	[1, 4, 1]
62	5	[2, 2, 2]
63	2	[1, 1, 1, 1, 1, 1]
64	7	[1, 2, 1]
65	2	[1, 0, 0, 0, 0, 0, 1]
66	10	[6, 6]
67	5	[2, 3, 2]
68	3	[2, 1, 1, 2]
69	22	[3, 3]
70	9	[7, 7]
71	7	[1, 3, 1]
72	5	[2, 4, 2]
73	2	[1, 0, 0, 1, 0, 0, 1]
74	6	[2, 0, 2]
75	14	[5, 5]
76	18	[4, 4]
77	10	[7, 7]
78	5	[3, 0, 3]
79	78	[1, 1]
80	3	[2, 2, 2, 2]
81	8	[1, 2, 1]
82	3	[1, 0, 0, 0, 1]
83	5	[3, 1, 3]
84	11	[7, 7]
85	2	[1, 0, 1, 0, 1, 0, 1]
86	6	[2, 2, 2]
87	28	[3, 3]
88	5	[3, 2, 3]
89	8	[1, 3, 1]
90	14	[6, 6]
91	3	[1, 0, 1, 0, 1]
92	6	[2, 3, 2]
93	2	[1, 0, 1, 1, 1, 0, 1]
94	46	[2, 2]
95	18	[5, 5]
96	11	[8, 8]
97	8	[1, 4, 1]
98	5	[3, 4, 3]
99	2	[1, 1, 0, 0, 0, 1, 1]
100	3	[1, 0, 2, 0, 1]

Now, "invalid" palindromes (note how few there are):

Base ≥ \((n - 1)\) (1–100)

Number	Base	Palindrome
1	2	[1]
2	3	[2]
3	2	[1, 1]
4	3	[1, 1]
6	5	[1, 1]
11	10	[1, 1]
19	18	[1, 1]
47	46	[1, 1]
53	52	[1, 1]
79	78	[1, 1]

Only 10% of numbers through 100 have only the default palindrome. Interestingly, none of these numbers use a digit greater than 8 in their palindromic representation. In fact … the first number to use 10 (or greater) in their lowest-base palindromic representation is 120 (base 11, [10, 10]). (108 is the first to use 9.)

What's the frequency?

How about the frequencies of these invalid palindromes? Here's a look at the percentages for each group of 100 numbers through 10,000:

Frequencies of invalid palindromes

Range	%
1–100	10
101–200	7
201–300	5
301–400	6
401–500	2
501–600	3
601–700	2
701–800	1
801–900	3
901–1000	3
1001–1100	3
1101–1200	1
1201–1300	2
1301–1400	1
1401–1500	4
1501–1600	3
1601–1700	1
1701–1800	3
1801–1900	0
1901–2000	4
2001–2100	4
2101–2200	3
2201–2300	2
2301–2400	2
2401–2500	2
2501–2600	1
2601–2700	4
2701–2800	2
2801–2900	1
2901–3000	1
3001–3100	2
3101–3200	1
3201–3300	3
3301–3400	2
3401–3500	2
3501–3600	3
3601–3700	2
3701–3800	0
3801–3900	2
3901–4000	0
4001–4100	4
4101–4200	2
4201–4300	2
4301–4400	4
4401–4500	1
4501–4600	2
4601–4700	2
4701–4800	2
4801–4900	1
4901–5000	3
5001–5100	5
5101–5200	1
5201–5300	2
5301–5400	4
5401–5500	3
5501–5600	2
5601–5700	2
5701–5800	2
5801–5900	2
5901–6000	1
6001–6100	4
6101–6200	2
6201–6300	4
6301–6400	4
6401–6500	0
6501–6600	2
6601–6700	1
6701–6800	1
6801–6900	1
6901–7000	3
7001–7100	2
7101–7200	1
7201–7300	3
7301–7400	0
7401–7500	2
7501–7600	0
7601–7700	1
7701–7800	0
7801–7900	2
7901–8000	2
8001–8100	3
8101–8200	2
8201–8300	5
8301–8400	0
8401–8500	1
8501–8600	2
8601–8700	2
8701–8800	1
8801–8900	1
8901–9000	1
9001–9100	3
9101–9200	1
9201–9300	3
9301–9400	3
9401–9500	2
9501–9600	2
9601–9700	2
9701–9800	2
9801–9900	1
9901–10000	0

There are very few numbers without a valid palindromic representation. In fact, through 10,000 there are only 2.22 per hundred. While there are only 9 instances of no valid palindromes in the arbitrary 100-number blocks above, there are in fact 22 different stretches of triple-digit runs without an invalid palindrome, the longest of these being 203! This includes the 112-number run that finishes with 10,000 and possibly goes longer. Excluding this final, partial run, the mean length of a run is a little over 44 ⅓.

Runs of valid palindromes

Invalid number	Valid numbers preceding
1	0
2	0
3	0
4	0
6	1
11	4
19	7
47	27
53	5
79	25
103	23
137	33
139	1
149	9
163	13
167	3
179	11
223	43
263	39
269	5
283	13
293	9
311	17
317	5
347	29
359	11
367	7
389	21
439	49
491	51
563	71
569	5
593	23
607	13
659	51
739	79
827	87
853	25
877	23
977	99
983	5
997	13
1019	21
1049	29
1061	11
1187	125
1213	25
1237	23
1367	129
1433	65
1439	5
1447	7
1459	11
1511	51
1553	41
1579	25
1669	89
1709	39
1753	43
1759	5
1907	147
1949	41
1993	43
1997	3
2011	13
2063	51
2087	23
2099	11
2111	11
2137	25
2179	41
2207	27
2287	79
2309	21
2339	29
2417	77
2459	41
2503	43
2657	153
2677	19
2683	5
2693	9
2713	19
2749	35
2897	147
2963	65
3023	59
3089	65
3119	29
3229	109
3253	23
3259	5
3323	63
3371	47
3407	35
3449	41
3547	97
3559	11
3583	23
3623	39
3643	19
3833	189
3847	13
4007	159
4073	65
4091	17
4099	7
4139	39
4157	17
4211	53
4283	71
4337	53
4339	1
4349	9
4391	41
4463	71
4523	59
4549	25
4643	93
4679	35
4729	49
4787	57
4871	83
4909	37
4919	9
4933	13
5011	77
5021	9
5039	17
5059	19
5099	39
5179	79
5231	51
5297	65
5303	5
5309	5
5351	41
5387	35
5417	29
5431	13
5471	39
5503	31
5527	23
5653	125
5693	39
5711	17
5791	79
5827	35
5839	11
5939	99
6047	107
6067	19
6079	11
6089	9
6131	41
6199	67
6229	29
6247	17
6269	21
6277	7
6311	33
6343	31
6359	15
6389	29
6551	161
6599	47
6653	53
6793	139
6871	77
6947	75
6983	35
6991	7
7019	27
7079	59
7159	79
7213	53
7247	33
7283	35
7433	149
7487	53
7691	203
7817	125
7877	59
7949	71
7963	13
8017	53
8069	51
8089	19
8123	33
8147	23
8221	73
8243	21
8287	43
8291	3
8293	1
8423	129
8539	115
8573	33
8669	95
8699	29
8783	83
8863	79
8941	77
9043	101
9059	15
9067	7
9173	105
9209	35
9227	17
9277	49
9337	59
9341	3
9377	35
9419	41
9421	1
9533	111
9587	53
9643	55
9689	45
9739	49
9781	41
9887	105

Looking at these two frequency graphs, it seems invalid palindromes, while a little more frequent in lower integers, occur otherwise without a discernible pattern.

Where do we go from here?

While we're having fun, let's look at some specific groups of numbers. Of the 222 invalid palindromes from 1–10,000, a staggering 219 are odd, with only 3 even. These are 2, 4 & 6 — the first three even numbers. Now we're getting somewhere — almost all invalid palindromes are odd! So why do almost all evens (assuming there continue to be none beyond 5,000,276 — the highest I've figured out so far through a brute force program running while I type this post — which is not certain) have valid palindromes? Maybe we'll get some insight if we examine the even palindromes. Join me in the next post for just that.