This is a continuation (part 2) of my blog titled The 3n+1 Problem & More!
I recommend you read that first to get the context, or it’ll be really boring or at least confusing 🙂
In the previous blog we generated a sequence of numbers starting from ANY number and converging to 1…always! I also proved a better, far more efficient way to converge than Collatz Conjecture’s algorithm, but here we’ll return to Collatz method and do the 3n+1 but in REVERSE. Meaning, we will find create a repeatable algorithm to find the number you picked! And generate the full sequence of numbers (and number of steps) that were visited in that journey starting from 1 to the number you picked…WITHOUT CHEATING!
What do I mean by cheating? For example, we could very easily just show the original user-input since it’s saved in memory for calculation. And we could simply reverse the sequence that we created in the first go to converge to 1 and “pretend” that it’s been re-created. Where’s the fun in that? No fun! Certainly not cerebral. The challenge is to find and code the algorithm and re-generate the EXACT sequence of numbers during the converge using 3n+1, and find the original starting number…100% reproducible for ANY input at any time.
Ok, so let’s see how we can do this. First, let’s explain the problem in more detail using a starting number 3:
Using the Collatz method, we generate the following sequence of numbers until the solution (i.e. convergence to 1): 3, 10, 5, 16, 8, 4, 2, 1
That’s the easy part. So, how can we then re-generate this sequence exactly starting from a number 1 and going backward, all the way to 3?
Remember the algorithm used above is: if n is even, divide by 2, and if n is odd, multiply by 3 and add 1.
So, to go backward, we start with 1. It’s an odd number, so previously, we would multiply it by 3 and add 1 for odd numbers, right? But if we do that, we would get 4! That’s not the second number in the sequence! We would expect 2, then 4, then 8, then 16, and so on as shown above. To go backward, we would have to reverse the logic to: if n is odd, multiply by 2. Ok, so we have 1, 2. What do we do with the even number 2? Well, the next one in series we expect is 4, so it’d be tempting to also multiply by 2! Ok, so let’s see what happens if we just multiply by 2 even when it’s an even number…we get 1, 2, 4, 8, 16, 32 (ooops!!). We don’t have 32 in series and we’ll never get to the original number 3 this way!
The solution is to figure out that the reverse of 3n+1 is (-1 + n/3). However, there’s still a problem! We still cannot re-generate the sequence for any given number using this new reverse logic where we said: if n is odd, do 2*n to find the next number, and if n is even, do -1+n/3 to generate the next number. It simply won’t scale to any number even if it worked for a particular input. We won’t be able to get to the original number, and we won’t be able to re-generate the sequence (or reverse of the original) using that algorithm.
Why? The problem is, while our reverse algorithm is correct as to how we handle the odd and even numbers, we are missing one more piece of information that is absolutely necessary to re-generate the sequence exactly backward…and that is…??? The 0peration (2*n or -1+n/3) taken on a given number at the nth step of the calculation. Therefore, in our first step, as we take the input 3, and converge to 1 (in this example), we have to keep track of three important things in addition to the logic applied: 1) The number being operated on and 2) The math operation itself to generate the next number in sequence and 3) At which step was that operation done.
Then, as we work backward, we can start with 1, then generate the full sequence and arrive to the original input. The sequence would be exactly the original sequence but in reverse and it’ll look like this: 1, 2, 4, 8, 16, 5, 10, 3
The Solution:
Generate the sequence of numbers to converge from n to 1.
- Now that we understand how we can solve this, let’s verbalize it in pseudocode, then we’ll implement it in real, executable code.
- Get input from the user, verify integrity (e.g. a positive number) and proceed with legal input
- Apply n/2 and 3n+1 depending on the the input to generate the next number in sequence
- Repeat this process until the generated number is exactly 1.
4.1. While repeating the process, save the each number examined, the operation taken (use operational codes to indicate n/2 or 3n+1), in exact order of the number generation (input being step 1, and up to the last number of 1).
To re-trace and re-generate:
5. Using the saved sequence and operations, start from the LAST number generated (in this case, always 1) and re-calculate the number previous to that, and previous to that, and so on until no operations are left to execute in the list saved in step 4.1.
5.1. While doing step 5, save each number (starting from 1, and the resulting number, after operating on the number) in a new sequence list.
This process will end when there’s no more operations left to execute, so the last number will be same as the original input. And display the new sequence of numbers in step 5…which should be exactly same as in step 4.1 in reverse.
The Code:
Now that we have the method nailed down, it’s time to actually tell the computer how to execute it. The code is shown below section by section (for brevity, I’ve taken out the usual error checking and exception handling, etc. out of this blog). Each block is explained…
Explanation: We create 2 empty lists (one to hold the sequence converging to 1, another to hold the re-generated sequence going backward from 1 to input). We create 2 objects each with an array of key-value paired data structure. These are Dictionary objects (in Python) but each being fully scalable/elastic sizes since we cannot anticipate the input and how many numbers will need to be stored throughout the sequence.
We declare a string variable called operationCode to denote the two operations taken to generate the first sequence as per Collatz method: divide by 2 (we’ll call it “div2”) and the 3n+1 (we’ll call it “3n1”). The Dictionary array objects will hold the number being operated on, and the operation code that was applied to the number to generate the next number in sequence. (Keep in mind, if the user input is 1, then the number of steps is 0, since there will be no operations needed on it and the program as written will handle it gracefully and accurately).
Explanation: This is the main loop where we check if the number is even or odd and apply the appropriate operation on it, and update the sequence list (originalList, which is an array), and also update the dictionary with the operation code each time. We increment the steps variable by 1 and continue until we’re at 1 (the userinput variable, which gets reused and holds the newly generated number in the loop).
This is my favorite block because this is where we go backward: I re-create the whole sequence and the original input number. First, get the length of the dictionary we created previously. Each key-value pair counts as 1 item. This will size (var sz) will help us find the exact number of times we need to loop to create a reversed sequence dynamically. Using append() method of the dictionary, we insert new items as we calculate the numbers. Notice, going backward in this loop, I start with 1 so, thenumber var starts at 1, and repeatedly goes through the operations on it until the size of the dictionary is exhausted. The type of operation is according to what we defined and saved earlier “div2” or “3n1”.
However, since we’re reversing here, if we find that the number that we got to was a result of “div2” as the dictionary tells us, to find its preceding number, we have to multiply it by 2. If the number’s associated operation is “3n1”, we have to deduct 1 and then divide the result by 3 to find its preceding number.
The final else: condition should never happen if everything went correctly, however, I like to keep it because it’s a good practice to catch all possible conditions and it helps in debugging during development.
You may notice the usage of lower() methods. This is necessary because Python “smartly” decided to change the character’s case of operationCode values when retrieving a stored value from a dictionary object. Even though I saved exactly “div2” string value, when I call title() method to retrieve it, it returns “Div2” which obviously means the string comparison would fail and the whole thing would fail. By converting both sides to lower cases and then comparing the strings solves that problem.
The last part of the code is just displaying the results on screen so we can actually verify its accuracy. A sample output is shown below.
Sample Session:
NOTES:
- So why did I pick 3n+1 instead of n+1 (my method)? Because 3n+1 is trickier to reverse, and that’s more globally known than my conjecture (I’m not famous).
- The code is in Python, although we can do it in C/C++ or any other language the same).
- This code works with ANY positive number in both directions. I’ve tried a value in trillions and the results are “instantaneous” even on a moderate PC.
