1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144# Mathematical formulas and reasonings
## Exact Factorial
We use the library `rug` (`gmp`).
## Exact Multifactorial
We use the library `rug` (`gmp`).
## Exact Termial
Termials are triangular numbers. They can be calculated with the well-known formula:
```math
n? = \frac{n(n+1)}{2}
```
## Exact Multitermial
Termials are triangular numbers. They can be calculated with the well-known formula:
```math
n?_k = k \left\lfloor\frac{n}{k}\right\rfloor? + \left\lceil\frac{n}{k}\right\rceil (n \mod k)
```
## Exact Subfactorial
As the most efficient common definition that only uses integers, we use the formula:
```math
\begin{aligned}
!0 &= 1 \\
!n &= n \cdot !(n-1)+(-1)^n
\end{aligned}
```
## Approximate Factorial
Factorials can be approximated with [Stirling’s formula](https://en.wikipedia.org/wiki/Stirling%27s_approximation):
```math
n! \approx \sqrt{2 \pi n} \cdot A(n) \cdot \left(\frac{n}{e}\right)^n
```
Which can be brought into a calculable form with a separate order of magnitude like so:
```math
\begin{aligned}
n! &\approx \sqrt{2 \pi n} \cdot A(n) \cdot \left(\frac{n}{e}\right)^n \text{ | Stirling's Approximation (A(n) only contains negative powers of n, not in exponents)} \\
&\approx \sqrt{2 \pi n} \cdot A(n) \cdot \left(\frac{n}{e}\right)^m \cdot 10^k \text{ | factoring out the 10 exponent (k)} \\
&\approx \sqrt{2 \pi n} \cdot A(n) \cdot \left(\frac{n}{e}\right)^{m + \frac{ln(10)}{ln\left(\frac{n}{e}\right)} k} \text{ | factoring it back in (to calculate it)} \\
\\
n &= m + log_{\frac{n}{e}}(10) \cdot k \text{ | got out of exponents} \\
n &\approx log_{\frac{n}{e}}(10) \cdot k \text{ | m should be small} \\
k &= \left\lfloor n / log_{\frac{n}{e}}(10) \right\rfloor \text{ | calculate k which is an integer (floor because otherwise m < 0)} \\
m &= n - log_{\frac{n}{e}}(10) \cdot k \text{ | calculate the exponent for the calculation}
\end{aligned}
```
## Approximate Multifactorial
We can bring the [continuation](#float-multifactorial) into a calculable form (the major part) like so:
```math
\begin{aligned}
z!_k &= k^{\frac{z}{k}} \cdot \frac{z}{k}! \cdot T_k(z) \text{ | we already have implementations for z! and T_k(z)} \\
\\
k^{\frac{z}{k}} &= k^m \cdot 10^n \
10^{log_{10}(k) \cdot \frac{z}{k}} &= 10^{log_{10}(k) \cdot m} \cdot 10^n \text{ | log_{10}} \\
log_{10}(k) \cdot \frac{z}{k} &= log_{10}(k) \cdot m + n \text{ | n should be as large as possible} \\
\\
n &= \left\lfloor log_{10}(k) \cdot \frac{z}{k} \right\rfloor \\
m \cdot log_{10}(k) &= log_{10}(k) \cdot \frac{z}{k} - n | \div log_{10}(k) \\
m &= \frac{z}{k} - \frac{n}{log_{10}(k)}
\end{aligned}
```
## Approximate Multitermial
Multitermials have a simple formula:
```math
n?_k \approx \frac{n(n+k)}{2k}
```
Which can be brought into a calculable form with a separate order of magnitude like so:
```math
\begin{aligned}
n?_k &\approx \frac{n(n+k)}{2k} \\
\\
m &= \left\lfloor log_{10}(n) \right\rfloor \\
\\
n?_k &\approx k \frac{l}{2k} 10^{2m} \\
n?_k &\approx k 10^m \cdot l \frac{10^m}{2k} \\
\\
k 10^m &\approx n \\
k &\approx \frac{n}{10^m} \\
l &= \frac{n+k}{10^m} \\
\end{aligned}
```
## Approximate Subfactorial
A subfactorial is approximately proportional to the factorial:
```math
!n = \left\lfloor \frac{n!+1}{e} \right\rfloor \approx \left\lfloor \frac{n!}{e} \right\rfloor
```
## Approximate Factorial Digits
Factorials can be approximated with [Stirling’s formula](https://en.wikipedia.org/wiki/Stirling%27s_approximation):
```math
n! \approx \sqrt{2 \pi n} \cdot A(n) \cdot (\frac{n}{e})^n
```
Its log_10 can be roughly approximated like so:
```math
\begin{aligned}
log_{10}(n!) &\approx log_{10}(\sqrt{2 \pi n} \cdot \left(\frac{n}{e})^n\right) \text{ | Stirling's Approximation} \\
&\approx \frac{1}{2} log_{10}(2 \pi n) + n \cdot log_{10}\left(\frac{n}{e}\right) \text{ | splitting up, taking exponents out} \\
&\approx \frac{1}{2} log_{10}(2 \pi) + \frac{1}{2} log_{10}(n) + n \cdot log_{10}(n) - n \cdot log_{10}(e) \text{ | splitting further} \\
\text{digits} &\approx \left\lfloor \left(\frac{1}{2}+n\right) log_{10}(n) + \frac{1}{2} log_{10}(2 \pi) - \frac{n}{ln(10)} \right\rfloor +1 \text{ | combining log_10(n) and turning into number of digits}
\end{aligned}
```
## Approximate Multifactorial Digits
A k-factorial very roughly is the k-th root of the factorial, while not exact enough for approximations, the number of digits is correct.
## Approximate Multitermial Digits
Multitermials have a simple formula:
```math
n?_k \approx \frac{n(n+k)}{2k}
```
Its log_10 can be roughly approximated like so:
```math
\begin{aligned}
log_{10}(n?_k) &= log_{10}\left(\frac{n(n+k)}{2k}\right) \\
&= log_{10}\left(n^2+nk\right) - log_{10}(2k) \text{ | drop inconsequential n} \\
&\approx 2 log_{10}(n) - log_{10}(2k)
\end{aligned}
```
## Approximate Subfactorial Digits
A subfactorial is approximately proportional to the factorial, less than an order of magnitude (just `e`) apart.
The number of digits does not significantly differ.
## Float Factorial
The analytical continuation of factorials is the gamma function, which we use through `rug` (`gmp`):
```math
x! = \Gamma(x+1)
```
## Float Multifactorial
There is an analytical continuation of any k-factorial [here](https://math.stackexchange.com/questions/3488791/define-the-triple-factorial-n-as-a-continuous-function-for-n-in-mathbb/3488935#3488935):
```math
\begin{aligned}
x!_k &= T_k(x) \cdot k^{\frac{x}{k}} \cdot (\frac{x}{k})! \\
\text{where} \\
T_k(x) &= \prod^k_{j=1}\left(k^{-\frac{j}{k}} j \cdot \left(\frac{j}{k}\right)!^{-1}\right)^{E_{k,j}(x)} \\
\text{where} \\
E_{k,j}(x) &= \frac{1}{k} \sum^k_{l=1}\left(cos(2 \pi l \frac{x-j}{k}\right)
\end{aligned}
```
However this does not match the commonly used double factorial continuation.
To make it match, we have to set:
```math
E_{k,j}(x) = \frac{\prod^{k-1}_{l=0}\left(1 - cos\left(\frac{2}{k} \pi (x-l)\right) \cdot (l \neq j)\right)}{\prod^{k-1}_{l=0}\left(1 - cos\left(-\frac{2}{k} \pi l\right)\right)}
```
Which preserves the trait of equaling 1 for one j while being zero for all others if x is an integer.
To improve performance, we only include those j near x.
## Float Termial
The termial formula is compatible with floats:
```math
n? = \frac{n(n+1)}{2}
```