Tom: Very sweet proof indeed. I have a proof which is essentially the same as yours, but I use a bit of handwaving and a nice number theory result to make it a bit shorter and sweeter(?). This proof is more along the lines that led me to the original post. ---------------------------------------------------------- Now let s_b(n) = be the sum of base-b digits of n. Theorem: n! has the same number of trailing zeroes in bases 10 and 16 iff 0 <= s_5(n) - s_2(n) <= 3. Proof: Let [x] = floor(x). Let e_b(n) = the exponent of the largest power of b dividing n! We then have: The number of trailing zeroes of n! in base 10 = e_10(n) = e_5(n). The number of trailing zeroes of n! in base 16 = e_16(n) = [e_2(n)/4]. (Note: Your proof mentions and semi-justifies these assertions, I'll just leave them as user exercises). Now let n! end have the same number of trailing zeroes in bases 10 and 16. Then (1) e_5(n) = [e_2(n)/4] which gives 0 <= e_2(n)/4 - [e_2(n)/4] < 1 by definition of floor 0 <= e_2(n)/4 - e_5(n) < 1 by (1) 0 <= e_2(n) - 4*e_5(n) < 4 and since the expressions are integer, we conclude (2) 0 <= e_2(n) - 4*e_5(n) <= 3 For prime p, a number theory result gives: (3) e_p(n) = (n - s_p(n))/(p - 1) (Note: This little gem establishes the core connection between prime exponents in n! and digit sums. This connection is what originally convinced me of a connection between tailing zeroes in n! and digit sums. The sweetest (and biggest) part of your proof below goes toward proving (3) for the special case p = 5. A little cleaning up and generalization of your proof yields the standard proof of (3) for prime p. Since (3) was part of my mental junk collection, I was able to invoke it to bypass this part of your proof). Anyway, (3) gives e_2(n) = n - s_2(n) e_5(n) = (n - s_5(n))/4 Substituting these in (2) and a little simplification yields (4) 0 <= s_5(n) - s_2(n) <= 3 and the "if" part of the theorem is proved. Since all of the steps from (1) to (4) are reversible, we also get the "only if" part, and the theorem is proved.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Tomas Rokicki Sent: Tuesday, November 08, 2016 2:04 PM To: math-fun Subject: Re: [math-fun] peculiar sequence
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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun