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;
namespace Factoradic
{
  class Program
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin factoradic demo\n");
      int nits = 9; // 'nits' is n-ary digits = how many places
      int n = 1047;

      int[] factoradic = IntToFactoradic(n, nits);
      Console.WriteLine("Factoradic of " + n +
        " is: " + FactoradicAsString(factoradic));
      Console.WriteLine("");

      int f = FactoradicToInt(factoradic, nits);
      Console.WriteLine("Value of factoradic " +
        FactoradicAsString(factoradic) + " is: " + f);

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

    public static int FactoradicToInt(int[] factoradic, int nits)
    {
      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)
    {
      int[] factoradic = new int[nits];

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

    public static string FactoradicAsString(int[] factoradic)
    {
      string s = "";
      for (int i = 0; i < factoradic.Length; ++i)
        s += factoradic[i] + " ";
      return s;
    }

  }
}
Advertisements
This entry was posted in Software Test Automation. Bookmark the permalink.