Distribution of 0 digits in factorial series
Large Factorials and the Distribution of '0' in base 10 digits.
- About the task
We can see that some features of factorial numbers (the series of numbers 1!, 2!, 3!, ...) come about because such numbers are the product of a series of counting numbers, and so those products have predictable factors. For example, all factorials above 1! are even numbers, since they have 2 as a factor. Similarly, all factorials from 5! up end in a 0, because they have 5 and 2 as factors, and thus have 10 as a factor. In fact, the factorial integers add another 0 at the end of the factorial for every step of 5 upward: 5! = 120, 10! = 3628800, 15! = 1307674368000, 16! = 20922789888000 and so on.
Because factorial numbers, which quickly become quite large, continue to have another terminal 0 on the right hand side of the number for every 5 increase in the factorial base number, one might think that the proportion of zeros in a base 10 factorial number might be close to 1/5. However, though the factorial products add another terminating 0 every 5, as the numbers become quite large, the number of digits in the factorial product expands exponentially, and the number above the terminating zeros tends toward 10% of each digit from 0 to 1, as the factorial becomes larger. Thus, as the factorials become larger, the proportion of 0 digits in the factorial products shifts slowly from around 1/5 toward 1/10, since the number of terminating zeros in n! increases only in proportion to n, whereas the number of digits of n! in base 10 increases exponentially.
- The task
Create a function to calculate the mean of the proportions of 0 digits out of the total digits found in each factorial product from 1! to N!. This proportion of 0 digits in base 10 should be calculated using the number as printed as a base 10 integer.
Example: for 1 to 6 we have 1!, 2!, 3!, 4!, 5!, 6!, or (1, 2, 6, 24, 120, 720), so we need the mean of (0/1, 0/1, 0/1, 0/2, 1/3, 1/3) = (2/3) (totals of each proportion) / 6 (= N), or 0.1111111...
Example: for 1 to 25 the mean of the proportions of 0 digits in the factorial products series of N! with N from 1 to 25 is 0.26787.
Do this task for 1 to N where N is in (100, 1000, and 10000), so, compute the mean of the proportion of 0 digits for each product in the series of each of the factorials from 1 to 100, 1 to 1000, and 1 to 10000.
- Stretch task
Find the N in 10000 < N < 50000 where the mean of the proportions of 0 digits in the factorial products from 1 to N permanently falls below 0.16. This task took many hours in the Python example, though I wonder if there is a faster algorithm out there.
Python
<lang python>def facpropzeros(N, verbose = True):
proportions = [0.0] * N fac, psum = 1, 0.0 for i in range(N): fac *= i + 1 d = list(str(fac)) psum += sum(map(lambda x: x == '0', d)) / len(d) proportions[i] = psum / (i + 1)
if verbose: print("The mean proportion of 0 in factorials from 1 to {} is {}.".format(N, psum / N))
return proportions
for n in [100, 1000, 10000]:
facpropzeros(n)
props = facpropzeros(47500, False) n = (next(i for i in reversed(range(len(props))) if props[i] > 0.16))
print("The mean proportion dips permanently below 0.16 at {}.".format(n + 2))
</lang>
- Output:
The mean proportion of 0 in factorials from 1 to 100 is 0.24675318616743216. The mean proportion of 0 in factorials from 1 to 1000 is 0.20354455110316458. The mean proportion of 0 in factorials from 1 to 10000 is 0.17300384824186707. The mean proportion dips permanently below 0.16 at 47332.
REXX
<lang rexx>/*REXX program computes the mean of the proportion of "0" digits a series of factorials.*/ parse arg $ /*obtain optional arguments from the CL*/ if $= | $="," then $= 100 1000 10000 /*not specified? Then use the default.*/
- = words($) /*the number of ranges to be used here.*/
numeric digits 100 /*increase dec. digs, but only to 100. */ big= word($, #); != 1 /*obtain the largest number in ranges. */
do i=1 for big /*calculate biggest ! using 100 digs.*/ != ! * i /*calculate the factorial of BIG. */ end /*i*/
if pos('E', !)>0 then do /*if its in exponential format, get EXP*/
parse var ! 'E' x /*parse the exponent from the number. */ numeric digits x+1 /*set the decimal digits to X plus 1.*/ end /* [↑] the +1 is for the dec. point.*/
title= ' mean proportion of zeros in the (decimal) factorial products for N' say ' N │'center(title, 80) /*display the title for the output. */ say '───────────┼'center("" , 80, '─') /* " a sep " " " */
do j=1 for #; n= word($, j) /*calculate some factorial ranges. */ p= 0dist(n) /* " the proportion of zeros. */ say center( commas(n), 11)'│' left(p/n, 75)... /*display the results for above range. */ end /*j*/
say '───────────┴'center("" , 80, '─') /*display a foot sep for the output. */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ 0dist: procedure; parse arg target; != 1; y= 0
do k=1 for target; != ! * k; z= countstr(0, !); y= y+ z/length(!) end /*k*/ return y</lang>
- output when using the default inputs:
N │ mean proportion of zeros in the (decimal) factorial products for N ───────────┼──────────────────────────────────────────────────────────────────────────────── 100 │ 0.2467531861674322177784158871973526991129407033266153063813195937196095976... 1,000 │ 0.2035445511031646356400438031711455302985741167890402203486699704599684047... 10,000 │ 0.1730038482418660531800366428930706156810278809057883361518852958446868172... ───────────┴────────────────────────────────────────────────────────────────────────────────
Wren
Very slow indeed, 10.75 minutes to reach N = 10,000. <lang ecmascript>import "/big" for BigInt import "/fmt" for Fmt
var fact = BigInt.one var sum = 0 System.print("The mean proportion of zero digits in factorials up to the following are:") for (n in 1..10000) {
fact = fact * n var bytes = fact.toString.bytes var digits = bytes.count var zeros = bytes.count { |b| b == 48 } sum = sum + zeros / digits if (n == 100 || n == 1000 || n == 10000) { Fmt.print("$,6d = $12.10f", n, sum / n) }
}</lang>
- Output:
The mean proportion of zero digits in factorials up to the following are: 100 = 0.2467531862 1,000 = 0.2035445511 10,000 = 0.1730038482