«
»

2012!

3rd October 2012, 08:24 pm

In what base does 2012! have more trailing zeros: base 15 or 16?

Explain why the result shouldn’t be too surprising.

Share:Facebooktwitterredditpinterestlinkedinmail
Category: Puzzles  |  Comment (RSS)  |  Trackback

9 Comments

  1. Code:

    Base 15 right? In order for a number to have 1 trailing 0 in base 15, it has to be divisible by 15. The number of trailing 0s should be the largest number n such that 15^n divides 2012! There are definitely more 3s than 5s in the prime factorization, so let’s estimate the number of 5s in it. 2012//5+2012//25+2012//125+2012//625=402+80+16+3=501. Now the number of trailing 0s for 2012! in base 16 would be the largest n such that 16^n divides 2012!. 2012//16+2012//256=125+7=132. Base 15 has almost 4 times the number of trailing 0s than base 16 does.

    3 October 2012, 10:40 pm

  2. Theo Johnson-Freyd:

    Since there are many more 3s than 5s, the number of trailing 0s in (2012!)_15 counts the number of 5s less than 2012. Base 16 counts 1/4 the number of 2s. If p is a prime, the number of ps in n! is estimated by n/(p-1). So to first order, the counts are the same, and a more careful count is required.

    The estimate n/(p-1) comes from estimating the floor of n/p^k by just ignoring the floor function. So the estimate is an over estimate every time n is not divisible by a power of p. Of course, this happens infinitely often, but most of the time it happens in the “tail” when p^k>n. This tail contributes 1/(p-1) to the sum, and so for our purposes is irrelevant. To get the correct count, then, requires counting finitely many overestimates.

    Since 20121.2. So if I have not made an error, there are more trailing zeros mood 15 than mod

    3 October 2012, 10:47 pm

  3. Theo Johnson-Freyd:

    Since there are many more 3s than 5s, the number of trailing 0s in (2012!)_15 counts the number of 5s less than 2012. Base 16 counts 1/4 the number of 2s. If p is a prime, the number of ps in n! is estimated by n/(p-1). So to first order, the counts are the same, and a more careful count is required.

    The estimate n/(p-1) comes from estimating the floor of n/p^k by just ignoring the floor function. So the estimate is an over estimate every time n is not divisible by a power of p. Of course, this happens infinitely often, but most of the time it happens in the “tail” when p^k>n. This tail contributes 1/(p-1) to the sum, and so for our purposes is irrelevant. To get the correct count, then, requires counting finitely many overestimates.

    Since 2012 is less than 5^5, there are for overestimates for the p=5 case, totaling 2/5+12/25+12/125+137/625~1.2. When p=2, the overestimates are 4/8+12/16+…, which is already more than 1.2. So if I have not made an error, there are more trailing zeros mod 15 than mod 16, but not by very many.

    3 October 2012, 10:54 pm

  4. alvarezp:

    Did you mean (2012!)_b or (2012_b)!? I assumed the first option. I think there are more zeros in base 16. Not sure how exactly I got these numbers, but I got 420 zeros for base 15 and 502 for base 16. For base 15 I did int(2012/5); for base 16 I did int[(2012/2 + 2012/4 + 2012/8 + 2012/16 + … + 2012/1024) / 4].

    4 October 2012, 1:36 am

  5. alvarezp:

    Looking a Code’s answer, I’d like to throw my estimation about base 15 away and use his. I stick to my estimation about base 16, though, so that leaves me with 501 vs 502.

    4 October 2012, 2:25 am

  6. Martin:

    They both have 501 zeroes. The number of factors 2 in n! is roughly n, the number of factors 5 in n! is roughly n/4. So the number of zeroes is roughly the same. I still find it surprising, that the numbers match. But, unsurprisingly, the same happens next year.

    4 October 2012, 9:40 am

  7. Oz:

    It is 501 for both (guess that was the point of asking if it’s ‘surprising’). Theo’s right that they agree to first order but turns out they agree exactly for 2012.
    (Code’s answer for 16 is wrong since 16 is not a prime number).
    The reason is that sum_{i=1}^infinity (1/2^i) = 4 * sum_{i=1}^infinity (1/5^i)

    4 October 2012, 9:58 am

  8. Per:

    Same answer as Os: The density of 5:s, times 4, is exactly the same as the 2:s.

    6 October 2012, 4:02 pm

  9. error:

    1

    1 November 2012, 5:05 am

Leave a comment