Distribution of 0 digits in factorial series: Difference between revisions
Distribution of 0 digits in factorial series (view source)
Revision as of 10:42, 5 October 2021
, 2 years agoAdded C++ and Rust solutions
Alextretyak (talk | contribs) (→{{header|11l}}: Base 1000 version) |
(Added C++ and Rust solutions) |
||
Line 132:
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|C++}}==
{{trans|Phix}}
<lang cpp>#include <array>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
auto init_zc() {
std::array<int, 1000> zc;
zc.fill(0);
zc[0] = 3;
for (int x = 1; x <= 9; ++x) {
zc[x] = 2;
zc[10 * x] = 2;
zc[100 * x] = 2;
for (int y = 10; y <= 90; y += 10) {
zc[y + x] = 1;
zc[10 * y + x] = 1;
zc[10 * (y + x)] = 1;
}
}
return zc;
}
template <typename clock_type>
auto elapsed(const std::chrono::time_point<clock_type>& t0) {
auto t1 = clock_type::now();
auto duration =
std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0);
return duration.count();
}
int main() {
auto zc = init_zc();
auto t0 = std::chrono::high_resolution_clock::now();
int trail = 1, first = 0;
double total = 0;
std::vector<int> rfs{1};
std::cout << std::fixed << std::setprecision(10);
for (int f = 2; f <= 50000; ++f) {
int carry = 0, d999, zeroes = (trail - 1) * 3, len = rfs.size();
for (int j = trail - 1; j < len || carry != 0; ++j) {
if (j < len)
carry += rfs[j] * f;
d999 = carry % 1000;
if (j < len)
rfs[j] = d999;
else
rfs.push_back(d999);
zeroes += zc[d999];
carry /= 1000;
}
while (rfs[trail - 1] == 0)
++trail;
d999 = rfs.back();
d999 = d999 < 100 ? (d999 < 10 ? 2 : 1) : 0;
zeroes -= d999;
int digits = rfs.size() * 3 - d999;
total += double(zeroes) / digits;
double ratio = total / f;
if (ratio >= 0.16)
first = 0;
else if (first == 0)
first = f;
if (f == 100 || f == 1000 || f == 10000) {
std::cout << "Mean proportion of zero digits in factorials to " << f
<< " is " << ratio << ". (" << elapsed(t0) << "ms)\n";
}
}
std::cout << "The mean proportion dips permanently below 0.16 at " << first
<< ". (" << elapsed(t0) << "ms)\n";
}</lang>
{{out}}
<pre>
Mean proportion of zero digits in factorials to 100 is 0.2467531862. (0ms)
Mean proportion of zero digits in factorials to 1000 is 0.2035445511. (1ms)
Mean proportion of zero digits in factorials to 10000 is 0.1730038482. (152ms)
The mean proportion dips permanently below 0.16 at 47332. (4598ms)
</pre>
Line 1,061 ⟶ 1,143:
10,000 │ 0.1730038482418660531800366428930706156810278809057883361518852958446868172...
───────────┴────────────────────────────────────────────────────────────────────────────────
</pre>
=={{header|Rust}}==
{{trans|Phix}}
<lang rust>fn init_zc() -> Vec<usize> {
let mut zc = vec![0; 1000];
zc[0] = 3;
for x in 1..=9 {
zc[x] = 2;
zc[10 * x] = 2;
zc[100 * x] = 2;
let mut y = 10;
while y <= 90 {
zc[y + x] = 1;
zc[10 * y + x] = 1;
zc[10 * (y + x)] = 1;
y += 10;
}
}
zc
}
fn main() {
use std::time::Instant;
let zc = init_zc();
let t0 = Instant::now();
let mut trail = 1;
let mut first = 0;
let mut total: f64 = 0.0;
let mut rfs = vec![1];
for f in 2..=50000 {
let mut carry = 0;
let mut d999: usize;
let mut zeroes = (trail - 1) * 3;
let len = rfs.len();
let mut j = trail - 1;
while j < len || carry != 0 {
if j < len {
carry += rfs[j] * f;
}
d999 = carry % 1000;
if j < len {
rfs[j] = d999;
} else {
rfs.push(d999);
}
zeroes += zc[d999];
carry /= 1000;
j += 1;
}
while rfs[trail - 1] == 0 {
trail += 1;
}
d999 = rfs[rfs.len() - 1];
d999 = if d999 < 100 {
if d999 < 10 {
2
} else {
1
}
} else {
0
};
zeroes -= d999;
let digits = rfs.len() * 3 - d999;
total += (zeroes as f64) / (digits as f64);
let ratio = total / (f as f64);
if ratio >= 0.16 {
first = 0;
} else if first == 0 {
first = f;
}
if f == 100 || f == 1000 || f == 10000 {
let duration = t0.elapsed();
println!(
"Mean proportion of zero digits in factorials to {} is {:.10}. ({}ms)",
f,
ratio,
duration.as_millis()
);
}
}
let duration = t0.elapsed();
println!(
"The mean proportion dips permanently below 0.16 at {}. ({}ms)",
first,
duration.as_millis()
);
}</lang>
{{out}}
<pre>
Mean proportion of zero digits in factorials to 100 is 0.2467531862. (0ms)
Mean proportion of zero digits in factorials to 1000 is 0.2035445511. (1ms)
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>
| |||