Last Digit Cycles

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 17⁵ = 1419857 or 2²¹ = 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 18^th 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 19^th and 20^th 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!