Patterns in the Last Digits of the Positive Powers of Two

http://www.exploringbinary.com/patterns-in-the-last-digits-of-the-positive-powers-of-two/


The positive powers of two — 2, 4, 8, 16, 32, 64, 128, 256, … — follow an obvious repeating pattern in their ending digit: 2, 4, 8, 6, 2, 4, 8, 6, … . This cycle of four digits continues forever. There are also cycles beyond the last digit — in the last m digits in fact — in the powers of two from 2m on. For example, the last two digits repeat in a cycle of length 20 starting with 04, and the last three digits repeat in a cycle of length 100 starting with 008.

In this article, I will show you why these cycles exist, how long they are, how they are expressed mathematically, and how to visualize them.

Cycle in the Last Digit

The last digit — the ones place — of a decimal integer d is the remainder of the division d/10. Equivalently, the last digit is the result of the operation d mod 10, when following the convention that the least nonnegative value — the common residue — is returned. Modular arithmetic, combined with iterative generation of the positive powers of two, allows us to show the cycle in the last digit:

  1. \mbox{\footnotesize{\displaystyle{2^1 \equiv \textbf{2} \pmod{10}}}}
  2. \mbox{\footnotesize{\displaystyle{2^2 \equiv 2^1 \cdot 2 \equiv 2 \cdot 2 \equiv \textbf{4} \pmod{10}}}}
  3. \mbox{\footnotesize{\displaystyle{2^3 \equiv 2^2 \cdot 2 \equiv 4 \cdot 2 \equiv \textbf{8} \pmod{10}}}}
  4. \mbox{\footnotesize{\displaystyle{2^4 \equiv 2^3 \cdot 2 \equiv 8 \cdot 2 \equiv \textbf{6} \pmod{10}}}}
  5. \mbox{\footnotesize{\displaystyle{2^5 \equiv 2^4 \cdot 2 \equiv 6 \cdot 2 \equiv \textbf{2} \pmod{10}}}}
  6. \mbox{\footnotesize{\displaystyle{2^6 \equiv 2^5 \cdot 2 \equiv 2 \cdot 2 \equiv \textbf{4} \pmod{10}}}}

We start with 2, compute it mod 10, multiply that result by 2, compute it mod 10, etc. From this it’s clear the pattern will repeat, once a previous result — 2 in this case, at step 5 — is obtained. This shows that the numbers 2n, n ≥ 1, cycle through the four ending digits 2, 4, 8, and 6.

The cycle implies that powers of two with the same ending digit are related, their exponents differing by a multiple of four:

  • Ends in 2: 21, 25, 29, 213, 217, … .
  • Ends in 4: 22, 26, 210, 214, 218, … .
  • Ends in 8: 23, 27, 211, 215, 219, … .
  • Ends in 6: 24, 28, 212, 216, 220, … .

You can express these relationships more succinctly using the laws of exponents, showing explicitly that the ending digit of the first four positive powers of two determine the ending digit of all positive powers of two:

  • Ends in 2: 21·24k, or 21+4k, k ≥ 0.
  • Ends in 4: 22·24k, or 22+4k, k ≥ 0.
  • Ends in 8: 23·24k, or 23+4k, k ≥ 0.
  • Ends in 6: 24·24k, or 24+4k, k ≥ 0.

You can also relate the positive powers of two to their ending digits based on their exponents (n) mod 4:

  • Ends in 2: \mbox{\footnotesize{\displaystyle{n \equiv 1 \pmod{4}}}}
  • Ends in 4: \mbox{\footnotesize{\displaystyle{n \equiv 2 \pmod{4}}}}
  • Ends in 8: \mbox{\footnotesize{\displaystyle{n \equiv 3 \pmod{4}}}}
  • Ends in 6: \mbox{\footnotesize{\displaystyle{n \equiv 0 \pmod{4}}}}

This gives an easy way to determine the last digit of any positive power of two. For example, the last digit of 2319 is 8, since \mbox{\footnotesize{\displaystyle{319 \equiv 3 \pmod{4}}}}.

Cycle in the Last Digit of 2n, n≥1
Power of Two (k ≥ 0) Exponent (mod 4) Last Digit
21+4k 1 2
22+4k 2 4
23+4k 3 8
24+4k 0 6

