Rosetta Code

Distribution of 0 digits in factorial series: Difference between revisions

Page Discussion

Distribution of 0 digits in factorial series (view source)

Revision as of 12:08, 8 February 2024

4,918 bytes added ,  3 months ago
Add C# implementation
(Add C# implementation)
 
(11 intermediate revisions by 7 users not shown)
Line 1:
{{draft task|Mathematics}}
 
Large Factorials and the Distribution of '0' in base 10 digits.
Line 41:
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.
 
=={{header|11l}}==
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F facpropzeros(n, verbose = 1B)
V proportions = [0.0] * n
V (fac, psum) = (BigInt(1), 0.0)
Line 60 ⟶ 59:
 
L(n) [100, 1000, 10000]
facpropzeros(n)</langsyntaxhighlight>
 
{{out}}
Line 70 ⟶ 69:
 
=== Base 1000 version ===
<langsyntaxhighlight lang="11l">F zinit()
V zc = [0] * 999
L(x) 1..9
Line 124 ⟶ 123:
print(‘The mean proportion dips permanently below 0.16 at ’first‘.’)
 
meanfactorialdigits()</langsyntaxhighlight>
 
{{out}}
Line 132 ⟶ 131:
The mean proportion of zero digits in factorials to 10000 is 0.173003848
The mean proportion dips permanently below 0.16 at 47332.
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">su: 0.0
f: 1
lim: 100
loop 1..10000 'n [
'f * n
str: to :string f
'su + (enumerate str 'c -> c = `0`) // size str
if n = lim [
print [n ":" su // n]
'lim * 10
]
]</syntaxhighlight>
 
{{out}}
 
<pre>100 : 0.2467531861674322
1000 : 0.2035445511031646
10000 : 0.1730038482418671</pre>
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Numerics;
 
public class DistributionInFactorials
{
public static void Main(string[] args)
{
List<int> limits = new List<int> { 100, 1_000, 10_000 };
foreach (int limit in limits)
{
MeanFactorialDigits(limit);
}
}
 
private static void MeanFactorialDigits(int limit)
{
BigInteger factorial = BigInteger.One;
double proportionSum = 0.0;
double proportionMean = 0.0;
 
for (int n = 1; n <= limit; n++)
{
factorial = factorial * n;
string factorialString = factorial.ToString();
int digitCount = factorialString.Length;
long zeroCount = factorialString.Split('0').Length - 1;
proportionSum += (double)zeroCount / digitCount;
proportionMean = proportionSum / n;
}
 
string result = string.Format("{0:F8}", proportionMean);
Console.WriteLine("Mean proportion of zero digits in factorials from 1 to " + limit + " is " + result);
}
}
</syntaxhighlight>
{{out}}
<pre>
Mean proportion of zero digits in factorials from 1 to 100 is 0.24675319
Mean proportion of zero digits in factorials from 1 to 1000 is 0.20354455
Mean proportion of zero digits in factorials from 1 to 10000 is 0.17300385
</pre>
 
=={{header|C++}}==
{{trans|Phix}}
<langsyntaxhighlight lang="cpp">#include <array>
#include <chrono>
#include <iomanip>
Line 206 ⟶ 270:
std::cout << "The mean proportion dips permanently below 0.16 at " << first
<< ". (" << elapsed(t0) << "ms)\n";
}</langsyntaxhighlight>
 
{{out}}
Line 221 ⟶ 285:
{{libheader|Go-rcu}}
Timings here are 2.8 seconds for the basic task and 182.5 seconds for the stretch goal.
<langsyntaxhighlight lang="go">package main
 
import (
Line 261 ⟶ 325:
fmt.Println(" (stays below 0.16 after this)")
fmt.Printf("%6s = %12.10f\n", "50,000", sum / 50000)
}</langsyntaxhighlight>
 
{{out}}
Line 276 ⟶ 340:
{{trans|Phix}}
Much quicker than before with 10,000 now being reached in 0.35 seconds and the stretch goal in about 5.5 seconds.
<langsyntaxhighlight lang="go">package main
 
