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

Published by

Harsh

Developer at Microsoft by the day, a wannabe physicist by the night.

15 thoughts on “Factorial Number System (factoradic)”

  1. Its good….i learned a new number system today.
    But… i think that this factoradics system can be more useful in encryption, not in daily use as it will be more difficult to write a no. in factoradics.
    Moreover we have to learn factorials of no.s and learn ways to perform operations(* , /) on them.

  2. has this been applied anywher already?? and are any operations possible on using this no. system?? btw interesting topic…:)

    1. wrote that mate.. in block cipher systems you can apply it.. and the kth permutation is the strongest part of this system.. 🙂
      and even @Rahul raised this topic about operating on them.. there has to be.. you cant have any number without any closed set of operations because if it has none then that number system becomes useless..

  3. it may be used only to cipher nd decipher dn it wont need any operations…bt if u find out method o ne operation pls post it..:)

  4. yeah, sure..
    in fact, i wanted to write a lot more but then there were constraints.. i can’t write particularly for geeks.. i had to mix the level of contents so that it could pull crowd of all kinds.

  5. Salve, scrivo dall’Italia
    ho letto per caso l’articolo.
    Ho pubblicato un libro, ” Numerazione dele combinazioni semplici ” anno 2006 Edizioni Delta3
    codice ISBN 88-89372-54-4
    che risolve tutto il problema del factoradic
    iniziando dal modo di contare facendo uso delle permutazioni.
    Credo sia interessante.
    Graniero Gerardo

  6. Salve,
    nel 2006 ho scritto un lavoro sul factoradic di 32 pagine ” Numerazione delle Permutazioni Semplici ”
    ISBN 88-89372-54-4
    Graniero Gerardo

  7. Hello,
    In 2006 I wrote a 32-page work on factoradic: “Numbering of Simple Permutations”
    ISBN 88-89372-54-4
    Gerardo Graniero

  8. Thanks for any other informative blog. Where else may I get that kind
    of info written in such a perfect method? I’ve a challenge that I am simply now working on, and I’ve been on the look out for such information.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s