In summary, the table says that if \mbox{\footnotesize{\displaystyle{x \equiv y \pmod{4}}}}, \mbox{\footnotesize{\displaystyle{2^x \equiv 2^y \pmod{10}}}}.

Cycle in the Last Two Digits

A similar analysis, but using mod 100, shows that the last two digits of the powers of two, starting at 22, cycle with a period of 20:

Cycle in the Last Two Digits of 2n, n≥2
Power of Two (k ≥ 0) Exponent (mod 20) Last 2 Digits
22+20k 2 04
23+20k 3 08
24+20k 4 16
25+20k 5 32
26+20k 6 64
27+20k 7 28
28+20k 8 56
29+20k 9 12
210+20k 10 24
211+20k 11 48
212+20k 12 96
213+20k 13 92
214+20k 14 84
215+20k 15 68
216+20k 16 36
217+20k 17 72
218+20k 18 44
219+20k 19 88
220+20k 0 76
221+20k 1 52

Cycle in the Last Three Digits

To determine the cycle in the last three digits, repeat the same process using mod 1000. It shows that the powers of two, starting at 23, cycle with a period of 100:

Cycle in the Last Three Digits of 2n, n≥3
Power of Two (k ≥ 0) Exponent (mod 100) Last 3 Digits
23+100k 3 008
24+100k 4 016
25+100k 5 032
26+100k 6 064
27+100k 7 128
28+100k 8 256
29+100k 9 512
210+100k 10 024
211+100k 11 048
212+100k 12 096
213+100k 13 192
214+100k 14 384
215+100k 15 768
216+100k 16 536
217+100k 17 072
218+100k 18 144
219+100k 19 288
220+100k 20 576
221+100k 21 152
222+100k 22 304
223+100k 23 608
224+100k 24 216
225+100k 25 432
226+100k 26 864
227+100k 27 728
228+100k 28 456
229+100k 29 912
230+100k 30 824
231+100k 31 648
232+100k 32 296
233+100k 33 592
234+100k 34 184
235+100k 35 368
236+100k 36 736
237+100k 37 472
238+100k 38 944
239+100k 39 888
240+100k 40 776
241+100k 41 552
242+100k 42 104
243+100k 43 208
244+100k 44 416
245+100k 45 832
246+100k 46 664
247+100k 47 328
248+100k 48 656
249+100k 49 312
250+100k 50 624
251+100k 51 248
252+100k 52 496
253+100k 53 992
254+100k 54 984
255+100k 55 968
256+100k 56 936
257+100k 57 872
258+100k 58 744
259+100k 59 488
260+100k 60 976
261+100k 61 952
262+100k 62 904
263+100k 63 808
264+100k 64 616
265+100k 65 232
266+100k 66 464
267+100k 67 928
268+100k 68 856
269+100k 69 712
270+100k 70 424
271+100k 71 848
272+100k 72 696
273+100k 73 392
274+100k 74 784
275+100k 75 568
276+100k 76 136
277+100k 77 272
278+100k 78 544
279+100k 79 088
280+100k 80 176
281+100k 81 352
282+100k 82 704
283+100k 83 408
284+100k 84 816
285+100k 85 632
286+100k 86 264
287+100k 87 528
288+100k 88 056
289+100k 89 112
290+100k 90 224
291+100k 91 448
292+100k 92 896
293+100k 93 792
294+100k 94 584
295+100k 95 168
296+100k 96 336
297+100k 97 672
298+100k 98 344
299+100k 99 688
2100+100k 0 376
2101+100k 1 752
2102+100k 2 504

Cycle in the Last m Digits

The last m digits of a positive power of two are taken mod 10m, and have a cycle of period 4·5m-1, starting at 2m. (The proof involves techniques of number theory, and is beyond the scope of this article.)

Cycle Length for Number of Ending Digits (1 to 10)
m Period (4·5m-1) Starts with
1 4 21
2 20 22
3 100 23
4 500 24
5 2500 25
6 12500 26
7 62500 27
8 312500 28
9 1562500 29
10 7812500 210

The periods grow very fast — exponentially — so it is impractical to list tables of ending digits for m greater than three.

Nesting of Cycles

The cycles in m digit, m-1 digit, m-2 digit, …, 1 digit endings can be viewed as nested, even though their starting points are staggered. You just have shift the starting points of the lesser digit cycles to make them coincide.

