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

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] |

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:

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

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:

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

Invalidnumber |
Validnumbers 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.

## No comments:

## Post a Comment