wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 100 factorial
        
(Message started by: klbarrus on Jul 25^th, 2002, 4:58pm)

Title: 100 factorial
Post by klbarrus on Jul 25^th, 2002, 4:58pm

Every trailing zero means there is a factor of 10 in the product. 10 = 5*2, and there are a ton of 2's in 100!, so this boils down to counting the factors of 5 in 100!

5, 10, 15, 20... contribute 20 5's
25, 50, 75, 100... contribute 4 more (each has 5^2, so one extra not counted in the 5, 10, 15, 20... group)

That makes 20+4 = 24 factors of 5 = 24 factors of 10 (with a whole lot of extra 2's).

So 100! ends in 24 zeros.

Title: Re: 100 factorial
Post by wowbagger on Aug 29^th, 2002, 9:53am

24 is the correct answer on condition that we write down 100! in base 10, but we don't have to!

If we choose to write it in base b (>=2), the answer will depend on the prime factors of b and their multiplicities in 100!. This is due to the fact that every factor of b in 100! yields a trailing zero. So how many factors of b are there in 100! ?

Let
n = product_{i=1...Nn} pn_j^mn_j = 100!
p = product_{j=1...Nb} pb_j^mb_j

where pn_j and pb_j are the prime factors of n and b, respectively, with multiplicities mn_j and mb_j.
For simplicity of notation, let's order the first Nb prime factors of n such that pn_j=pb_j for j=1...Nb. If not all prime factors of b divide n, there are no trailing zeroes. Otherwise, the number nz of trailing zeroes is

nz(n,b) = min { [mn_j/mb_j] | j=1...Nb }

Here [x] denotes the largest integer not greater than x.

For b=10:
pb_1 = 2, mb_1 = 1, pb_2 = 5, mb_2 = 1
mn_1 = 97, mn_2 = 24
=> nz(100!,10) = min {[97/1], [24/1]} = min {97, 24} = 24

Another example:
n = 111!, b = 448
pb_1 = 2, mb_1 = 6, pb_2 = 7, mb_2 = 1
mn_1 = 105, mn_2 = 17
=> nz(111!,448) = min {[105/6], [17/1]} = min {[17.5], 17} = 17
As you can see, in base 896, 111! would have two trailing zeroes less (105/7=15).

One last remark: As the problem doesn't prescribe any particular base, one can easily arrange for the answer "zero" by choosing an appropriate base b_0. If you can do so, I think you got the general concept.

Title: Re: 100 factorial
Post by oliver on Sep 5^th, 2002, 2:49pm

Quote:

One last remark: As the problem doesn't prescribe any particular base, one can easily arrange for the answer "zero" by choosing an appropriate base b_0. If you can do so, I think you got the general concept.

b_0 = 100! + 1

Have I got the concept? ;D ;D ;D

Title: Re: 100 factorial
Post by wowbagger on Sep 6^th, 2002, 2:35am

Yep, that b_0 works!

However, it's not "optimal" in the sense that it is a bit, um, large. I know I didn't say anything about b_0 having to be small.

So let's make it (at least a bit) more interesting:
You should know by now what property b_0 must have to qualify. So what's the smallest value possible?

Title: Re: 100 factorial
Post by oliver on Sep 6^th, 2002, 5:01am

Excuse my little joke, wowbagger, I knew that wasn't the answer you're on to.
I'll wait if someone else comes up with an answer before spoiling your riddle.

Title: Re: 100 factorial
Post by James Fingas on Sep 6^th, 2002, 6:50am

b_0 = 1?

Title: Re: 100 factorial
Post by wowbagger on Sep 6^th, 2002, 7:07am

on 08/29/02 at 09:53:47, wowbagger wrote:

[...] If we choose to write it in base b (>=2), [...]

Hmm, how do you write numbers other than zero in base 1?

Title: Re: 100 factorial
Post by S. Owen on Sep 6^th, 2002, 7:45am

on 09/06/02 at 02:35:30, wowbagger wrote:

So let's make it (at least a bit) more interesting:
You should know by now what property b_0 must have to qualify. So what's the smallest value possible?

b₀ must not evenly divide 100! (that 100 is in base 10) in order for there to be no trailing zeroes in the base b₀ representation of it. The smallest possible value would be 101 then, since everything <= 100 divides 100!. And 101 works for sure, as it is prime. So the smallest b₀ is 101, yes?

Title: Re: 100 factorial
Post by wowbagger on Sep 6^th, 2002, 8:15am

Exactly. :)

Title: Re: 100 factorial
Post by James Fingas on Sep 6^th, 2002, 10:26am

The reason that b_0 = 1 works is that there's only the '0' digit.

Since there's no other digits to worry about, there can't be any "trailing" zeros! What could they be trailing?

Title: Re: 100 factorial
Post by S. Owen on Sep 6^th, 2002, 11:29am

on 09/06/02 at 10:26:35, James Fingas wrote:

... there's only the '0' digit.

... which is also why you can't represent 100! in base 1, as wowbagger pointed out. I'd say the question presupposes a base in which one can represent 100!.

Title: Re: 100 factorial
Post by James Fingas on Sep 6^th, 2002, 11:53am

I think I'll patent base-1 arithmetic because it's so easy to do! And so what if you can't represent 100! in base-1. When's the last time you needed a number like that?

Title: Re: 100 factorial
Post by S. Owen on Sep 6^th, 2002, 12:01pm

It came up in a riddle I heard once...

Title: Re: 100 factorial
Post by NickH on Sep 6^th, 2002, 1:29pm

How many trailing zeroes are there in the (base 10) representation of (10^100)! ?

Title: Re: 100 factorial
Post by James Fingas on Sep 6^th, 2002, 1:49pm

NickH,

Never satisfied, are you?

n = floor(10¹⁰⁰/5) + floor(10¹⁰⁰/5²) + ... + floor(10¹⁰⁰/5^{floor(100ln10/ln5)})

And that is what we call a messy answer

Title: Re: 100 factorial
Post by NickH on Sep 6^th, 2002, 3:23pm

It is messy indeed!

We CAN say that it is "approximately" (10^100)/4.

Title: Re: 100 factorial
Post by Chronos on Sep 6^th, 2002, 5:29pm

But isn't it reasonable to suppose that 100! is expressed in the same base as 100 is? That is to say, if you want to consider the problem in base n, then what you want is the number of trailing zeros in the base n representation of (n²)! .