math.cs
View source code here on GitHub!
1using System;
2
3namespace Euler
4{
5 public static class Mathematics
6 {
7 public static ulong Factorial(ulong n)
8 {
9 ulong answer = 1;
10 for (ulong x = 2; x <= n; x += 1)
11 answer *= x;
12 return answer;
13 }
14
15 public static ulong NChooseR(ulong n, ulong r)
16 {
17 if (n <= 20)
18 return Factorial(n) / Factorial(r) / Factorial(n - r);
19 ulong answer, tmp;
20 uint i, j;
21 sbyte[] factors = new sbyte[n + 1];
22 // collect factors of final number
23 for (i = 2; i <= n; i += 1)
24 factors[i] = 1;
25
26 // negative factor values indicate need to divide
27 for (i = 2; i <= r; i += 1)
28 factors[i] -= 1;
29 for (i = 2; i <= n - r; i += 1)
30 factors[i] -= 1;
31
32 // this loop reduces to prime factors only
33 for (i = (uint)n; i > 1; i -= 1)
34 for (j = 2; j < i; j += 1)
35 if (i % j == 0)
36 {
37 factors[j] += factors[i];
38 factors[i / j] += factors[i];
39 factors[i] = 0;
40 break;
41 }
42
43 i = j = 2;
44 answer = 1;
45 while (i <= n)
46 {
47 while (factors[i] > 0)
48 {
49 tmp = answer;
50 answer *= i;
51 while (answer < tmp && j <= n)
52 {
53 while (factors[j] < 0)
54 {
55 tmp /= j;
56 factors[j] += 1;
57 }
58 j += 1;
59 answer = tmp * i;
60 }
61 if (answer < tmp)
62 return ulong.MaxValue; // this indicates an overflow
63 factors[i] -= 1;
64 }
65 i += 1;
66 }
67
68 while (j <= n)
69 {
70 while (factors[j] < 0)
71 {
72 answer /= j;
73 factors[j] += 1;
74 }
75 j += 1;
76 }
77
78 return answer;
79 }
80 }
81}