Author |
Topic: 100 factorial (Read 4230 times) |
|
klbarrus
Newbie
Posts: 29
|
 |
100 factorial
« on: Jul 25th, 2002, 4:58pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender: 
Posts: 727
|
|
Re: 100 factorial
« Reply #1 on: Aug 29th, 2002, 9:53am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 29th, 2002, 9:59am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
oliver
Newbie
Posts: 25
|
|
Re: 100 factorial
« Reply #2 on: Sep 5th, 2002, 2:49pm » |
Quote Modify
|
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? 
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
 |
Re: 100 factorial
« Reply #3 on: Sep 6th, 2002, 2:35am » |
Quote Modify
|
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?
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
oliver
Newbie
Posts: 25
|
|
Re: 100 factorial
« Reply #4 on: Sep 6th, 2002, 5:01am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 factorial
« Reply #5 on: Sep 6th, 2002, 6:50am » |
Quote Modify
|
b_0 = 1?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: 100 factorial
« Reply #6 on: Sep 6th, 2002, 7:07am » |
Quote Modify
|
on Aug 29th, 2002, 9:53am, wowbagger wrote:| [...] If we choose to write it in base b (>=2), [...] |
|
Hmm, how do you write numbers other than zero in base 1?
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: 100 factorial
« Reply #7 on: Sep 6th, 2002, 7:45am » |
Quote Modify
|
on Sep 6th, 2002, 2:35am, 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? |
|
b0 must not evenly divide 100! (that 100 is in base 10) in order for there to be no trailing zeroes in the base b0 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 b0 is 101, yes?
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: 100 factorial
« Reply #8 on: Sep 6th, 2002, 8:15am » |
Quote Modify
|
Exactly. 
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 factorial
« Reply #9 on: Sep 6th, 2002, 10:26am » |
Quote Modify
|
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?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: 100 factorial
« Reply #10 on: Sep 6th, 2002, 11:29am » |
Quote Modify
|
on Sep 6th, 2002, 10:26am, 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!.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 factorial
« Reply #11 on: Sep 6th, 2002, 11:53am » |
Quote Modify
|
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?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: 100 factorial
« Reply #12 on: Sep 6th, 2002, 12:01pm » |
Quote Modify
|
It came up in a riddle I heard once...
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 100 factorial
« Reply #13 on: Sep 6th, 2002, 1:29pm » |
Quote Modify
|
How many trailing zeroes are there in the (base 10) representation of (10^100)! ?
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 factorial
« Reply #14 on: Sep 6th, 2002, 1:49pm » |
Quote Modify
|
NickH,
Never satisfied, are you?
n = floor(10100/5) + floor(10100/52) + ... + floor(10100/5floor(100ln10/ln5))
And that is what we call a messy answer
|
| « Last Edit: Sep 6th, 2002, 1:51pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 100 factorial
« Reply #15 on: Sep 6th, 2002, 3:23pm » |
Quote Modify
|
It is messy indeed!
We CAN say that it is "approximately" (10^100)/4.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: 100 factorial
« Reply #16 on: Sep 6th, 2002, 5:29pm » |
Quote Modify
|
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 (n2)! .
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print