For example, one copy of the length 100 cycle of three digit endings has within it five copies of the length 20 cycle of two digit endings; one copy of the length 20 cycle of two digit endings has within it five copies of the length 4 cycle of one digit endings. This works when you view the one digit ending cycle as starting at 8 (shifted two positions), the two digit ending cycle as starting at 08 (shifted one position), and the three digit ending cycle as starting at 008 (not shifted).

The diagram below shows the nesting by shading every other occurrence of a cycle (the 100s place is fully shaded, because only 100 powers of two — one cycle of the last three ending digits — are shown).

Nested 1-3 Digit Ending Patterns in Powers of Two from 2^3 to 2^102

Nested 1-3 Digit Ending Patterns From 23 to 2102

Exploring Ending Digits with PARI/GP

I used PARI/GP to make some of the calculations above and to check my work. Here are three examples:

  • Print the first 20 powers of two that end in 2:
    ? for (i=0,19,print("2^",1+4*i,": ",2^(1+4*i)))
    2^1: 2
    2^5: 32
    2^9: 512
    2^13: 8192
    2^17: 131072
    2^21: 2097152
    2^25: 33554432
    2^29: 536870912
    2^33: 8589934592
    2^37: 137438953472
    2^41: 2199023255552
    2^45: 35184372088832
    2^49: 562949953421312
    2^53: 9007199254740992
    2^57: 144115188075855872
    2^61: 2305843009213693952
    2^65: 36893488147419103232
    2^69: 590295810358705651712
    2^73: 9444732965739290427392
    2^77: 151115727451828646838272
    
  • Print the cycle of the last two digits (the ‘%’ operator returns the remainder, which in effect is how we’re using modular arithmetic):
    ? for (i=2,21,print("2^",i," mod(100): ",2^i % 100))
    2^2 mod(100): 4
    2^3 mod(100): 8
    2^4 mod(100): 16
    2^5 mod(100): 32
    2^6 mod(100): 64
    2^7 mod(100): 28
    2^8 mod(100): 56
    2^9 mod(100): 12
    2^10 mod(100): 24
    2^11 mod(100): 48
    2^12 mod(100): 96
    2^13 mod(100): 92
    2^14 mod(100): 84
    2^15 mod(100): 68
    2^16 mod(100): 36
    2^17 mod(100): 72
    2^18 mod(100): 44
    2^19 mod(100): 88
    2^20 mod(100): 76
    2^21 mod(100): 52
    

    (Single-digit results have an implicit leading 0.)

  • Print the period of the last 1 to 10 digits:
    ? for (i=1,10,print(i,": ",4*5^(i-1)))
    1: 4
    2: 20
    3: 100
    4: 500
    5: 2500
    6: 12500
    7: 62500
    8: 312500
    9: 1562500
    10: 7812500
    
Dingbat

6 Responses to “Patterns in the Last Digits of the Positive Powers of Two”

  1. Carnival of Mathematics #59 « The Number Warrior Says:

    [...] Rick Regan of Exploring Binary finds patterns in the last digits of the positive powers of two. [...]

  2. David Bandel Says:

    I also noticed the digits of the powers of two cycled with a period growing by a factor of five per digit. Never thought to google the result.

    I proved it as well but I did it more simply using group theory. Starting from the assumption that the period didn’t multiply by five per digit I arrived at a non-commutative cyclic group. But we know that all cyclic groups are Abelian.

  3. Rick Regan Says:

    David,

    Yes, my proof is a little long, though I was happy the way it turned out (it took quite a bit of work to do). If your proof is simpler, I’d love to see it, or at least some more of the details.

    BTW, would your technique work for proving the cycle length of powers of five mod powers of ten? I rather liked how I did that one, with the recursive factoring of differences of squares.

  4. cherry blazo Says:

    How about the pattern of powers of nine?

  5. Rick Regan Says:

    I discuss powers of two and powers of five (in another article) because they are related to the binary representation of numbers. Any particular reason you are interested in powers of nine?

    (In any case you could work it out similarly: last digit cycle is 1, 9; last two digits cycle is 01, 09, 81, 29, 61, 49, 41, 69, 21, 89; … Note I started out with 90, so this covers nonnegative powers.)

  6. Kishor Biswas Says:

    what is the last digit of 7 to the power 73 and explain

Leave a Comment

(To reduce spam, cookies must be enabled)


css.php