## Sunday, February 24, 2013

### 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):

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.