Factorial Number System (factoradic)

Once while surfing through Wikipedia, I came across a new kind of number system – Factorial Number System. Also known as factoradic, this number system is most apt for permutations. Like 10 is the base in decimals, 2 in binary, factorials are the bases in factoradics(though not in true sense because it is a mixed radix number system; the factorials just provide the values for a particular digit’s place).

As a brush up, mixed radix system are the numeral systems in which the base varies from one place to another. This is to say that the base value varies from what it was for ones digit to what it will be for the tens digit to that for hundreds digit. The table below will make the idea clearer. For the digit at ones place, the base is 0!, for tens it’s 1!, for hundreds it is 2! and so on.

base 8 7 6 5 4 3 2 1
place value 7! 6! 5! 4! 3! 2! 1! 0!
in decimal 720 360 120 24 6 2 1 1

A point to be remembered is one should keep in mind that a digit can’t be placed at a position if it’s numeral value is greater than or equal to the base. This is to say that one cannot place 1 at ones place or 2 at tens or 4 at the thousands place.

So how to write these factorial numbers is what comes next.

Suppose we want to write 16 in factorial number system. Now, we can write 16 = 2*3! + 2*2! + 0*1! + 0*0!

So, 16 in decimals becomes 2200.

We often drop the last 0 in this system because the last position can only be occupied by 0 which is obvious. So, you may write 16 as 220.

The obvious: 54321 is the largest factoradic for 5 digits (or 543210 if you include 0 too in the system in 6 digits).

Now, a question arises why should I prefer a new number system when we have many others along with us which keep bugging? Well the reason would just satisfy you. This number system helps us in finding the permutations more easily and efficiently.

The kth permutation of order n can be written in mere seconds. Suppose that we have to write 9,99,999th permutation of 10th order permutation which is 2,78,39,15,460. The mere hit and trial is definitely going to give a hard time.

With factoradics, the only thing that we gotta do is write the factoradic for 9,99,999. We find that 9! = 362880 and 10! = 3628800. Clearly, we don’t require the 10! in our answer as 10! – 1 = 3628799 > 9,99,999. Now, 999999/9! gives 2 as quotient. Now, we are left with 2,74,239. Continuing this, 2,74,239/8!, we get 6 as quotient and 32319 as remainder and so on. Thus, we get 9,99,999 as 2,66,25,12,110 in factoradics (including 0!).

The set for which we have to find the permutation is {0,1,2,3,4,6,7,8,9}. We have to permute them in such a way that the string thus generated contains every digit without repetition. We are going to select the corresponding digit of the factoradic from the remaining set to write the required permutation. The process will be easy to understand with the illustration below.

2                                                     6                               6    —>    1            1      0

|                                                      |                                |    —>     |             |      |

(0,1,2,3,4,5,6,7,8,9)–>(0,1,3,4,5,6,7,8,9)–>(0,1,3,4,5,6,8,9)—>(0,4,6)->(0,6)->(0)

Thus our 9,99,999th permutation becomes 2,78,39,15,460. In seconds as I said!

Not just in string permutations, factoradics also help in encryption system, block ciphers being one such example. I wont dwell a lot in that again. Moreover, I read somewhere that in this system , e (exponential) can be represented as 10.1111.. and π (pi) as 11.1010101.. Though, I am not sure about these claims.

But there are still some problems with it. You need to have large set of numbers to represent very large numbers. After 9 we use A,B,C,D.. Z for integers upto 35. Well, one can use subscripts to represent larger numbers with subscipts to represent their base, e.g., 2423020for 16 but even that is cumbersome. Next, representation of decimals is again something to be worked on. Though after a small googling, i found that a guy did propose how to write decimals –

an*n! + an-1*(n-1)! + … + a2*2! + a1*1! + a0*0! + b1/2! + b2/3! + … + bn-1/n! + …

where ai represents digits before decimal while bi represents digits after decimal. How? That will lead this blog haywire! So, I will better leave that. Though this proposal does give an instance where we can get e = 10.111.. as e = 1/0! +1/1! + 1/2! + 1/3! + ..

Concluding note – all cryptographers should know this simple basic concept because this method accomplishes their task elegantly and with almost no pain (at least in comparison to the labor applied without this knowledge).

Advertisements