3
$\begingroup$

Note: This question was inspired by this projectEuler problem, but I am not looking for a way to solve it.

Why is it that the last $n$ non-zero digits do not repeat themselves in a simple fashion. After all, lets say I am looking for the last non-zero digit. I will always be multiplying by the same set of numbers in the same order, (01-99) and so I would assume that since all of these numbers will be hit once for 100!, twice for 200!, three times for 300! and four times for 400!, the last digit of these numbers would be scalar multiples of each other (mod 10) but this is not the case.

I sense that I am making a simple logical error. What is it?

  • 0
    An interesting question. I know this is not quite an answer, though it is almost one - hence the comment: note that e.g. because 5 is greater than 4, (and 2) after the first few factorials knocking off the trailing zeros is eventually divisible by 4, and the relevant power of 2 increases as the factorial increases (so eventually divisible by 8, 16, 32 ...). This leads to a "thinning out" of possibilities as $n$ increases.2012-01-19
  • 0
    I don't really agree. The fact that it is divisible by eight just means that there are at least 3 zero's after any number. It tells me nothing about the lat non-zero digit.2012-01-19
  • 0
    quite different - the fact that powers of two accumulate faster than powers of five means that you get numbers which are successively divisible by 2, 4, 8, 16 etc even after dropping the zeros. Every multiple of 5 you pass adds a zero or more, and maybe lose a little ground, but the 2s win every time.2012-01-19
  • 0
    The answer may be in the references provided at http://oeis.org/A0089042012-01-20

1 Answers 1

2

The issue comes from not counting the "hidden" occurrences of digits in multiples of $5$, including the multiples of $10$. The digits $1$, $2$, $3$, $4$, $6$, $7$, $8$, $9$ repeat in a pleasant fashion, and if we forgot about the multiples of $5$ (including the multiples of $10$), we would get automatic periodicity. However, the $7$ that is hidden in $35$, and from the point of view of last digits, becomes $7\cdot 9$ on multiplication by $38$, is different from the $1$ that is hidden in $55$, and becomes $1\cdot 9$ on multiplication by $58$. More simply, $600$ and $700$ end in the same digit, but effectively for the last non-zero digit problem they are different.

This unfortunately does not prove that the last non-zero digits are not eventually periodic. It only shows why your reasonable first approach to showing periodicity does not work.

  • 0
    So you are saying that for 1000!, I should do 100!*10! and then take the last digits, and it will work out?2012-01-20
  • 0
    Sorry, have no time, but definitely not.2012-01-20
  • 0
    How does that not account for all of the numbers that only have one non-zero digit?2012-01-20
  • 0
    @soandos: There are several reasons. For example, $625$ is quite special, it sucks up four $2$'s. So not all chunks of $100$ are created equal. We can count the number of $2$'s sucked up by the ordinary simple multiples of $5$, but then we have to add those sucked up by numbers divisible by higher powers of $5$ ($25$ needs two, $50$ needs $1$, and so on). One can get an expression for this, but it is somewhat complicated. I have assigned the problem in the past. Already for $1000$ it takes some work.2012-01-20
  • 0
    This formula tells me how many 2's and fives are sucked up: $$\sum _{i=0}^k \left\lfloor \frac{n}{5^i}\right\rfloor$$ How can I combine this to make it work out right?2012-01-20
  • 0
    There are what look like good links to discussions of this in the OEIS entry referenced by Michael Lugo above. The details are lengthy but not terribly difficult. The formula you give is not quite right, since for example it counts the $5$ in $10$.2012-01-20
  • 0
    As it should, as there is now one trailing zero...2012-01-20
  • 0
    It looks as if the algorithm I have in mind is not the same as yours. For the last non-zero digit problem, $10$ makes no difference, while $5$, $15$, $50$ do.2012-01-20
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2265/discussion-between-soandos-and-andre-nicolas)2012-01-20