Factoradic Number Systems

mgcadmin 01-10-2023

Like many other software engineers out there, I love XKCD so whenever Randall publishes a comic with something computationally interesting I like to take a stab at it. Friday's comic (2835) was just such a comic. It has to do with "factorial" or factoradic numbers, which Randall eloquently describes as "the number system that sounds most like a prank by someone who's about to escorted from the Math department by security."

Sometimes when xkcd touches upon mathematical topics, I don't have the mathematical background to truly appreciate them. But after a quick google about what they were I was able to come up with the following algorithm to compute the factoradic value of any base 10 number:

#include <iostream>
#include <algorithm>
using namespace std;

int factoradic(int num) {
    string digits;
    int radix = 2;
    while (num != 0) {
        digits.push_back(to_string(num % radix)[0]);
        num /= radix++;
    }
    reverse(digits.begin(), digits.end());
    return atoi(digits.c_str());
}

int main(int argc, char* argv[]) {
    for (int i = 1; i < 26; i++) {
        cout<<i<<" - "<<factoradic(i)<<endl;
    }
    for (int i = 5038; i < 5042; i++) {
        cout<<i<<" - "<<factoradic(i)<<endl;
    }
    for (int i = 999998; i < 1000002; i++) {
        cout<<i<<" - "<<factoradic(i)<<endl;
    }
    return 0;
} 

max@MaxGorenLaptop:~/code$ ./xkcd
 1 - 1
 2 - 10
 3 - 11
 4 - 20
 5 - 21
 6 - 100
 7 - 101
 8 - 110
 9 - 111
 10 - 120
 11 - 121
 12 - 200
 13 - 201
 14 - 210
 15 - 211
 16 - 220
 17 - 221
 18 - 300
 19 - 301
 20 - 310
 21 - 311
 22 - 320
 23 - 321
 24 - 1000
 25 - 1001
 5038 - 654320
 5039 - 654321
 5040 - 1000000
 5041 - 1000001
 999998 - 266251210
 999999 - 266251211
 1000000 - 266251220
 1000001 - 266251221
 max@MaxGorenLaptop:~/code$

That reminds me, I really need to start using scripting languages for stuff like this. It's just that I'm still a little bitter about perl dying.. stupid Raku... Really though, it's just that I can never make up my mind on which one I want to really learn: Python or Ruby. 🤷‍♂️

---