Comment Re:Just a search for a multiple of 2? (Score 1) 167
Look at the powers of 2. The only way you get to 1 is by coming down to 1. Thus, 2, which must be divided by 2 gives you one. The only way to get 2 is from 4 being divided by 2. In fact, once you end up on any power of two, it is just a number of divisions by 2 to get you to 1. If you end up at 1024, then divide by 2 for ten times and you end up at 1.
So how to you end up on a power of 2? Two possible ways:
1. Half of the next higher power of two.
2. 3n + 1
So what are the powers of two that minus one are evenly divisible by 3. Each number of this form is just one iteration away from a power of two. And the POWER of two is the number of iterations to get to 1 at that point.
Since an "n" for 3n+1 to be a power of 2 is an odd number, the only way you got to it was by dividing an even number. So what are all of the 2n values where 3n+1 is a power of 2?
Now each of these 2n values is even, and therefore is half of another even number, and possibly also a 3n+1 for some odd n.
In Clojure (or some other suitable Lisp, or something close enough to Lisp such as Python), create an infinite stream of powers of two. From that a function filters all powers of 2 that are a 3n+1 for some odd n. From here have functions that when mapped over a stream of evens gives you possible n/2 or 3n+1 forms. Or from a stream of odds gives you n/2 forms. You end up with a list of these lazy infinite streams. And each stream may fork into more streams which are added to the list of streams. Now merge sort the streams. It is important that the streams are lazy -- which is easy to implement in Clojure. Probably easy with Python using a loop with yield. See how long it takes for you to go insane.
So how to you end up on a power of 2? Two possible ways:
1. Half of the next higher power of two.
2. 3n + 1
So what are the powers of two that minus one are evenly divisible by 3. Each number of this form is just one iteration away from a power of two. And the POWER of two is the number of iterations to get to 1 at that point.
Since an "n" for 3n+1 to be a power of 2 is an odd number, the only way you got to it was by dividing an even number. So what are all of the 2n values where 3n+1 is a power of 2?
Now each of these 2n values is even, and therefore is half of another even number, and possibly also a 3n+1 for some odd n.
In Clojure (or some other suitable Lisp, or something close enough to Lisp such as Python), create an infinite stream of powers of two. From that a function filters all powers of 2 that are a 3n+1 for some odd n. From here have functions that when mapped over a stream of evens gives you possible n/2 or 3n+1 forms. Or from a stream of odds gives you n/2 forms. You end up with a list of these lazy infinite streams. And each stream may fork into more streams which are added to the list of streams. Now merge sort the streams. It is important that the streams are lazy -- which is easy to implement in Clojure. Probably easy with Python using a loop with yield. See how long it takes for you to go insane.