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 Open-Address 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 In-order 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