Collatz Conjecture
If you havent heard about what the hell the "Collatz Conjecture" is supposed to be, don't worry: it's quite simple.
Basically the Conjecture is a simple math formula and a question. I will write the formula in C Code since that's quite easy to read:
if (x % 2 == 0) {
x = x/2;
} else {
x = 3*x + 1;
}
"If a number x
is cleanly divisible by 2, half it, else multiply by 3 and add
one. Repeat for the result."
The question is: Does every number diverge to 1 when you apply this formula?
I found out about this from this video from YouTuber ThoughtThrill.
I didn't plan on solving it since I (and seemingly no one else) am nowhere good enough in math to do so but I thought it would be a nice coding adventure and an easy enough problem to visualize.
Programming
This for me was a really fun programming challenge.
For the main calculation I started with a map that had the number as a key and the value as the result the number would turn into when thrown into the collatz function. This way i had a nice look-up table and didn't have to re-calculate numbers twice which would save time.
Then for the drawing process I created an n-ary tree using the look up table from before. The tree could be traversed using the 'child' nodes which also had child nodes which also... .
This had the advantage of not having to re-compute the numbers while rendering. Also you have the added bonus of knowing really easily at which 'depth' the current node is.
So before rendering, we calculate all the numbers and build a tree from it. While rendering we start at the root node, which is the node with value 1. We draw it's value, then look at the children of this node and draw their value, in a breadth first manner. From there we draw the next children and so on.
So how does the result look? It looks like this:
The calculation is also somewhat fast. Building the map is the part where most of the calculation happens. Yet it can calculate one million numbers in roughly 2.2 seconds on a single thread of a AMD Ryzen 1600X. I'm sure there is still room for a lot of improvement but I'm happy about the results for now :)
The project is nowhere near finished or optimized but I'm gonna work on it every now and then (if I feel like it).
Also expect updates to this post!