Howdy! The number of zeroes at the end of n! is equal in bases 10 and 16 iff 0 <= sum of base-5 digits of n - sum of base-2 digits of n <= 3. In other words, to see if 1033! (a large number) has the same number of zeros in base 10 and base 16, all we need to do is add the digits of 1033 in base 5 (13113, with a sum of 9) and compare it to the sum of the digits of 1033 in base 2 (10000001001, with a sum of 3), and we observe a difference of 6, which is not between 0 and 3 inclusive, so the number of zeros is different. Conversely, 1035 in base 5 is 13120 with a sum of digits of 7, and in binary it is 10000001011 with a sum of digits of 4, and 4-7 is in 0..3 inclusive, so 1035! has the same number of trailing zeros in both base 10 and 16. This was stated by David Wilson, and at first I did not believe it; it's so obviously false. Certainly there is a small counterexample. But I could not find one. So let's do the math. The number of 0s on the end of n! is determined by the power of 5 in n!, because the power of 2 in n! will always be greater than or equal to the power of 5 in n!. To calculate the power of 5 in n!, we calculate how many numbers from 1..n give us at least one power of 5, then add to that the number of numbers that give us at least two powers of 5, and so on and so forth, giving the expression #z_10(n!) = floor(n/5)+floor(n/25)+floor(n/125)... So it's almost a geometric sequence, except for all those floors. What is the difference between the geometric sequence and the actual sequence above? Well, if we denote the sequence of digits in base 5 as x5_0, x5_1, x5_2, ..., we see that: n/5 - floor(n/5) = x5_0/5 n/25 - floor(n/25) = (5*x5_1 + x5_0) / 25 = x5_1/5 + x5_0/25 n/125 - floor(n/125) = (25*x5_2 + 5*x5_1 + x5_0) / 125 = x5_2/5 + x5_1/25 + x5_0/125 ... So x5_0 shows up in this sequence of expressions as x5_0/5, x5_0/25, x5_0/125, and so forth, and so does every other digit of x in base 5. Thus, (x/5+x/25+x/125...) = #z_10(n!) + (x5_0/5+x5_0/25+x5_0/125...) + (x5_1/5+x5_1/25+x5_1/125...)... If we call the sum of all the digits in base 5 X5, then this is (x/5+x/25+x/125...) = #z_10(n!) + X5*(1/5+1/25+1/125...) We all know the sum of 1/5+1/25+1/125... is just 1/4, so this reduces to x/4 = #z_10(n!) + X5/4 exactly. Note in particular here that (x/4-X5/4) is always integral. For hexadecimal, the number of zeros in base 16 is the floor of the number of zeros in base 2, divided by 4. So we apply the argument above to base 2, and obtain x = #z_2(n!) + X2 Since #z_16(n!) = floor(#z_2(n!)/4), we find #z_16(n!) = floor((x-X2)/4) If #z_16(n!) = #z_10(n!), we must have floor((x-X2)/4) = x/4-X5/4 Removing the floor: x/4-X5/4 <= (x-X2)/4 < x/4-X5/4 + 1 Multiplying both sides by 4, we get x-X5 <= x-X2 < x-X5+4 and subtracting x-X5 from both sides: 0 <= X5-X2 < 4 -tom On Tue, Nov 8, 2016 at 9:59 AM, Joerg Arndt <arndt@jjj.de> wrote:
Nobody asked, shame! What is the proof?
Best regards, jj
P.S.: broke the thread in order to not bury this in old-ish messages.
* Tomas Rokicki <rokicki@gmail.com> [Sep 04. 2016 19:07]:
David Wilson's assertion that
The number of zeroes at the end of n! is equal in bases 10 and 16 iff
0 <= sum of base-5 digits of n - sum of base-2 digits of n <= 3.
has a very sweet proof! I admit I started looking for a counterexample before a proof, but I should have had more faith.
I'm omitting the proof because I don't want to spare anyone else the joy of discovery.
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --