## The Factoradic of a Number

Normal numbers can be uniquely expressed as powers of 10. For example the number 7246 can be expressed as (7 2 4 6) = (7 * 10^3) + (2 * 10^2) + (4 * 10^1) + (6 * 10^0). Normal numbers can also be uniquely expressed as powers of 2, for example, 23 can be expressed as (1 0 1 1) = (1 * 2^4) + (0 * 2^3) + (1 * 2^2) + (1 * 2^1) + (1 * 2^0).

Now recall that the factorial of some number k is k * (k-1) * (k-2) * . . . * 1. So factorial(5), usually abbreviated as 5! is 5 * 4 * 3 * 2 * 1 = 120. Somewhat surprisingly, numbers can be expressed as the sum of factorials. For example, the number 1047 can be expressed as (1 2 3 2 1 1 0):

(1 * 6!) + (2 * 5!) + (3 * 4!) + (2 * 3!) + (1 * 2!) + (1 * 1!) =
(1 * 720) + (2 * 120) + (3 * 24) + (2 * 6) + (1 * 2) + (1 * 1) =
720 + 240 + 72 + 12 + 2 + 1 =
1047

Here is placed a dummy 0 value at the right-most position. The representation of a number n as the sum of factorials is called the factoradic of n. By themselves factoradics are interesting by not particularly useful. But, it turns out that the factoradic of a number n maps directly to the nth permutation of n items. This allows arbitrary permutations to be computed extremely quickly.

Listed below is some demo C# language code to illustrate basic factoradic concepts. The code uses the idea of ‘nits’ (n-ary digits) to stand for how many factoradic digits to use. The code also places a dummy 0 value in the right-most position — this is useful when working with permutations and to account for the fact that both 1! and 0! equal 1 by definition.

```using System;
{
class Program
{
static void Main(string[] args)
{
int nits = 9; // 'nits' is n-ary digits = how many places
int n = 1047;

Console.WriteLine("Factoradic of " + n +
Console.WriteLine("");

Console.WriteLine("\nEnd demo\n");

{
int result = 0;
for (int i = 0; i < factoradic.Length; ++i)
{
int f = Factorial(nits - 1 - i);
int v = f * factoradic[i];
result = result + v;
}
return result;
}

public static int Factorial(int n)
{
int ans = 1;
for (int i = 1; i &lte; n; ++i)
ans = ans * i;
return ans;
}

public static int[] IntToFactoradic(int n, int nits)
{

for (int j = 1; j &lte; nits; ++j)
{
factoradic[nits - j] = n % j;
n /= j;
}
}