import (
Line 363 ⟶ 427:
fmt.Println(" (stays below 0.16 after this)")
fmt.Printf("%6s = %12.10f\n", "50,000", total/50000)
}</langsyntaxhighlight>
 
{{out}}
<pre>
Same as 'brute force' version.
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
 
import java.math.BigInteger;
import java.util.List;
 
public final class DistributionInFactorials {
 
public static void main(String[] aArgs) {
List<Integer> limits = List.of( 100, 1_000, 10_000 );
for ( Integer limit : limits ) {
meanFactorialDigits(limit);
}
}
private static void meanFactorialDigits(Integer aLimit) {
BigInteger factorial = BigInteger.ONE;
double proportionSum = 0.0;
double proportionMean = 0.0;
for ( int n = 1; n <= aLimit; n++ ) {
factorial = factorial.multiply(BigInteger.valueOf(n));
String factorialString = factorial.toString();
int digitCount = factorialString.length();
long zeroCount = factorialString.chars().filter( ch -> ch == '0' ).count();
proportionSum += (double) zeroCount / digitCount;
proportionMean = proportionSum / n;
}
String result = String.format("%.8f", proportionMean);
System.out.println("Mean proportion of zero digits in factorials from 1 to " + aLimit + " is " + result);
}
 
}
</syntaxhighlight>
{{ out }}
<pre>
Mean proportion of zero digits in factorials from 1 to 100 is 0.24675319
Mean proportion of zero digits in factorials from 1 to 1000 is 0.20354455
Mean proportion of zero digits in factorials from 1 to 10000 is 0.17300385
</pre>
 
Line 378 ⟶ 484:
 
'''From BigInt.jq'''
<syntaxhighlight lang="jq">
<lang jq>
# multiply two decimal strings, which may be signed (+ or -)
def long_multiply(num1; num2):
Line 420 ⟶ 526:
else mult($a1[1]; $a2[1]) | adjustsign( $a1[0] * $a2[0] )
end;
</syntaxhighlight>
</lang>
'''The task'''
<syntaxhighlight lang="jq">
<lang jq>
def count(s): reduce s as $x (0; .+1);
 
Line 446 ⟶ 552:
 
# The task:
100, 1000, 10000 | meanfactorialdigits</langsyntaxhighlight>
{{out}}
<pre>
Line 453 ⟶ 559:
Mean proportion of zero digits in factorials to 10000 is 0.17300384824186707; goal (0.16) unmet.
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">function meanfactorialdigits(N, goal = 0.0)
factoril, proportionsum = big"1", 0.0
for i in 1:N
Line 476 ⟶ 581:
 
