Understanding 3n + 1 problem
09 Aug 2019
Problem source: Programming Challenges: The Programming Contest Training Manual
Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when the value is 1. For an input n, the cycle length of n is the number of numbers generated up to and including the 1. The cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.
1 10 100 200 201 210 900 1000
1 10 20 100 200 125 201 210 89 900 1000 174
Do I understand the problem?
Here are the key rules that stand out to me:
Rules as I understand them
- If n is even, divide by two
- If odd, multiply by 3 then add 1
- Stop after you have reached the end point
- Keep track of how many cycles there are up to and including the end point.
The first thing I'm going to do is write a test list which includes all of the sample output cases, as well as the example mentioned in the problem statement.
- 1 22 16
- 1 10 20
- 100 200 125
- 201 210 89
- 900 1000 174
The next thing I'm going to do is work out the example given in the problem statement by hand to see if it matches their solution
22 is even so / 2 11 is odd so x 3 + 1 34 is even so / 2 17 is odd so x 3 + 1 52 is even so / 2 26 is even so / 2 13 is odd so x 3 + 1 40 is even so / 2 20 is even so / 2 10 is even so / 2 5 is odd so x 3 + 1 16 is even so / 2 8 is even so / 2 4 is even so / 2 2 is even so / 2 1 Cycle length = 16.
Okay, my workings out matched the example in the problem statement. Now I'm going to do the same thing for the first sample example in the test output, which is '1 10 20'
10 is even so / 2 5 is odd so x 3 + 1 16 is even so / 2 8 is even so / 2 4 is even so / 2 2 is even so / 2 1 cycle length: 7
Well, something went wrong, the expected output was supposed to be 10. I've done the same thing as I did for the 22 example. They both had the same end point of 1.
Reading the problem again, it says determine the 'maximum' cycle length, which implies that there is a 'minimum' cycle length. The emphasis was on including both end points. Was the 1 included in the cycle for 22? Yes.
Hmm, maybe I need to do do the cycle for each individual number from 1 to 10. Let's try it
Cycle length of 10 is 7
Cycle length of 9 is 20, which takes us over the 20 limit, so this isn't the way to go. OH WAIT, maybe that IS the answer. So are we counting the cycles individually for each number and keeping the largest score?? THAT MAKES SENSE.
I did not expect the first problem in the book to be this difficult. But okay, now I think I understand it properly.
Rephrasing problem statement
My program then must count the cycles for each number in the range including both the start and end number, and then return the largest of all of those cycle counts.
Now that I understand the problem statement, the next step is to think about how I'm going to solve the problemas well as set up my developer environment. Will link to it here once the article is started.
Wow, it took me a good 2 hours to actually understand what this problem was actually asking, though I was also getting distracted by a kitten who keeps pouncing on me and the keyboard. He's currently lying on my chest trying to boop my nose with his paws, heart melted.
Time to get ready for work.