In my article “Patterns in the Last Digits of the Positive Powers of Five” I showed that the cycles of ending digits of the positive powers of five could be represented with a binary tree:
Binary Tree Showing Nested Ending Digit Patterns of the Positive Powers of Five
The tree layout shows that certain pairs of ending digits are related, and that these pairs differ by five in their starting digits. I will show why this is true.
In my article “Counting Binary and Hexadecimal Palindromes” I derived formulas for counting binary palindromes and hexadecimal palindromes. For each type of palindrome, I derived two pairs of formulas: one pair to count n-digit palindromes, and one pair to count palindromes of n digits or less.
In this article, I will derive similar formulas to count binary/hexadecimal palindromes — multi-base palindromes I’ve shown to have an algorithmically defined structure.
How many nonzero, n-digit, decimal number palindromes are there? These two formulas give the answer:
How many nonzero, decimal number palindromes are there, consisting of n-digits or less? These two formulas give the answer:
So for example, there are 900 5-digit decimal palindromes, 9,000 8-digit decimal palindromes, 1,098 decimal palindromes of 5 digits or less, and 19,998 decimal palindromes of 8 digits or less.
In this article, I will derive similar formulas to count binary and hexadecimal number palindromes.
In my article “Patterns in the Last Digits of the Positive Powers of Five” I noted that the positive powers of five modulo 10m cycle with period 2m-2, m ≥ 2, starting at 5m. In this article, I’ll present my proof, which has two parts:
The highlight of my proof is in part 1, where I derive a formula to show that the period, or order, of 5 mod 2m is 2m-2. While it is in general not possible to derive a formula for the order of a number, I’ll show it is possible for the powers of five mod 2m — due to a hidden, binary structure I’ve uncovered.
In my article “Nines in Binary”, I proved the following: positive integers of the form 10n-1, that is, integers made up of n digits of 9s, have binary representations with exactly n digits of trailing 1s. Pat Ballew made a clever observation, adapting my result to prove an equivalent statement for base 5 (quinary): positive integers of the form 10n-1 have quinary representations that have exactly n digits of trailing 4s. For example, 9999 in decimal is 304444 in quinary.
In “Nines in Binary”, I derived an expression for 10n – 1 that shows its structure as a binary number:
10n – 1 = (5n – 1) 2n + (2n – 1)
Pat derived a similar expression for 10n – 1 that shows its structure as a quinary number:
10n – 1 = (2n – 1) 5n + (5n – 1)
In essence, he swapped the 2s and 5s, making it the “dual” of my formula, if you will.
I’ll show the details of the derivation and prove why the formula works.
Pradeep Mutalik of The New York Times recently blogged about a puzzle that is an instance of the Josephus Problem. The problem, restated simply, is this: there are n people standing in a circle, of which you are one. Someone outside the circle goes around clockwise and repeatedly eliminates every other person in the circle, until one person — the winner — remains. Where should you stand so you become the winner?
Here’s an example with 13 participants:
Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)
As Pradeep and his readers point out, there’s no need to work through the elimination process — a simple formula will give the answer. This formula, you won’t be surprised to hear, has connections to the powers of two and binary numbers. I will discuss my favorite solution, one based on the powers of two.
I discovered a cool property of positive integers of the form 10n-1, that is, integers made up of n digits of 9s: they have binary representations that have exactly n digits of trailing 1s. For example, 9,999,999 in decimal is 100110001001011001111111 in binary.
The property is interesting in and of itself, but what is more interesting is the process I went through to discover it. It’s a small-scale example of experimental mathematics: I observed something interesting, experimented to collect more data, developed a hypothesis, and constructed a proof.
