Multifactorial
You are encouraged to solve this task according to the task description, using any language you may know.
The factorial of a number, written as is defined as
A generalization of this is the multifactorials where:
- Where the products are for positive integers.
If we define the degree of the multifactorial as the difference in successive terms that are multiplied together for a multifactorial (The number of exclamation marks) then the task is to
- Write a function that given n and the degree, calculates the multifactorial.
- Use the function to generate and display here a table of the first 1..10 members of the first five degrees of multifactorial.
Note: The wikipedia entry on multifactorials gives a different formula. This task uses the Wolfram mathworld definition.
C
<lang c> /* Include statements and constant definitions */
- include <stdio.h>
- define HIGHEST_DEGREE 5
- define LARGEST_NUMBER 10
/* Recursive implementation of multifactorial function */ int multifact(int n, int deg){
return n <= deg ? n : n * multifact(n - deg, deg);
}
/* Iterative implementation of multifactorial function */ int multifact_i(int n, int deg){
int result = n;
while (n >= deg + 1){
result *= (n - deg);
n -= deg;
}
return result;
}
/* Test function to print out multifactorials */ int main(void){
int i, j;
for (i = 1; i <= HIGHEST_DEGREE; i++){
printf("\nDegree %d: ", i);
for (j = 1; j <= LARGEST_NUMBER; j++){
printf("%d ", multifact(j, i));
}
}
} </lang>
- Output:
Degree 1: 1 2 6 24 120 720 5040 40320 362880 3628800 Degree 2: 1 2 3 8 15 48 105 384 945 3840 Degree 3: 1 2 3 4 10 18 28 80 162 280 Degree 4: 1 2 3 4 5 12 21 32 45 120 Degree 5: 1 2 3 4 5 6 14 24 36 50
C++
<lang cpp> /*Generate multifactorials to 9
Nigel_Galloway November 14th., 2012.
- /
int main(void) {
for (int g = 1; g < 10; g++) {
int v[12];
for (int n = 1; n < 11; n++) {
v[n] = (g < n)? v[n-g]*n : n;
std::cout << v[n] << " ";
}
std::cout << std::endl;
}
return 0;
} </lang>
- Output:
1 2 6 24 120 720 5040 40320 362880 3628800 1 2 3 8 15 48 105 384 945 3840 1 2 3 4 10 18 28 80 162 280 1 2 3 4 5 12 21 32 45 120 1 2 3 4 5 6 14 24 36 50 1 2 3 4 5 6 7 16 27 40 1 2 3 4 5 6 7 8 18 30 1 2 3 4 5 6 7 8 9 20 1 2 3 4 5 6 7 8 9 10
D
<lang d>import std.stdio, std.algorithm, std.range;
T multifactorial(T=long)(in int n, in int m) /*pure*/ {
T one = 1;
return reduce!q{a * b}(one, iota(n, 0, -m));
}
void main() {
foreach (m; 1 .. 11)
writefln("%2d: %s", m, iota(1, 11)
.map!(n => multifactorial(n, m))());
}</lang>
- Output:
1: 1 2 6 24 120 720 5040 40320 362880 3628800 2: 1 2 3 8 15 48 105 384 945 3840 3: 1 2 3 4 10 18 28 80 162 280 4: 1 2 3 4 5 12 21 32 45 120 5: 1 2 3 4 5 6 14 24 36 50 6: 1 2 3 4 5 6 7 16 27 40 7: 1 2 3 4 5 6 7 8 18 30 8: 1 2 3 4 5 6 7 8 9 20 9: 1 2 3 4 5 6 7 8 9 10 10: 1 2 3 4 5 6 7 8 9 10
Go
<lang go>package main
import "fmt"
func multiFactorial(n, k int) int {
r := 1
for ; n > 1; n -= k {
r *= n
}
return r
}
func main() {
for k := 1; k <= 5; k++ {
fmt.Print("degree ", k, ":")
for n := 1; n <= 10; n++ {
fmt.Print(" ", multiFactorial(n, k))
}
fmt.Println()
}
}</lang>
- Output:
degree 1: 1 2 6 24 120 720 5040 40320 362880 3628800 degree 2: 1 2 3 8 15 48 105 384 945 3840 degree 3: 1 2 3 4 10 18 28 80 162 280 degree 4: 1 2 3 4 5 12 21 32 45 120 degree 5: 1 2 3 4 5 6 14 24 36 50
Haskell
<lang haskell>mulfac k = 1:s where s = [1 .. k] ++ zipWith (*) s [k+1..]
-- for single n mulfac1 k n = product [n, n-k .. 1]
main = mapM_ (print . take 10 . tail . mulfac) [1..5]</lang>
- Output:
[1,2,6,24,120,720,5040,40320,362880,3628800] [1,2,3,8,15,48,105,384,945,3840] [1,2,3,4,10,18,28,80,162,280] [1,2,3,4,5,12,21,32,45,120] [1,2,3,4,5,6,14,24,36,50]
J
<lang J>
NB. tacit implementation of the recursive c function
NB. int multifact(int n,int deg){return n<=deg?n:n*multifact(n-deg,deg);}
multifact=: [`([ * - $: ])@.(<~) (a:,<' degree'),multifact table >:i.10
┌─────────┬──────────────────────────────────────┐ │ │ degree │ ├─────────┼──────────────────────────────────────┤ │multifact│ 1 2 3 4 5 6 7 8 9 10│ ├─────────┼──────────────────────────────────────┤ │ 1 │ 1 1 1 1 1 1 1 1 1 1│ │ 2 │ 2 2 2 2 2 2 2 2 2 2│ │ 3 │ 6 3 3 3 3 3 3 3 3 3│ │ 4 │ 24 8 4 4 4 4 4 4 4 4│ │ 5 │ 120 15 10 5 5 5 5 5 5 5│ │ 6 │ 720 48 18 12 6 6 6 6 6 6│ │ 7 │ 5040 105 28 21 14 7 7 7 7 7│ │ 8 │ 40320 384 80 32 24 16 8 8 8 8│ │ 9 │ 362880 945 162 45 36 27 18 9 9 9│ │10 │3628800 3840 280 120 50 40 30 20 10 10│ └─────────┴──────────────────────────────────────┘ </lang>
Mathematica
<lang perl6>Multifactorial[n_, m_] := Abs[ Apply[ Times, Range[-n, -1, m]]] Table[ Multifactorial[j, i], {i, 5}, {j, 10}] // TableForm</lang>
- Output:
1: 1 2 6 24 120 720 5040 40320 362880 3628800 2: 1 2 3 8 15 48 105 384 945 3840 3: 1 2 3 4 10 18 28 80 162 280 4: 1 2 3 4 5 12 21 32 45 120 5: 1 2 3 4 5 6 14 24 36 50
Objeck
<lang objeck> class Multifact {
function : Main(args : String[]) ~ Nil {
v := Int->New[12];
for(g := 1; g < 10; g+=1;) {
for (n := 1; n < 11; n+=1;) {
v[n] := (g < n)? v[n-g]*n : n;
IO.Console->Print(v[n])->Print(" ");
};
IO.Console->PrintLine();
};
}
} </lang>
Output:
1 2 6 24 120 720 5040 40320 362880 3628800 1 2 3 8 15 48 105 384 945 3840 1 2 3 4 10 18 28 80 162 280 1 2 3 4 5 12 21 32 45 120 1 2 3 4 5 6 14 24 36 50 1 2 3 4 5 6 7 16 27 40 1 2 3 4 5 6 7 8 18 30 1 2 3 4 5 6 7 8 9 20 1 2 3 4 5 6 7 8 9 10
Perl 6
<lang perl6>sub mfact($n, :$degree = 1) { [*] $n, *-$degree ...^ * <= 0 }
for 1 .. 5 -> $degree {
say "$degree: ", map &mfact.assuming(:$degree), 1 .. 10;
}</lang>
- Output:
1: 1 2 6 24 120 720 5040 40320 362880 3628800 2: 1 2 3 8 15 48 105 384 945 3840 3: 1 2 3 4 10 18 28 80 162 280 4: 1 2 3 4 5 12 21 32 45 120 5: 1 2 3 4 5 6 14 24 36 50
Python
Python: Iterative
<lang python>>>> from functools import reduce >>> from operator import mul >>> def mfac(n, m): return reduce(mul, range(n, 0, -m))
>>> for m in range(1, 11): print("%2i: %r" % (m, [mfac(n, m) for n in range(1, 11)]))
1: [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800] 2: [1, 2, 3, 8, 15, 48, 105, 384, 945, 3840] 3: [1, 2, 3, 4, 10, 18, 28, 80, 162, 280] 4: [1, 2, 3, 4, 5, 12, 21, 32, 45, 120] 5: [1, 2, 3, 4, 5, 6, 14, 24, 36, 50] 6: [1, 2, 3, 4, 5, 6, 7, 16, 27, 40] 7: [1, 2, 3, 4, 5, 6, 7, 8, 18, 30] 8: [1, 2, 3, 4, 5, 6, 7, 8, 9, 20] 9: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
10: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> </lang>
Python: Recursive
<lang python>>>> def mfac2(n, m): return n if n <= (m + 1) else n * mfac2(n - m, m)
>>> for m in range(1, 6): print("%2i: %r" % (m, [mfac2(n, m) for n in range(1, 11)]))
1: [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800] 2: [1, 2, 3, 8, 15, 48, 105, 384, 945, 3840] 3: [1, 2, 3, 4, 10, 18, 28, 80, 162, 280] 4: [1, 2, 3, 4, 5, 12, 21, 32, 45, 120] 5: [1, 2, 3, 4, 5, 6, 14, 24, 36, 50]
>>> </lang>
Tcl
<lang tcl>package require Tcl 8.6
proc mfact {n m} {
set mm [expr {-$m}]
for {set r $n} {[incr n $mm] > 1} {set r [expr {$r * $n}]} {}
return $r
}
foreach n {1 2 3 4 5 6 7 8 9 10} {
puts $n:[join [lmap m {1 2 3 4 5 6 7 8 9 10} {mfact $m $n}] ,]
}</lang>
- Output:
1:1,2,6,24,120,720,5040,40320,362880,3628800 2:1,2,3,8,15,48,105,384,945,3840 3:1,2,3,4,10,18,28,80,162,280 4:1,2,3,4,5,12,21,32,45,120 5:1,2,3,4,5,6,14,24,36,50 6:1,2,3,4,5,6,7,16,27,40 7:1,2,3,4,5,6,7,8,18,30 8:1,2,3,4,5,6,7,8,9,20 9:1,2,3,4,5,6,7,8,9,10 10:1,2,3,4,5,6,7,8,9,10
XPL0
<lang XPL0>code ChOut=8, CrLf=9, IntOut=11;
func MultiFac(N, D); \Return multifactorial of N in degree D int N, D; int F; [F:= 1; repeat F:= F*N;
N:= N-D;
until N <= 1; return F; ];
int I, J; \generate table of multifactorials for J:= 1 to 5 do
[for I:= 1 to 10 do
[IntOut(0, MultiFac(I, J)); ChOut(0, 9\tab\)];
CrLf(0);
]</lang>
- Output:
1 2 6 24 120 720 5040 40320 362880 3628800 1 2 3 8 15 48 105 384 945 3840 1 2 3 4 10 18 28 80 162 280 1 2 3 4 5 12 21 32 45 120 1 2 3 4 5 6 14 24 36 50