2

This problem is from projecteuler problem 160. I am not looking for an answer or anything like that I just got stuck on some of the mathematics and am looking for some help. Instead of solving the problem as it is given I first tried to solve a simpler problem:

Let $f(N)$ be the function that assigns to $N$ the last non zero digit of $N!$. For instance $f(9) = f(10) = 8$. Now I was looking for some kind of recursive formula for $f(10^n)$ but got stuck. For notational convenienve, denote $\pi (n)$ to be the last non zero digit of a number $n$.

My thoughts are as follows: Note that $f(10)$ is the last non zero digit of $1\cdot 2\ldots\cdot 10$. Now $f(11)$ is given by

\begin{align} \pi(11\cdot (1\cdot 2\ldots\cdot 10))&=\pi[10\cdot (1\cdot 2\ldots\cdot 10) + 1\cdot 2\ldots\cdot 10]\\ &=\pi[ 1\cdot 2\ldots\cdot 10]\\ &= f(10). \end{align}

The second equality follows from the fact that the first term in square brackets is 10 times the second part, and thus cannot contribute to the last digit. Similarly $f(12)$ is equal to the last digit of $12 \cdot f(11)$ which is then equal to the last digit of $2\cdot f(11)$ which is 6. This is correct so far as $12!=479001600$. Continuing this line of reasoning it would follow that

\begin{align} f(19) &= \pi[(11\cdot 12\ldots\cdot 19)\cdot (1\cdot 2\ldots\cdot 10)]\\ &= \pi[(1\cdot 2\ldots\cdot 9)\cdot (1\cdot 2\ldots\cdot 9)]\\ &=\pi [(1\cdot 2\ldots\cdot 9)^2]\\ &=\pi (f(9)^2)\\ &= \pi (8^2)\\ &= 4. \end{align}

However, no such luck as $f(19)=2$, as can be seen by working out the actual factorial of 19. Can someone help me understand what is going on?

EDIT: One of the main reason I ask questions on Stackexchange is that it forcces me to write out clearly what I know and more often than not I will see where the mistake lies. I found one problem, namely that I mistakenly assumed that $\pi(a\cdot b) = \pi(\pi(a)\cdot \pi(b))$, which is not the case, particularly if $\pi(a)=2$ and $\pi(b)=5$. I feel like there is still something to salvage here though.

Thanks in advance for any help!

Slugger
  • 5,556

1 Answers1

0

Ignore all multiples of 5, since they add a 0 to the product. You just have to look at the final digit, so for $1\times 2\times 3\dots$ that would only be 1, 2, 3, 4, 6, 7, 8, 9, and then starting again with 1, 2... For the final digit of the product this quickly results in a repeating pattern.

Simon
  • 64
  • thanks for your answer, I was thinking about something along these lines. However, we have for instance that $f(10) = 8$, while the last digit of $10!/5$ is not 8. – Slugger Jun 15 '15 at 17:06
  • For $f(10)$ we would be fine if we leave out both 2 and 5 as they multiply to form 10, but that no longer works when we get above 10. – Slugger Jun 15 '15 at 17:07
  • Make sure to omit a $2$ for every $5$ you omit. – Ashkay Jun 15 '15 at 17:08
  • Oops.. there's also some extra factors 2 that you should take care of. For every 5 you're kind of using one factor 2 for the added 0, the remaining 2's contribute to the final digit. I solved it this way, but I kind of forgot the details. – Simon Jun 15 '15 at 17:09
  • Exactly but when we get above ten we cannot simply omit 12 and 15 for instance as they multiply to 180 which does change the last non zero digit, besides adding an extra zero digit. – Slugger Jun 15 '15 at 17:09
  • Yes, it's not quite as simple as this answer suggests. – TonyK Jun 15 '15 at 17:09
  • Maybe this helps: http://maths.wordpandit.com/finding-last-non-zero-digit-of-any-factorial/ – Simon Jun 15 '15 at 17:20