Factorial Zeroes
Factorial Zeroes
The factorial grows very fast. How many zeroes does a factorial have?
Here are some factorials from 1 to 130 in steps of 30.
In[]:=
Table[n!,{n,1,130,30}]
Out[]=
{1,8222838654177922817725562880000000,507580213877224798800856812176625227226004528988036003099405939480985600000000000000,135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000,809429852527344373968162284544935082997082306309701607045776233628497660426640521713391773997910182738287074185078904956856663439318382745047716214841147650721760223072092160000000000000000000000000000}
To count the number of zeroes at the end, we can count the numbers of 5.
In[]:=
FactorialZeroes//ClearAllFactorialZeroes[n_?IntegerQ]/;1<n:=Sum[Quotient[n,],{i,Floor[Log[5,n]]}]
i
5
How many zeroes does 403 have?
In[]:=
FactorialZeroes[403]
Out[]=
99
This function takes less time than this one.
In[]:=
FactorialZeroesThatDoesnTTakeLessTime[n_Integer]:=Length[Last[Split[IntegerDigits[n!]]]]
In[]:=
RepeatedTiming[FactorialZeroesThatDoesnTTakeLessTime[10000]]
Out[]=
{0.00670822,2499}
In[]:=
RepeatedTiming[FactorialZeroes[10000]]
Out[]=
{0.0000126805,2499}
The difference becomes more significant as the input grows.
In[]:=
RepeatedTiming[FactorialZeroesThatDoesnTTakeLessTime[100000]]
Out[]=
{0.11787,24999}
In[]:=
RepeatedTiming[FactorialZeroes[100000]]
Out[]=
{0.0000142718,24999}
Here’s how the other function works for 54.
First I find the digits of the factorial.
In[]:=
IntegerDigits[54!]
Out[]=
{2,3,0,8,4,3,6,9,7,3,3,9,2,4,1,3,8,0,4,7,2,0,9,2,7,4,2,6,8,3,0,2,7,5,8,1,0,8,3,2,7,8,5,6,4,5,7,1,8,0,7,9,4,1,1,3,2,2,8,8,0,0,0,0,0,0,0,0,0,0,0,0}
Then I make runs of the number’s digit.
In[]:=
Split[IntegerDigits[54!]]
Out[]=
{{2},{3},{0},{8},{4},{3},{6},{9},{7},{3,3},{9},{2},{4},{1},{3},{8},{0},{4},{7},{2},{0},{9},{2},{7},{4},{2},{6},{8},{3},{0},{2},{7},{5},{8},{1},{0},{8},{3},{2},{7},{8},{5},{6},{4},{5},{7},{1},{8},{0},{7},{9},{4},{1,1},{3},{2,2},{8,8},{0,0,0,0,0,0,0,0,0,0,0,0}}
Then I get the last sequence of 0s at the end.
In[]:=
Last[Split[IntegerDigits[54!]]]
Out[]=
{0,0,0,0,0,0,0,0,0,0,0,0}
And then I take the length.
In[]:=
Length[Last[Split[IntegerDigits[54!]]]]
Out[]=
12
When I was a student at the West Virginia 2018 State Math Field Day in 10th Grade at Marshall University there was a problem my team for Huntington High School had to solve together to find I think the number of zeroes in 2018! Find the answer:
In[]:=
FactorialZeroes[2018]
Out[]=
502
Brilliant Wiki page
Brilliant Wiki page
I will now use the page on Brilliant's Wiki for Trailing Number of Zeros
Count the number of trailing zeros in 15!
In[]:=
15!
Out[]=
1307674368000
In[]:=
FactorialZeroes[15]
Out[]=
3
In[]:=
IntegerExponent[18720,10]
Out[]=
1
In[]:=
IntegerExponent[22810000,10]
Out[]=
4
It’s pretty clear that if an integer is divisible by , then it has
k trailing zeros. Now consider the prime factorizations of integers and how this affects trailing zeros.
k
10
k trailing zeros. Now consider the prime factorizations of integers and how this affects trailing zeros.
I have an idea for an alternative way to find the number of zeroes.
In[]:=
FactorialZeroes2[n_Integer]:=IntegerExponent[n!,10]
Compare the timing for 200,000.
In[]:=
RepeatedTiming[FactorialZeroes[200000]]
Out[]=
{0.000012295,49998}
In[]:=
RepeatedTiming[FactorialZeroes2[200000]]
Out[]=
{0.0536955,49998}
In[]:=
RepeatedTiming[FactorialZeroesThatDoesnTTakeLessTime[200000]]
Out[]=
{0.250927,49998}
Brilliant states, “In light of the above theorem, the strategy for finding the trailing zeros of a factorial will revolve around the prime factorization of the factorial.”.
Give the prime factorization of 10! and find the number of trailing zeros of 10!
I can obtain this with FactorInteger.
In[]:=
FactorInteger[10!]
Out[]=
{{2,8},{3,4},{5,2},{7,1}}
Here is the prime factorization with a center-dot, cross, and circle-dot.
In[]:=
CenterDot@@Superscript@@@FactorInteger[10!]
Out[]=
8
2
4
3
2
5
1
7
In[]:=
Cross@@Superscript@@@FactorInteger[10!]
Out[]=
8
2
4
3
2
5
1
7
In[]:=
CircleDot@@Superscript@@@FactorInteger[10!]
Out[]=
8
2
4
3
2
5
1
7
The theorem is
Let f(n) give the number of trailing zeroes in the base ten representation of n!. Then
f(n)==+++…+
k
∑
i=1
n
i
5
n
5
n
2
5
n
3
5
n
k
5
k=⌊n⌋
log
5
The function Quotient[n,5] can be used instead of .
n
5
Example. Determine the number of trailing zeroes in 777!.
In[]:=
FactorialZeroes[777]
Out[]=
193
This is how I defined the function
In[]:=
?FactorialZeroes
Out[]=
In[]:=
FactorialZeroes[60]
Out[]=
14
Try it yourself. 2015! is multiplied by itself 2015 times as follows . Count how many trailing zeroes there are.
2015!×2015!×…×2015!
2015
I think it might be
I got it correct!.
I’m just curious what the fullform looks like
Example. Determine the number of trailing zeroes of 10005!
I’m going to add a function TrailingZeroes with the same definition as FactorialZeroes.
Try it yourself. For how many positive integral values of n does n! end with precisely 23 trailing zeroes?
The answer is 0.
There is 1 trailing zero. I think this is because
There’s an alternative way to compute the number of trailing zeroes.
I wonder if this is fast.
I think this new method is faster.
I like the new method better.
Trailing Zeroes in other bases
Trailing Zeroes in other bases
The first definition with sum of quotient although slower makes it easier to generalize to other bases
This might not always work but it works for find the number of trailing zeroes in the base-17 representation of 2017!, where 2017 is written in base 10.
The correct answer is 124.
This is where the new function breaks down. This output should be 24 not 2.
Maybe I need to greatest prime factor.
This works.
Now I can revise the definition.
This now returns the correct result of 24.
Find the smallest integer N such that when N! is written in base 12, it has 121 trailing zeroes. Enter your answer in base 6.
I think the number is 243.
I need to make sure this is the smallest number.
Then I need to write in base 6.
I didn’t get the problem right. Now I see why. This is where I could have used my alternative method with Split.
The right answer is 1052 in base 6.
Floor and Ceiling Functions
Floor and Ceiling Functions
Find the number of trailing zeroes in 19! 59! 158!
Before I embark on this challenge I think I’m going to consolidate the functions.
I add up the number of trailing zeroes. I can use a list because I gave the function the attribute Listable.
If x! has 112 trailing zeroes, what is the smallest possible integer x?
This function FromTrailingZeroesToSmallestNumber works even when there are no numbers whose factorial has a certain number of trailing zeroes such as how no factorial has 23 trailing zeroes. In that case, it returns the first number with more than 23 trailing zeroes.
end of scratch work subsubsection
end of scratch work subsubsection
How many trailing zeroes does 247! have?
Find the number of trailing zeroes in 303!+304!+305!.
I think to be safe here I want to list the digits.
Correct!
The answer is 76.
8% of people got this right.
Correct!
The answer is 76.
8% of people got this right.
Floor and Ceiling Functions: Level 2 Challenges
Floor and Ceiling Functions: Level 2 Challenges
Is this just the factorial zeroes because the floor of an integer is an integer?
Ideas for future research
Ideas for future research
Make a fast function based on quotient that works with different bases because right now the only function that works for trailing zeroes in different bases involves displaying all the IntegerDigits, splitting the list, taking the last run of digits, and calculating the length of the run of digits.