A factorial problem
d n is the last nonzero digit of the decimal representation of n ! .
Is d n eventually periodic?
Clarification: d n is called "eventually periodic" if there exist k and n 0 such that d n + k = d n for all n ≥ n 0 .
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
@Freddie Hand Why is it you can say that d 1 0 a = d 1 0 a − 1 ?
Log in to reply
@Piero Sarti because d 1 0 a − 1 is the last nonzero digit of ( 1 0 a − 1 ) ! , and d 1 0 a is the last nonzero digit of ( 1 0 a ) ! = ( 1 0 a ) ( 1 0 a − 1 ) ! . Since we are multiplying by a power of ten ( 1 0 a ), the last nonzero digit remains unchanged.
Log in to reply
@Freddie Hand Ok I got everything. Great proof! I would've never thought of doing it like this. Sorry if I came off as rude earlier I really wasn't trying to, was generally interested in seeing a solution.
@Freddie Hand Why is it that 1 0 a ≡ 1 0 b ( m o d T ) for all positive integer T ? I also don't understand why d 2 ⋅ 1 0 a − 1 0 b − 1 = 5 merely by saying that 5 × 9 ends in 5. Are you implying that d 2 ⋅ 1 0 a − 1 0 b = 5 ?
Log in to reply
@donglin loo These are all good questions!
First, the claim that there exist integers a and b such that 1 0 a ≡ 1 0 b ( m o d T ) . This in fact follows directly from Euler's theorem- https://en.wikipedia.org/wiki/Euler%27s_theorem if you want to take a look.
Secondly, the last nonzero digit of ( 2 ⋅ 1 0 a − 1 0 b − 1 ) ! remains unchanged when it is multiplied by a number ending in 9 (from d 2 ⋅ 1 0 a − 1 0 b − 1 = d 2 ⋅ 1 0 a − 1 0 b ), which means the only possibility for the last nonzero digit is 5 .
PS I sometimes leave out small details like this for the reader to work out for themselves, because if one merely reads the solution, one will not absorb it as fully.
Log in to reply
Ah! Now I understand your solution. BTW, what a neat proof to justify the problem!
Well, this really got me thinking harder than most problems to follow all the steps you didn't over explain. Thank you.
For anyone else struggling, the proof relies on the fact that d k is never 5. But if the sequence is periodic, Freddie showed that would mean d k has to be 5 at some point. Freddie did this by showing that there has to be a place where d k = d k − 1 where the last non-zero digit of k is 9. Everything else is convenient number theory tricks to get there.
I dont understand how you concluded that 5 divides n! with a greater power than 2 does.
Log in to reply
That is the point! I was using proof by contradiction. By assuming that the sequence was eventually periodic, I reached the conclusion that 5 divided n! with a greater power than 2, which is of course untrue. This meant that the original assumption (that the sequence was eventually periodic) was wrong so the sequence is never periodic.
Let n ! = k ⋅ 1 0 j = k ⋅ 2 j 5 j where 10 does not divide k . If k is divisible by 5, then it is not divisible 2. Therefore, 5 j + 1 ∣ n ! but 2 j + 1 ∤ n ! . As Freddie states, this is not how factorials work. They are always most divisible by 2.
How can we assume that a = b (mod varphi(T)) without proving T is coprime with 10? I don't really get this part...
Log in to reply
Good catch! I forgot to put that bit in the solution.
Whilst it is true that not all a = b ( m o d φ ( T ) ) will satisfy the congruence, we can rely on the fact that a and b can be arbitrarily large. Then, working with the required congruence 1 0 b ( 1 0 a − b − 1 ) ≡ 0 ( m o d T ) , we know from Euler's theorem that there exist infinitely many a and b satisfying 1 0 a − b − 1 ≡ 0 m o d 2 k 1 5 k 2 T (where k 1 and k 2 are the powers of 2 and 5 in the prime factorisation of T ), and then by making b large enough (i.e. 1 0 b ≡ 0 ( m o d 2 k 1 5 k 2 ) ), this gives rise to the required congruence.
Log in to reply
Thanks, I just intuitively grasped the idea and just answered "no" , and I wanted some formal mathematical description for this. Thanks for contributing great problem. Btw, Level 2 seems ridiculous. This is at least 4 compared to others
Log in to reply
@Wonseok Shin – lol it's because it's multiple choice so a lot more people get it right
Log in to reply
@Freddie Hand – yeah...it is true. This implys a lot more than it seems.
Would you allow me to post this question and proof on my blog? I'm writing posts about math in Korean, and this seems great. It'll be written in Korean and I'll include a link to this page or wherever you want.
Assuming d n is eventually periodic:
The sequence from d 0 to d k − 1 is identical to that of d k to d 2 k − 1 . For this to be true, the last digit of n 1 must be equal to the last digit of n k + 1 : if the sequence of last digits of n are not the same, then given that the starting values d 0 and d k are identical, the following d n values will be different. This means k must be a multiple of 1 0 .
Within this sequence of length k , there is a subsequence of the numbers where n is a multiple of 1 0 . For d n to be periodic, these numbers must again match up between the two sequences. This means k must be a multiple of 1 0 0 .
For the subsequence of multiples of 1 0 0 to match between the two sequences, k must be a multiple of 1 0 0 0 . For the 1 0 0 0 's to match, k must be a multiple of 1 0 0 0 0 . At this point its pretty clear that k must be infinite to be periodic, and an infinitely long period is not a period at all.
We cannot immediately assume the last digit of n 1 is equal to the last digit of n k + 1 . All we know is that the last nonzero digit of n 1 ! is the same as the last nonzero digit of n k + 1 ! .
To give an example, 2 ! , 5 ! , 6 ! and 8 ! all have the same last nonzero digit, namely 2
Log in to reply
But for it to be periodic, the sequences must be the same. The only way the final digit can match if the last digit of n 1 and n k + 1 are different, is if n is not sequentially ordered.
The last digit of 2 ! × 3 is not the same as 8 ! × 9 . For them to match, we'd need 8 to be followed by either 3 or 8 . The only way we can make the last digits of d n to follow the same order, is for the last digits of n to follow their same order too.
Log in to reply
I don't think that your argument take fully into account the "last non-zero" part of the question. You could have d n = d n + k and d n + 1 = d n + 1 + k without k being a multiple of 10 as you would not always look at the same digit in all numbers. but for each one at its own last non-zero digit.
To give you a concrete example, with a period of k = 3 , we have d 4 = d 7 = 4 and d 5 = d 8 = 2 .
Log in to reply
@Thomas Lesgourgues – My argument is because of the "last non-zero" part. Consider:
There are only 9 possible sequences of values of d n , trailing from when n is a multiple of 1 0 (as the next values of n will end with 1 through 9 consecutively, and the initial d n can only start with numbers 1 through 9 ). Regardless of the rest of the number, the final digits will always follow the same sequence, based on the last digit in the starting number.
The only times in these sequences which match for more than just a couple numbers, either have a difference of 5 or 0 . This means the only way the two sequences can match for more than a couple numbers is if k is a multiple of 5 .
However, if k is a multiple of 5 but not 1 0 , when n reaches a number ending in 5 , n + k will be a multiple of 1 0 . Although sometimes this will match, the majority of the time the last non-zero digit of n + k will be a number that is not 5 , and thus will not produce matching end digits.
This means the only possible values for k must be a multiple of 1 0 .
Sorry that I missed this step in my thought process out in my original answer.
Log in to reply
@Binky Mh – I believe you have the right ideas to form a full solution, but it might be very difficult to formulate. It seems intuitively that since one is multiplying by different numbers (if k is not a multiple of 10) the sequences obtained will be different, but this is very hard to write up rigorously!
why is "k must be a multiple of 10"?
Log in to reply
If it is periodic, d 0 and d k Must end in the same number. d 1 and d k + 1 must also end in their own, same number. For this to be true, and continue being true as n increases, n 1 and n k + 1 must also end in the same number.
Consider as an example, a number ending in 2 multiplied by a number ending in 4 will always result in a number ending in 8 . Multiplying it with most other numbers will result in a different end number.
The exception would be that 2 multiplied by 9 results in 8 . However, continuing these two sequences will produce different numbers: a number ending in 8 multiplied by 5 always results in a number ending in 4 0 , whereas multiplying 8 with a multiple of 1 0 can result in many different numbers. Because of this, having a difference of 5 between the end numbers of n 1 and n k + 1 causes the end numbers of d n to desync upon reaching multiples of 1 0 .
For the end numbers of n 1 and n k + 1 to be the same, k must be a multiple of 10.
As 1 ! and 2 ! haven't a last zero-digit. For having a last zero-digit we need a 5 be multiplied by 2 , so after 5 ! all of the elements have a last zero-digit
The question quite clearly states 'last NONZERO digit'.
Log in to reply
And the reflexion is right that simple
Assume the sequence has period T after a certain point. We can find integers a > b > 0 (for simplicity we make these rather large) so that 1 0 a ≡ 1 0 b ( m o d T ) . This means that the terms d k and d k + ( 1 0 a − 1 0 b ) are the same (since T ∣ 1 0 a − 1 0 b ).
Clearly, d 1 0 a − 1 = d 1 0 a . Making use of the periodicity property (bearing in mind that a and b are rather large) we now have
d 2 ⋅ 1 0 a − 1 0 b − 1 = d 1 0 a − 1 = d 1 0 a = d 2 ⋅ 1 0 a − 1 0 b
Since ( 2 ⋅ 1 0 a − 1 0 b ) ! = ( 2 ⋅ 1 0 a − 1 0 b ) ( 2 ⋅ 1 0 a − 1 0 b − 1 ) ! and the last nonzero digit of 2 ⋅ 1 0 a − 1 0 b is 9 , we must have d 2 ⋅ 1 0 a − 1 0 b − 1 = 5 , because 5 × 9 ends in 5 . However, this implies that 5 divides n ! with a greater power than 2 does, which is impossible. Therefore, the sequence is never periodic.