Tuesday, March 13, 2018

Calculating Frequency of Palindromes

In this entry, I will attempt to provide formulas for the calculation of the number of palindromes (in any number base).

If we start with our customary base 10 system, through perhaps somewhat trivial, all of the single-digit numbers from 1 - 9 (inclusive) can be viewed as palindromes.

The number 9 for example in clearly the same whether digit(s) are read from left to right (or alternatively right to left).

Then with respect to 2-digit numbers from 11 – 99 (inclusive) again we have 9 examples (where the digits from 1 - 9 repeat).

Then with respect to 3-digit palindromes, the 1st and last digits must be the same (as one of the 9 digits from 1 - 9). Then the middle digits can be any one of the 10 digits (from 0 to 9 inclusive).

Thus with respect to 3-digit numbers, we have an additional 90 examples.
Then it is just the same with respect to 4 digit numbers where the two middle digits must be the same leaving again 10 options from 00 to 99.

Then with 5-digit numbers we will have 900 additional examples and another 900 with 6 digit numbers.

So we have  9 + 9 + 90 + 90 + 900 + 900 + …

= 18 + 180 + 1800 + …

= 2 * 9(1 + 10 + 102 + …)

Thus if we let x = base number (which in this case = 10), then we have

2 (x – 1)(1 + x + x2 + …) = – 2(1 – x)( 1 + x + x2  + …)

Therfore from 1-digit to n-digit numbers (where n is even), the total no. of palindromes is

2(xn/2 – 1).

So where n = 6, we have

2(x3 – 1) which when x = 10, gives 2 * 999 = 1998 (i.e. 9 + 9 + 90 + 90 + 900 + 900).

When n is odd we get,

2{x(n + 1)/2} – {x – 1}x(n 1)/2

So with n = 5 we get 2(x3 – 1) – {x – 1}x2.

So again with x = 10 (as number base) we obtain

1998 – 900 = 1098 (i.e. 9 + 9 + 90 + 90 + 900).

Again this expresses the frequency of all palindromes for numbers up to 5 digits i.e. from 1 - 99999 (inclusive).


The 2nd part of the formula {x – 1}x(n  1)/2 expresses the narrower notion of the number of n digit palindromes (where n is odd).

Then {x – 1}x(n  2)/2 expresses the corresponding notion of the number of n digit palindromes (where n is even).

Thus when n = 6, the no. of palindromes (in base 10) = 9 * 10= 900.

No comments:

Post a Comment