Ending Digits of Powers of Five Form a Binary Tree
Copyright © 2008-2013 Exploring Binary
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:
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.
Ending Digit Cycles
The ending digit cycles of the positive powers of five can be determined by incremental calculation modulo powers of ten. The resulting calculations can be tabulated as follows:
- 1-digit endings
- 51: 5
- 2-digit endings
- 52: 25
- 3-digit endings
- 53: 125
- 54: 625
- 4-digit endings
- 54: 0625
- 55: 3125
- 56: 5625
- 57: 8125
- 5-digit endings
- 55: 03125
- 56: 15625
- 57: 78125
- 58: 90625
- 59: 53125
- 510: 65625
- 511: 28125
- 512: 40625
Each group of m-digit endings repeats in a cycle. Each cycle is a power of two in length, and for m ≥ 2, equals 2m-2.
Ending digits are labeled with specific powers of five: those that make up the first occurrence of each cycle. Each cycle — from the 3-digit endings on — contains the ending digits of 5m through 5(m+2m-2-1).
Ending Digit Cycles In Tree Form
The pairing of ending digits in the binary tree shows a relationship between endings in successive cycles; in particular, for level 3 and higher:
- Each pair of m digit endings has a common m-1 digit suffix.
- The starting digits of each pair of m digit endings differ by five.
Why Pairs of Siblings Have the Same Suffix
Why is there always a pair of siblings, and why do siblings match up as they do? The answer lies in the nesting of power of two sized cycles of ending digits. For example, the last four digits repeat in a cycle of four, and the last five digits repeat in a cycle of eight. To form the eight unique five digit endings, the set of four digit endings must be repeated; duplicate four digit endings will have different starting digits prefixed.
Endings with the same suffix are a half cycle length apart, and are paired as siblings. For example, in the length eight cycle of five ending digits, the following endings are paired: 1st and 5th; 2nd and 6th; 3rd and 7th; 4th and 8th.
In terms of powers of five, sibling pairs differ in their exponents by half a cycle length. You can see this by looking at the underlying powers of five in the tree:
Why the Starting Digits of Siblings Differ by Five
To show why the starting digits of siblings differ by five, let’s look at an example. In level 5 of the tree — the 5-digit endings — let’s compute the difference between each pair of powers of five (I’ll go in cycle order, not in tree order):
- 59 – 55 = 1950000
- 510 – 56 = 9750000
- 511 – 57 = 48750000
- 512 – 58 = 243750000
You can see that each differs by five in their fifth digit — the algebra behind the subtraction shows why:
- 59 – 55 = 55(54 – 1) = 50·55(54 – 1)
- 510 – 56 = 56(54 – 1) = 51·55(54 – 1)
- 511 – 57 = 57(54 – 1) = 52·55(54 – 1)
- 512 – 58 = 58(54 – 1) = 53·55(54 – 1)
Let’s analyze these expressions by evaluating them in three stages:
- 54 – 1
This expression has a factor of 24. I’ve shown that 52n – 1 has exactly n+2 factors of 2; that is, a factor of 2n+2.
- 55(54 – 1)
This expression has a factor of 55·24 = 5·104 = 50000.
- 5i·55(54 – 1), 0 ≤ i ≤ 3
This expression ends in 50000. For i > 0, 5i ends in the digit 5; for i = 0, 5i = 1. In either case, multiplying by 5i leaves the 5 in the fifth digit unchanged.
The example generalizes to show that every pair of endings in every level m of the tree, m ≥ 3, differ by 5 in their starting digits:
- Cycle length is 2m-2
- Level m includes the powers of five 5m through 5(m+2m-2-1)
- Siblings are the powers of five p and p·52m-3
- The difference between each sibling pair is 5i·5m·(52m-3 – 1), for each i between 0 and 2m-3 – 1
- The factor 52m-3 – 1 itself has a factor of 2m-1
- The factor 5m·(52m-3 – 1) itself has a factor of 5m·2m-1 = 5·10m-1
- 5·10m-1 is an m-digit number consisting of the digit 5 followed by m-1 zeros
- The factor 5i leaves the last m digits unchanged: the digit 5 followed by m-1 zeros