@time meanfactorialdigits(50000, 0.16)
</langsyntaxhighlight>{{out}}
<pre>
Mean proportion of zero digits in factorials to 100 is 0.24675318616743216
Line 488 ⟶ 593:
=== Base 1000 version ===
{{trans|Pascal, Phix}}
<langsyntaxhighlight lang="julia">function init_zc()
zc = zeros(Int, 999)
for x in 1:9
Line 552 ⟶ 657:
meanfactorialzeros(100, false)
@time meanfactorialzeros()
</langsyntaxhighlight>{{out}}
<pre>
Mean proportion of zero digits in factorials to 100 is 0.24675318616743216
Line 560 ⟶ 665:
4.638323 seconds (50.08 k allocations: 7.352 MiB)
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[ZeroDigitsFractionFactorial]
ZeroDigitsFractionFactorial[n_Integer] := Module[{m},
m = IntegerDigits[n!];
Line 576 ⟶ 680:
means = Accumulate[N@fracs]/Range[Length[fracs]];
len = LengthWhile[Reverse@means, # < 0.16 &];
50000 - len + 1</langsyntaxhighlight>
{{out}}
<pre>0.111111
Line 584 ⟶ 688:
0.173004
47332</pre>
 
=={{header|Nim}}==
 
===Task===
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import strutils, std/monotimes
import bignum
 
Line 604 ⟶ 707:
lim *= 10
echo()
echo getMonoTime() - t0</langsyntaxhighlight>
 
{{out}}
Line 617 ⟶ 720:
At each step, we eliminate the trailing zeroes to reduce the length of the number and save some time. But this is not much, about 8%.
 
<langsyntaxhighlight Nimlang="nim">import strutils, std/monotimes
import bignum
 
Line 638 ⟶ 741:
 
echo "Permanently below 0.16 at n = ", first
echo "Execution time: ", getMonoTime() - t0</langsyntaxhighlight>
 
{{out}}
<pre>Permanently below 0.16 at n = 47332
Execution time: (seconds: 190, nanosecond: 215845101)</pre>
 
=={{header|Pascal}}==
Doing the calculation in Base 1,000,000,000 like in [[Primorial_numbers#alternative]].<BR>
The most time consuming is converting to string and search for zeros.<BR>
Therefor I do not convert to string.I divide the base in sections of 3 digits with counting zeros in a lookup table.
<langsyntaxhighlight lang="pascal">program Factorial;
{$IFDEF FPC} {$MODE DELPHI} {$Optimization ON,ALL} {$ENDIF}
uses
Line 836 ⟶ 938:
inc(i);
writeln('First ratio < 0.16 ', i:8,SumOfRatio[i]/i:20:17);
end.</langsyntaxhighlight>
{{out}}
<pre> 100 0.246753186167432
Line 844 ⟶ 946:
First ratio < 0.16 47332 0.15999999579985665
Real time: 4.898 s CPU share: 99.55 % // 2.67s on 2200G freepascal 3.2.2</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use ntheory qw/factorial/;
Line 855 ⟶ 956:
$f = factorial $_ and $sum += ($f =~ tr/0//) / length $f for 1..$n;
printf "%5d: %.5f\n", $n, $sum/$n;
}</langsyntaxhighlight>
{{out}}
<pre> 100: 0.24675
1000: 0.20354
10000: 0.17300</pre>
 
=={{header|Phix}}==
Using "string math" to create reversed factorials, for slightly easier skipping of "trailing" zeroes,
but converted to base 1000 and with the zero counting idea from Pascal, which sped it up threefold.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rfs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- reverse factorial(1) in base 1000</span>
Line 929 ⟶ 1,029:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The mean proportion dips permanently below 0.16 at %d. (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">first</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 940 ⟶ 1,040:
=== trailing zeroes only ===
Should you only be interested in the ratio of trailing zeroes, you can do that much faster:
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span>
Line 968 ⟶ 1,068:
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The mean proportion dips permanently below 0.07 at %d. (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">first</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 976 ⟶ 1,076:
The mean proportion dips permanently below 0.07 at 31549. (0.1s)
</pre>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def facpropzeros(N, verbose = True):
proportions = [0.0] * N
fac, psum = 1, 0.0
Line 1,000 ⟶ 1,099:
 
print("The mean proportion dips permanently below 0.16 at {}.".format(n + 2))
</langsyntaxhighlight>{{out}}
<pre>
The mean proportion of 0 in factorials from 1 to 100 is 0.24675318616743216.
Line 1,008 ⟶ 1,107:
</pre>
The means can be plotted, showing a jump from 0 to over 0.25, followed by a slowly dropping curve:
<langsyntaxhighlight lang="python">import matplotlib.pyplot as plt
plt.plot([i+1 for i in range(len(props))], props)
</syntaxhighlight>
</lang>
=== Base 1000 version ===
{{trans|Go via Phix via Pascal}}
<langsyntaxhighlight lang="python">def zinit():
zc = [0] * 999
for x in range(1, 10):
Line 1,074 ⟶ 1,173:
meanfactorialdigits()
print("\nTotal time:", time.perf_counter() - TIME0, "seconds.")
</langsyntaxhighlight>{{out}}
<pre>
The mean proportion of zero digits in factorials to 100 is 0.24675318616743216
Line 1,083 ⟶ 1,182:
Total time: 648.3583232999999 seconds.
</pre>
 
=={{header|Raku}}==
Works, but depressingly slow for 10000.
 
<syntaxhighlight lang="raku" perl6line>sub postfix:<!> (Int $n) { ( constant factorial = 1, 1, |[\*] 2..* )[$n] }
sink 10000!; # prime the iterator to allow multithreading
 
Line 1,096 ⟶ 1,194:
,1000
,10000
).map: -> \n { "{n}: {([+] (^n).map: *.&zs) / n}" }</langsyntaxhighlight>
{{out}}
<pre>100: 0.24675318616743216
Line 1,102 ⟶ 1,200:
10000: 0.17300384824186605
</pre>
 
=={{header|REXX}}==
<langsyntaxhighlight 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.*/
Line 1,134 ⟶ 1,231:
do k=1 for z; != ! * k; y= y + countstr(0, !) / length(!)
end /*k*/
return y/z</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 1,144 ⟶ 1,241:
───────────┴────────────────────────────────────────────────────────────────────────────────
</pre>
 
=={{header|Rust}}==
{{trans|Phix}}
<langsyntaxhighlight lang="rust">fn init_zc() -> Vec<usize> {
let mut zc = vec![0; 1000];
zc[0] = 3;
Line 1,232 ⟶ 1,328:
duration.as_millis()
);
}</langsyntaxhighlight>
 
{{out}}
Line 1,240 ⟶ 1,336:
Mean proportion of zero digits in factorials to 10000 is 0.1730038482. (149ms)
The mean proportion dips permanently below 0.16 at 47332. (4485ms)
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">[100, 1000, 10_000].each do |n|
v = 1
total_proportion = (1..n).sum do |k|
v *= k
digits = v.digits
Rational(digits.count(0), digits.size)
end
puts "The mean proportion of 0 in factorials from 1 to #{n} is #{(total_proportion/n).to_f}."
end</syntaxhighlight>
{{out}}
<pre>The mean proportion of 0 in factorials from 1 to 100 is 0.24675318616743222.
The mean proportion of 0 in factorials from 1 to 1000 is 0.20354455110316463.
The mean proportion of 0 in factorials from 1 to 10000 is 0.17300384824186604.
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func mean_factorial_digits(n, d = 0) {
 
var v = 1
var total = 0.float
 
for k in (1..n) {
v *= k
total += v.digits.count(d)/v.len
}
 
total / n
}
 
say mean_factorial_digits(100)
say mean_factorial_digits(1000)
say mean_factorial_digits(10000)</syntaxhighlight>
{{out}}
<pre>
0.246753186167432217778415887197352699112940703327
0.203544551103164635640043803171145530298574116789
0.173003848241866053180036642893070615681027880906
</pre>
 
Line 1,247 ⟶ 1,381:
{{libheader|Wren-fmt}}
Very slow indeed, 10.75 minutes to reach N = 10,000.
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt
import "./fmt" for Fmt
 
var fact = BigInt.one
Line 1,262 ⟶ 1,396:
Fmt.print("$,6d = $12.10f", n, sum / n)
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,275 ⟶ 1,409:
{{trans|Phix}}
Around 60 times faster than before with 10,000 now being reached in about 10.5 seconds. Even the stretch goal is now viable and comes in at 5 minutes 41 seconds.
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
 
var rfs = [1] // reverse factorial(1) in base 1000
Line 1,340 ⟶ 1,474:
Fmt.write("$,6d = $12.10f", first, firstRatio)
System.print(" (stays below 0.16 after this)")
Fmt.print("$,6d = $12.10f", 50000, total/50000)</langsyntaxhighlight>
 
{{out}}
Aspen138
337

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/313089...354862"