A Modular Exponential Sequence
A sequence a 1 , a 2 , a 3 , . . . is defined as
a n = 2 n ( m o d 1 0 0 ) .
It starts off as 2 , 4 , 8 , 1 6 , . . . . Find the last term before the sequence repeats.
This problem is based off Finn Hulse's problem, A Modular Recursion Sequence .
The answer is 52.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
This is nonsense. The sequence will never repeat!!!! Period..................................
Log in to reply
It is in modulo 100. Just take the last 2 digits.
Log in to reply
If there is no 2 in the next round, the sequence does not repeat. I knew 52 is the answer he was looking for but did not enter it. The question is wrong.
Log in to reply
@Hatim Zaghloul – Incorrect. It enters an infinite recursion with itself with repetition period 2 0 . This is still considered a repeat.
Log in to reply
@Josh Speckman – Partially repeats which is not the same thing.
Log in to reply
@Hatim Zaghloul – Look at it this way: The decimal 1 . 3 4 3 is still considered a repeating decimal, even though the 3 4 at the beginning does not repeat.
Log in to reply
@Josh Speckman – Good point. Because the last digits repeat:.this is by definition. If you are asked about the repeating sequence you will know which digits one is referring to. But to name a sequence and ask when it repeats is different. I just like accuracy.
The sequence starts with 2,4,8.... This sequence can never repeat it self. But it repetition starts with 4,8... I think the question is wrong or not properly coined. Correct me if I'm wrong.
It's another way, keep doubling the terms & you get to the answer
Cool beans!
Log in to reply
You know where Robert Fritz went? He's just about the same age as us but he's disappeared of the radar. Has he stopped going on Brilliant?
Log in to reply
No wait, he's just not posting problems and discussions.
Log in to reply
@Sharky Kesa – Yeah. He used to post tons of comments.
The sequence thus on writing will be 2, 4, 8,..., 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76,
52
, 4.
THUS 52 is the last term before sequence repeats.
Wow, what an awesome problem! I really enjoyed solving this. I really couldn't find a good way to do this other than brute force. I'd be really interested to see a good solution. So anyways, I just listed out each term. You see that after 52, the sequence restarts at 4. Something interesting to note, however, is that if you were to have known that the sequence would restart at 4, it would have been obvious that the term before it was either a 2, or a 52. It's obvious that the 2 can be ruled out, because the only two terms that could have been before it are 1 and 51, which are both odd and thus impossible. If somebody can find a more rigorous, neat approach, tag me! :D
You can directly conclude that the sequence starts to repeat at 4.
Hint: We almost want to apply Euler's Theorem, apart from the fact that g cd ( 2 , 1 0 0 ) = 1 .
Hint: Other than a 1 , all other terms are a multiple of 4.
Working modulo 4, we know that the sequence repeats after the second term. All terms are
0
(
m
o
d
4
)
.
Working modulo 25, since
g
cd
(
2
,
2
5
)
=
1
, Euler's Theorem tells us that the sequence is immediately repeating (and has a period length of
ϕ
(
2
5
)
=
2
0
). Since we previously had to discard the first term, hence this tells us that the last term of the sequence will be equal to
2
(
m
o
d
2
5
)
.
Hence it is
5
2
(
m
o
d
1
0
0
)
.
Log in to reply
Yeah, I thought the same. I wanted to apply Euler´s Theorem, but that fact stopped from doing so...
Log in to reply
I've updated my comment to show how to use Euler's Theorem here. Basically, identify the issue and deal with it separately.
Yeah, I realized that after the fact, though.
So Calvin, how can this problem be correct? The sequence never repeats. It is frustrating to even attempt to explain!!!!!!!!!!!!!!
Log in to reply
No dude, it repeats.
Log in to reply
@Finn Hulse – Where is the 2. The sequence never repeats. It partially repeats which, in mathematics, is not the same thing. The problem is very interesting but is worded wrong.
Log in to reply
@Hatim Zaghloul – It didn't say it had to repeat from the beginning, just when it starts doing the same thing.
Log in to reply
@Finn Hulse – It did not say that the sequence starts doing the same thing; it said repeats. The question is wrongly worded.
@Finn Hulse I have written a solution but it isn't exactly rigorous or neat but doesn't require brute force.
@Sharky Kesa Great problem! I'm glad that one of my ideas has branched into such a cool area of Number Theory. I'll probably write another one of these types of problems. :D
All we need to know is the first term that repeats. If the first term that repeats had been 2, the previous number had to be either 1 or 51, which are odd, so 2 can be ruled out. If the first term was 4, the previous term could be either 52 or 2. 2 is not possible as we previously saw but 52 is a possibility. If the first term was 8, the previous term could be either 4 or 54. If it were 4, then the sequence would have already started repeating but if the previous term was 54, then the term before that would have been either 27 or 77 which are impossible. If you keep on dong these steps, you find that the sequences starts to repeat at 4. The previous number has to be 52.