In 2014, an
addictive video game app named 2048
became a viral hit. It is a simple single-player
game played on a 4 x 4 grid, in which each turn consists of sliding all the
tiles on the grid either up, down, left, or right. Any two adjacent matching tiles are combined
to make one new tile worth the sum of the two original tiles, and after each
turn a new tile worth either 2 or 4 is placed randomly on an open spot on the
board. If there is no room on the board
for the random tile to appear, then the game is over and the player loses; but
if the player manages to make a 2048 tile before this happens, then he or she
wins.
2048 video game app
Every time a
match is made, the numbers double in value, and since the starting values are 2
or 4, every number on the board must be a power of 2. Furthermore, a winning tile of 2048 (that
begins as a 2) must at some point be every power of 2 before it – first 2, then
4, then 8, then 16, then 32, then 64, then 128, then 256, then 512, then 1024,
and finally 2048.
Last Digit Cycles of Exponents in Base 10
Interestingly,
the last digit of these powers of 2 cycle through a pattern. The last digits of 2, 4, 8, 16, 32, 64, 128,
256, 512, 1024, and 2048 are 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, and 8 respectively,
which repeats the cycle [2, 4, 8, 6] over and over again.
The powers
of other digits also follow cycles. The
powers of 3 are 3, 9, 27, 81, 343, 729, 2187, 6561, … whose last digits are 3,
9, 7, 1, 3, 9, 7, 1 … , making a cycle of [3, 9, 7, 1]. The powers of 4 are 4, 16, 64, 256, 1024,
4096, … whose last digits are 4, 6, 4, 6, 4, 6, … , making a cycle of [4, 6],
this time only two numbers. The powers
of 5 are 5, 25, 125, 625, 3125, … whose last digits are all fives, making a
cycle of [5], only one number. The
cycles can be calculated for all the other digits, too, and the results are
summarized in the table below.
digit
|
exp.
cycle
|
period
|
0
|
[0]
|
1
|
1
|
[1]
|
1
|
2
|
[2, 4, 8, 6]
|
4
|
3
|
[3, 9, 7, 1]
|
4
|
4
|
[4, 6]
|
2
|
5
|
[5]
|
1
|
6
|
[6]
|
1
|
7
|
[7, 9, 3, 1]
|
4
|
8
|
[8, 4, 2, 6]
|
4
|
9
|
[9, 1]
|
2
|
Last Digit Cycles of
Exponents in Base 10
The most
intriguing feature of these cycles is that the period for each digit is either
4 or a factor of 4. That means that any
whole number to the exponent of 4n + 1, where n is any integer (such as exponents
1, 5, 9, 13, … ), has the same last digit as the original base. This applies to all whole numbers big and
small in base 10, whether it be 175 = 1419857 or 221
= 2097152, which is pretty amazing!
But why does
the period of exponent cycles in base 10 have the value of 4? Examining the properties and patterns of last
digit cycles of multiples and examining patterns of last digit cycles in
multiples and exponents of bases other than 10 will help answer this question.
Last Digit Cycles of Multiples in Base 10
The last
digit cycles of the multiples of different digits can be calculated fairly
easily by using elementary multiplication facts. The multiples of 1 are the counting numbers
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, … ,
making a cycle of [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] and a period of 10. The multiples of 2 are the even numbers 2, 4,
6, 8, 10, 12, 14, … , making a cycle of [2, 4, 6, 8, 0] and a period of 5. The multiples of 3 are 3, 6, 9, 12, 15, 18,
21, 24, 27, 30, 33, 36, … , making a cycle of [3, 6, 9, 2, 5, 8, 1, 4, 7, 0]
and a period of 10. The results for the other
digits are summarized in the table below.
digit
|
multiples
cycle
|
period
|
0
|
[0]
|
1
|
1
|
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
|
10
|
2
|
[2, 4, 6, 8, 0]
|
5
|
3
|
[3, 6, 9, 2, 5, 8, 1, 4, 7, 0]
|
10
|
4
|
[4, 8, 2, 6, 0]
|
5
|
5
|
[5, 0]
|
2
|
6
|
[6, 2, 8, 4, 0]
|
5
|
7
|
[7, 4, 1, 8, 5, 2, 9, 6, 3, 0]
|
10
|
8
|
[8, 6, 4, 2, 0]
|
5
|
9
|
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
|
10
|
Last Digit Cycles of Multiples
in Base 10
There are a
few things that can be observed from this table. First of all, all the periods are either 10
or a factor of 10, the same value as the base.
That means that any whole number multiplied by 10n + 1, where n is any
integer (such as multipliers 1, 11, 21, 31, …) has the same last digit as the
original number; for example, 17 ∙ 11 = 187 or 23 ∙
21 = 483. This makes sense since the last digit of the multiplier is 1,
the identity for multiplication.
Secondly, the period is shorter than its base if and only if the digit
and the base have a common factor greater than 1. For example, the digit 2 has a period less
than 10 because 2 and 10 have a common factor of 2. Conversely, a digit has a full period if and
only if it is co-prime with the base.
For example, since the greatest common factor 3 and 10 is 1, 3 and 10
are co-prime, and 3 has a full period of 10. Lastly, all the cycles end with 0,
the identity for addition.
Strangely,
these properties for multiples do not carry over to exponents. The periods of exponents in base 10 are
factors of 4, not factors of 10. The
periods of exponents are not consistent with the number of common factors between
its digit and its base (for example, both 7 and 9 are co-prime with 10, but 7
has a full period while 9 does not).
Finally, the last numbers in each period of exponents are different (0,
1, 5, or 6).
Unfortunately,
the properties of last digit multiples does not give a solution to why the
period of the exponent cycles in base 10 has a value of 4. However, it does give valuable insights about
greatest common factors and numbers that are co-prime, which is a clue. Hopefully, examining last digit cycles in a
different base, a prime base, should give even more insight.
Last Digit Cycles of Multiples in Base 5
Finding last
digit cycles in a different base is the same as finding them in base 10, but
instead of using the last digit, which is technically the remainder after
dividing by 10, the remainders after dividing by the base are used instead. For example, the multiples of 2 are 2, 4, 6,
8, 10, 12, … , but the remainders of each of these numbers after dividing by 5
are 2, 4, 1, 3, 0, 2, … , making a cycle of [2, 4, 1, 3, 0] and a period of 5
for multiples of 2 in base 5. For
another example, the multiples of 3 are 3, 6, 9, 12, 15, 18, … , but the
remainders of each of these numbers after dividing by 5 are 3, 1, 4, 2, 0, 3, …
, making a cycle of [3, 1, 4, 2, 0] and a period of 5 for multiples of 3 in
base 5. The results for all the digits
are summarized in the table below.
digit
|
mult.
cycle
|
period
|
0
|
[0]
|
1
|
1
|
[1, 2, 3, 4]
|
4
|
2
|
[2, 4, 1, 3]
|
4
|
3
|
[3, 1, 4, 2]
|
4
|
4
|
[4, 3, 2, 1]
|
4
|
Last Digit Cycles of Multiples
in Base 5
This time,
all digits except 0 have a period of 5, which is the same as the base. This is because 5 is prime, which means all
the digits on the table are co-prime with it.
Additionally, once again all the cycles end with 0.
Another property
of the last digit cycles of multiples in base 5 is that if all the zeros are
taken out of the table, the leftover numbers form a Latin Square, a grid of
numbers where each number appears exactly once in each row and column, just like
in a Sudoku puzzle.
1
|
2
|
3
|
4
|
2
|
4
|
1
|
3
|
3
|
1
|
4
|
2
|
4
|
3
|
2
|
1
|
Last Digit Cycles of
Multiples in Base 5 without the
Zeroes Form a Latin
Square (a Sudoku Pattern)
This appears
to be true for all prime bases.
Last Digit Cycles of Exponents in Base 5
Last digit
cycles of exponents in different bases can be found once again by using
remainders. For example, the powers of 2
are 2, 4, 8, 16, 32, 64, … , but the remainders of each of these numbers after
dividing by 5 are 2, 4, 3, 1, 2, 4, … , making a cycle of [2, 4, 3, 1] and a
period of 4 for powers of 2 in base 5. For another example, the powers of 3 are 3, 9,
27, 81, 243, 729, … , but the remainders of each of these numbers after
dividing by 5 are 3, 4, 2, 1, 3, 4, … , making a cycle of [3, 4, 2, 1] and a
period of 4 for powers of 2 in base 5. The results for all the digits are
summarized in the table below.
digit
|
exp.
cycle
|
period
|
0
|
[0]
|
1
|
1
|
[1]
|
1
|
2
|
[2, 4, 3, 1]
|
4
|
3
|
[3, 4, 2, 1]
|
4
|
4
|
[4, 1]
|
2
|
Last Digit Cycles of
Exponents in Base 5
The period
of each digit is either 4 or a factor of 4 for exponents in base 5.
Using a Computer to Find Last Digit Cycles
There still remains
the question of why the full period of last digit cycles of exponents is 4 for
base 5, and 4 for base 10. Is there a
relationship between the period of last digit cycles of exponents and the base?
It is apparent that more data is needed
to answer this question, and a computer program is the quickest way to obtain
this data. The following is a computer
program written in Python that calculates last digit cycles.
01
|
# Last Digit Cycles
|
02
|
# Python 2.7.3
|
03
|
# To see the last digit cycles of multiples, type
"LDCM(b)",
|
04
|
# where b
is the base. For example,
"LDCM(10)".
|
05
|
# To see the last digit cycles of exponents, type
"LDCE(b)",
|
06
|
# where b
is the base. For example,
"LDCE(10)".
|
07
|
|
08
|
# Last Digit Cycle function
|
09
|
def LDC(b, o):
|
10
|
digits = []
|
11
|
cycle = []
|
12
|
maxperiod = 1
|
13
|
# go
through each digit in the base
|
14
|
for i in range(0, b):
|
15
|
digits.append([])
|
16
|
digits[i].append(i)
|
17
|
endperiod = False
|
18
|
lastdigit = i
|
19
|
#
cycle through the digits
|
20
|
while not endperiod:
|
21
|
# perform the correct operation
|
22
|
if o == "+":
|
23
|
nextdigit = (lastdigit + i) %
b
|
24
|
else:
|
25
|
nextdigit = (lastdigit * i) %
b
|
26
|
if nextdigit in digits[i]:
|
27
|
# if there is a repeated digit in the cycle,
|
28
|
# record it and exit out
|
29
|
cycle.append(len(digits[i]) -
digits[i].index(nextdigit))
|
30
|
if cycle[i] > maxperiod:
|
31
|
maxperiod = cycle[i]
|
32
|
if nextdigit != i:
|
33
|
digits[i].append("...")
|
34
|
endperiod = True
|
35
|
else:
|
36
|
# if there is not a repeated digit in the cycle,
|
37
|
# continue the cycle
|
38
|
digits[i].append(nextdigit)
|
39
|
lastdigit = nextdigit
|
40
|
#
print the results
|
41
|
print str(i) + " -> " +
str(cycle[i]) + " -> " + str(digits[i])
|
42
|
print "The largest period of base
" + str(b) + " is " + str(maxperiod)
|
43
|
|
44
|
#Last Digit Cycle of Multiples function
|
45
|
def LDCM(b):
|
46
|
LDC(b, "+")
|
47
|
|
48
|
#Last Digit Cycle of Exponents function
|
49
|
def LDCE(b):
|
50
|
LDC(b, "*")
|
For example,
to find the last digit cycles of exponents for base 10, type “LDCE(10)”:
>>
|
LDCE(10)
|
0 -> 1 -> [0]
1 -> 1 -> [1]
2 -> 4 -> [2, 4, 8, 6]
3 -> 4 -> [3, 9, 7, 1]
4 -> 2 -> [4, 6]
5 -> 1 -> [5]
6 -> 1 -> [6]
7 -> 4 -> [7, 9, 3, 1]
8 -> 4 -> [8, 4, 2, 6]
9 -> 2 -> [9, 1]
The largest period of base 10
is 4
|
Using the computer
program to quickly find the last digit cycles of exponents on different prime
number bases finally provides an obvious pattern for periods. In base 7, the period of each digit is either
6 or a factor of 6. In base 11, it is
10. In base 13, it is 12.
Solution
It appears
that if the base is a prime number, the period of the last digit cycles of
exponents is one less than its prime base.
By definition, the number of co-prime digits to a prime number is one
less than its value. For example, 5 is
co-prime with 1, 2, 3, and 4; 7 is co-prime with 1, 2, 3, 4, 5, and 6. So it appears that the period of the last digit cycles of exponents is the same as, or a
factor of, the number of digits that are co-prime with its base. Additionally, recall that a digit has a full
period in a last digit cycle of a multiple if and only if it is co-prime with
the base. Therefore, it would also
appear that the period of the last digit
cycles of exponents is the same as, or a factor of, the number of digits that
have a full period in last digit cycles of multiples in the same base. For example, there are 4 digits that have
full periods of 10 (the digits 1, 3, 7, and 9) in the multiples cycles of base
10, which means the maximum period for exponents in base 10 is also 4.
digit
|
multiples
cycle
|
period
|
digit
|
exp.
cycle
|
period
|
|
0
|
[0]
|
1
|
0
|
[0]
|
1
|
|
1
|
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
|
10
|
1
|
[1]
|
2
|
|
2
|
[2, 4, 6, 8, 0]
|
5
|
2
|
[2, 4, 8, 6]
|
4
|
|
3
|
[3, 6, 9, 2, 5, 8, 1, 4, 7, 0]
|
10
|
3
|
[3, 9, 7, 1]
|
4
|
|
4
|
[4, 8, 2, 6, 0]
|
5
|
4
|
[4, 6]
|
2
|
|
5
|
[5, 0]
|
2
|
5
|
[5]
|
1
|
|
6
|
[6, 2, 8, 4, 0]
|
5
|
6
|
[6]
|
1
|
|
7
|
[7, 4, 1, 8, 5, 2, 9, 6, 3, 0]
|
10
|
7
|
[7, 9, 3, 1]
|
4
|
|
8
|
[8, 6, 4, 2, 0]
|
5
|
8
|
[8, 4, 2, 6]
|
4
|
|
9
|
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
|
10
|
9
|
[9, 1]
|
2
|
Last Digit Cycles of
Multiples and Exponents in Base 10.
There are 4 Full
Periods of Multiples, so 4 is a Maximum Period for Exponents
The Swiss
mathematician Leonhard Euler showed many of these properties in the 18th
century, in what is now known as Euler’s theorem. Euler’s theorem states that if n is a
positive integer, and if a is an integer that is relatively prime to n, then aɸ(n) ≡ 1
mod n, where ɸ(n) is Euler’s totient
function, which counts the number of integers that are less than or equal to n
which are relatively prime to n. So in
base 10, n = 10, and the number of digits that are co-prime with 10 is ɸ(n) = 4, which becomes the maximum
period for exponents in this base. (More
information and proofs for Euler’s theorem can be found at here.)
Left: Leonhard Euler
(1707-1783)
Right: Robert Daniel
Carmichael (1879-1967)
Sometimes no
exponent cycles reach the expected maximum period, but rather only a factor of
the expected maximum period. These cases
are predicted by the reduced totient function, or the Carmichael function,
studied by the American mathematician Robert Daniel Carmichael in the 19th
and 20th centuries. (More
information on the Carmichael function can be found at here.) For example, in base 100, a fun base to examine
since it represents the last 2 digits of our base 10 numbering system, the
expected maximum period is 40, because 40 is the total number of positive
integers less than 100 that are co-prime with 100 (in other words, the total
number of positive integers less than 100 that end with the digits 1, 3, 7, and
9). However, the actual maximum period
is 20, a factor of 40. For example, the
powers of 13 in base 100 are 13, 13 · 13 = 169 ≡ 69 mod 100, 69 ·
13 = 897 ≡
97 mod 100, 97 · 13 = 1261 ≡ 61 mod 100, … , making a cycle of [13,
69, 97, 61, 93, 9, 17, 21, 73, 49, 37, 81, 53, 89, 57, 41, 33, 29, 77, 1] and a
period of 20. This means that any whole
number to the exponent of 20n + 1, where n is any integer (such as exponents 1,
21, 41, 61, … ), has the same last 2 digits as the original base.
Conclusion
Finding last
digit cycles of multiples and exponents produces all sorts of amazing patterns
and properties. Some of these patterns
and properties are obvious, especially for the last digit cycles of multiples. However, some of these patterns and
properties are less obvious, especially for the last digit cycles of exponents. This
article only scraped the surface of the topic of last digit cycles, but there
is still so much more to discover and prove!
