# Collatz Conjecture

Recently I had an interesting problem to solve on the Collatz Conjecture and it started a conversation amongst some of my friends on set theory and math’s ability to reduce the complexity of coding problems. The Collatz Conjecture is described simply as an unsolved problem in mathematics. From wikipedia: Start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1. Its namesake comes from Lothar Collatz, a mathematician who introduced the idea in 1937. It’s history and the history of mathematicians attempting to prove it false if fascinating and can be read just a bit deeper on the wiki for the problem. However ths focus of this is piece in on the problem I had an opportunity to solve.

So first let’s make the conjecture just a bit easier to understand. If it was a piecewise function it would be as follows:
n/2 if n=even,
3n+1 if n=odd

From a coding perspective this is pretty simple to implement. You could make a simple function that acts as follows.

function collatz(n) {
if ( n == 1) { return; }
else if ( n%2 == 0) { return collatz(n/2) }
else { return collatz(3*n+1) }
}

From here any number we enter into the collatz in theory will return 1 to us eventually. But that isn’t much of a problem is it. So let’s talk about the actual problem.

Given a range between 1 and 1,000,000, calculate the number of operations it takes using the Collatz Conjecture to reduce a number to 1. Finally find the which number between 1 and 1,000,000 took the most operations to equal 1.

Now we have an interesting coding problem. As coders doing these sorts of problems we are always thinking of processing speed, memory, and how well this could scale with use on our system and this can really get at the heart of those core issues.

Like all problems, it is useful to brute force it first. Taken the same function as written above let’s expand it and write a loop to call it.

Function collatz(n, operations) {
if ( n == 1) { return operations; }
else if ( n%2 == 0) { return collatz(n/2, operations + 1) }
else { return collatz(3*n+1, operations + 1) }
}

Function callCollatz = () {
operations = 0
for (i = 1000000; i>=1; i–) {
temp = collatz(i, operations);
if (temp > operations) { operations = temp }
}
return operations;
}

callCollatz();

No this is a first approach counting down from 1,000,000 and calculating the length of operations for each number then return the longest. Time wise this is O(a * b) where a is the for loop iterations, and b is the amount of iterations the recursive collatz function takes. Spacewise is a different story though, We are really only abusing space when we attempt the recursive function and this is O(n) space.

Left simply as is we have a quick and dirty way to get the number of operations, however this is where simple diverges. We can make this faster in a few ways.

First why did I initially choose to iterate down from 1,000,000. Well that’s because we could attempt a divide and conquer strategy similar to merge sort and have multiple recursive loops breaking the number in half recursively and then calculating the solution.
This approach really doesn’t optimize much though.

Instead the function should be changed to iterate up from 1 to 1,000,000. But why though. Well we know that each iteration of the Collatz conjecture has a number of operations it takes to get to 1. 1 takes 1 operation, 2 takes 2, 4 takes 3, 3 takes 7. Let’s look at it in sets.
1 ->  = 1
2 -> [2, 1] = 2
3 -> [3, 10, 5, 16, 8, 4, 2, 1] = 8
4 -> [4, 2, 1] = 3
5 -> [5, 16, 8, 4, 2, 1] = 6

You may notice that when we are calculating these results there is some overlap in the adding. For instance 4 takes 3 operations, and 5 takes 6.

5 goes to 16, then 8, then 4, 2 1. We don’t need to iterate during the 4, 2, 1 part however since we already have attempted that starting point and know its total number of operations. This means that if we just store the operations a number takes to reach 1 in a dictionary like data structure, we can check the dictionary for whether we have crossed that number before and if we did just add its number of operations to our current number and return it.

This can reduce the amount of processing time by a significant number, and has the advantage of getting faster with more iterations over the function.

So that handles the amount of operations and ultimately the processing time, but what about other things that we can do to reduce the load.

Well with a large chunk of the main functionality already optimized We can look at the actual math occuring in the problem. Instead of approaching the problem using the adding and dividing math functions(dividing having a history with being a bit processor intensive. We can approach it with bit shifting and manipulation. If the number is odd we can add a bit to the number and add the new number to the old number. If there are trailing 0s aka the first bit is 0 we can just drop shift that bit altogether which is the equivalent of dividing by 2.

Using a bit shifting approach seems minor but it really does add up to better performance if implemented correctly, and this problem is ideal for that type of system.

So as you can see the Collatz conjecture occupies an interesting problem as a simple cs problem that can be open for a depth of complexity in the implementation. For those reading this, how would you approach this problem.

# Game Table: Round Two It’s been a few weeks since I have had an opportunity to work on my table mostly due to weather, the holidays, and a few family emergencies. But now that I am back to work and I set up an indoor workshop I can finally finish the table.

First up was attaching the table top a bit better and problem solving my Pin legs not having much to support. Its moments like these that I feel cursed by my MechE degree because I immediately go into engineer mode and start considering torque, shear stress, and a thousand other things when really I just need a few more screws.

With the table top attached and the legs in I realized my leg problem had more to due with my screws then anything else. I was using #6 fine thread 1/2″ screws on some soft pine wood. It is pretty easy to see that my legs would wobble. So I grabbed some #10 3/4″ screws which really bit into the wood, after that I decided I should secure every bit of my table top with the better screws and things really seemed to come together.

I decided to take a break to really let some wood glue dry on a few of the pieces that just weren’t getting enough force to held down. As I fiddled with the wood glue I think about how much time I could save if my work surface was actually flat and not on a weird 5º angle.

# Custom Game Table After a year of looking at custom tables that other folks have been building I decided it was about time to build one myself. I took most of my inspiration from Black Magic Crafts table linked here. I took the key frame that he built and expanded a bit on it. For me the table was all about having enough space for my players. 12×6 pine was for the top of the table and 2×4 were used for the frame. I was going to make legs but decided that I didn’t have the right tools to make a nice one so instead I ordered some pin legs. Finally, I used some 1×2’s to build a channel for the LEDs and that is what holds up the center.

# Starting a Blog Among the thousands of blogs that already exist out there on wood work, gaming, and coding starting a little thing here really is just a drop in the pond. This just means that the goal is to build something that is well I guess more for me than anyone else. With that stated to myself, this blog will be about wood working, electronics, coding, and dungeons and dragons. Among other things
.