Factoradic Number Systems
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. 🤷♂️

A Different Take on Merge Sort: Binary Search Trees?

Deleting Entries From OpenAddress Hash tables

Transform any Binary Search Tree in to a Sorted Linked List

From Regular Expressions To NFA by way of Abstract Syntax Trees: Thompsons Construction

Extending Sedgewick's explicit Digraph NFA

Iterative Inorder B Tree Traversal

Simple DB Migration with JDBC

Welcome to CodeBlahger, A Blahging Platform for Programmers.

The Façade Pattern

The Interpreter Pattern: Implementing Interpreters the OOP way
Leave A Comment