Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was doing some Math / CS work, and noticed a pattern in the last few digits of $2^n$.

I was working in Python, in case anyone is wondering.

The last digit is always one of 2, 4, 8, 6; and has a period of 4:

n = 1, str(2 ^ 1)[-1] = 2
n = 2, str(2 ^ 2)[-1] = 4
n = 3, str(2 ^ 3)[-1] = 8
n = 4, str(2 ^ 4][-1] = 6

I was interested, so I looked further. The second to last digit also has a repeating pattern, this time with a period of 20:

n =  2, str(2 ^  2)[-2] =  0
n =  3, str(2 ^  3)[-2] =  0
n =  4, str(2 ^  4)[-2] =  1
n =  5, str(2 ^  5)[-2] =  3
n =  6, str(2 ^  6)[-2] =  6
n =  7, str(2 ^  7)[-2] =  2
n =  8, str(2 ^  8)[-2] =  5
n =  9, str(2 ^  9)[-2] =  1
n = 10, str(2 ^ 10)[-2] =  2
n = 11, str(2 ^ 11)[-2] =  4
n = 12, str(2 ^ 12)[-2] =  9
n = 13, str(2 ^ 13)[-2] =  9
n = 14, str(2 ^ 14)[-2] =  8
n = 15, str(2 ^ 15)[-2] =  6
n = 16, str(2 ^ 16)[-2] =  3
n = 17, str(2 ^ 17)[-2] =  7
n = 18, str(2 ^ 18)[-2] =  4
n = 19, str(2 ^ 19)[-2] =  8
n = 20, str(2 ^ 20)[-2] =  7
n = 21, str(2 ^ 21)[-2] =  5

Is there a way I can generalize this so I can find any digit of any $2^n$ with out having to actually calculate the value of $2^n$?

If not, is there a way to find the period of the pattern, given an index (from the back of the integer) to look at?

share|improve this question

migrated from stackoverflow.com Dec 12 '11 at 21:26

This question came from our site for professional and enthusiast programmers.

    
Oh... how do I move it? –  Matthew D Dec 12 '11 at 21:14
    
@MatthewD flag it for a diamond mod, you can't do it yourself. –  Kevin Dec 12 '11 at 21:24
2  
Google found this: exploringbinary.com/… –  lhf Dec 12 '11 at 21:33
    
@lhf Thank you!!! (I'll be making a trip to the math department tomorrow for an explanation though...) –  Matthew D Dec 12 '11 at 21:45

1 Answer 1

The reason for the observer behavior is periodicity of $n \mapsto 2^n \bmod 10$, or $n \mapsto 2^n \bmod 10^k$ for any fixed $k$. This wikipedia article, as well as this, among others, math.SE answer are relevant.

Specifically, for a fixed positive integer $k$, $m \mapsto 2^m \bmod 10^k$ is quasi-periodic with period $p = \phi(5^k) = 4 \cdot 5^{k-1}$, i.e. for all $m \geq k$, $2^m \equiv 2^{m+p} \mod 10^k$.

Thus the last digit has period $4$, the one before last, has period $20$, the third one from the end has period $100$ and so on.

share|improve this answer
    
Let me see if I understand the first paragraph: when you said that $n \mapsto 2^n \bmod 10^k$, k is the index of the digit from the end of $2^n$? And you lost me completely in the second paragraph. I haven't had any number theory yet. –  Matthew D Dec 13 '11 at 1:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.