# Mini-Collatz

Chris Miller
TL;DR Summary
if is_even(x) then x=+x/2 else x=(x+1)-(x+1)/2 reduces to 2 for any x proof
How would one prove that, for any integer x (where x>1), this series always reduces to 2?

if is_even(x)
x=x+(x/2)
else
x=(x+1)-((x+1)/2)
end

Mentor
You stop at 2?

It seems that it will oscillate 2,3,2,3,2,3... if you start with x=2 or x=3

Is that right?

I wrote a small python v3.7 program to try it out:

Python:
x=int(input("Starting x value: "))

for i in range(10):

if x%2 == 0:
x=x+x//2

else:
x=(x+1) - (x+1)//2

print (x)

Chris Miller
Yes, that's correct. The series always ends toggling between 2 and 3. I have a "for 3 to infinity" type test program that's past 23 million now with the highest number of iterations so far being 441 for test integer 15733192. I've random tested much larger integers: e.g.: 0xffffffffffffffffffffffffffffffabcd took 995 iterations to reach 2.

Last edited:
Mentor
I'm not aware of any non-trivial problem of this kind that would have been solved, I would be surprised if this one has a solution that is known or easy to find.

Chris Miller
Thanks mfb. It strikes me as a lot simpler than the Collatz. I might take your reply as a challenge.

Gold Member
It strikes me as a lot simpler than the Collatz.
Why?

It’s an interesting map: it converts all numbers of the form ##2^n(odd)## to ##3^n(odd)##. Since, given any ##k##, you can always find an ##n## such that ##3^n>2^{n+k}##, it’s plausible to imagine this thing shooting off to infinity for some large power of two. With Collatz, if you hit a power of two, you immediately fall down to 1, but with this, if you hit a power of two, you zoom up, and if you happen to hit another one when meandering back down, you zoom up even further.

Chris Miller
@TeethWhitener

Unlike the Collatz there's no multiplication. Also, the series are shorter. I seriously doubt any power of 2 will shoot off to infinity. Adding powers of 2, e.g., ##\sum_{n=1}^{1024} 2^n## shot up for a while but then resolved to 2 in 995 iterations. I think ##2^{1024}## would ascend to the above summation, and resolved to 2 in 9144 iterations.

##2^{10000}## zoomed up to a 15850 bit value before dropping back to 2 in 82678 total iterations.

Is it possible to hit a power of 2 on the way up?

Last edited:
Mentor
If x is odd then the next step is (x+1)/2, which is a power of 2 if x is one below a power of 2. As an example, 15 -> 8.
Unlike the Collatz there's no multiplication
You multiply by 3/2 if the number is even.

Gold Member
Division is multiplication.

Chris Miller
Right @mfb and @TeethWhitener, and multiplication is just repeated addition. It will only hit powers of 2 on the way down though. To me it seems simpler, if only only because the series descends more rapidly, which is why I thought it might be more easily proved. Maybe I was wrong.

Mentor
It's not the way down if it hits a power of 2, because that will be followed by a series of 3/2 multiplications. I don't see the point.

Chris Miller
@mfb
All I meant was, only processing an odd integer will result in a power of 2, never an even one, so it can never zoom off to infinity. Harder to prove would be that there can be no closed loops higher than 2 3 2 3... Odd and even integers eventually occur about equally, and since x+(x/2) is, percentage wise, a smaller step up than x+1 - ((x+1)/2) is down, the trend is eventually lower.

Mentor
All I meant was, only processing an odd integer will result in a power of 2, never an even one, so it can never zoom off to infinity.
Why not?
Here is a simple sequence that satisfies what you said but it will shoot off to infinity if you start e.g. with 3:
If the number is odd, subtract 1 and divide by 2. If the number is even, multiply by 4 then add 1.

TeethWhitener
Gold Member
Of course it won’t go to infinity monotonically. The argument I’m making is that if you start with ##2^a(odd)##, you end up with ##3^a(odd)##. For ##a\geq3##, there will be a positive ##k## for which ##3^a(odd)>2^{a+k}(odd)##, and if the sequence continues from ##3^a(odd)## to ##2^{a+k}(odd)##, then you zoom up to ##3^{a+k}(odd)##. Rinse, repeat. You have to prove that doesn’t ever happen.

Chris Miller
Why not?
Here is a simple sequence that satisfies what you said but it will shoot off to infinity if you start e.g. with 3:
If the number is odd, subtract 1 and divide by 2. If the number is even, multiply by 4 then add 1.
First, that's a different algorithm. Second, (3-1)/2=1, (1-1)/2=0

Chris Miller
Of course it won’t go to infinity monotonically. The argument I’m making is that if you start with ##2^a(odd)##, you end up with ##3^a(odd)##. For ##a\geq3##, there will be a positive ##k## for which ##3^a(odd)>2^{a+k}(odd)##, and if the sequence continues from ##3^a(odd)## to ##2^{a+k}(odd)##, then you zoom up to ##3^{a+k}(odd)##. Rinse, repeat. You have to prove that doesn’t ever happen.
Had too look up "monotonically." Still don't understand though. ##2^a## is never odd. One would have to prove it can't ascend infinitely, and that there are no looping sequences other than 2,3,2,3,2,3 for any initial value. Proving that your assertion could occur might serve as disproof of the conjecture, even if the integers involved were too large to test.

PS. Looked at your comment some more. Hadn't noticed that ##2^a## (where a is odd and >2) always hits ##3^a##. Might be interesting to prove just that. Cool place to begin. The rest of your conjectures I'll need to think about some more.

Last edited:
Mentor
First, that's a different algorithm.
Yes, I demonstrated that what you wrote is not sufficient. I changed the example but didn't update the starting number, sorry. Start with 5 -> 2 -> 9 -> 4 -> 17 -> 8 -> ...

Your algorithm might guarantee that nothing disappears to infinite, but you didn't provide any argument against it.

Chris Miller
Yes, I demonstrated that what you wrote is not sufficient. I changed the example but didn't update the starting number, sorry. Start with 5 -> 2 -> 9 -> 4 -> 17 -> 8 -> ...

Your algorithm might guarantee that nothing disappears to infinite, but you didn't provide any argument against it.
I never said that there is no algorithm that can produce an infinite series? How about if even or odd add 1?

Gold Member
Looked at your comment some more. Hadn't noticed that 2a (where a is odd and >2) always hits 3a. Might be interesting to prove just that.
The proof is trivial. ##x## is even implies that ##x=2k,k\in\mathbb{N}##. Applying the algorithm converts ##x## to ##x+\frac{x}{2}=\frac{3}{2}x=3k##. That’s your base step. Now you can use induction to prove that your algorithm converts ##2^an## to ## 3^an##.

Mentor
I never said that there is no algorithm that can produce an infinite series? How about if even or odd add 1?
You are missing the point. You claimed that your algorithm cannot produce an infinite series because it has a specific property. I constructed a different algorithm with that property that does produce infinite series, demonstrating that your argument doesn't hold.

Chris Miller
You are missing the point. You claimed that your algorithm cannot produce an infinite series because it has a specific property. I constructed a different algorithm with that property that does produce infinite series, demonstrating that your argument doesn't hold.
What property did I say the algorithm had that no other algorithm could have and ascend to infinity?

Mentor
That's not what you said, or what I said. Here is what you claimed:
All I meant was, only processing an odd integer will result in a power of 2, never an even one, so it can never zoom off to infinity.
"Only odd integers will result in powers of 2" is not a sufficient criterion to be sure it will not go to infinity.

Chris Miller
That's not what you said, or what I said. Here is what you claimed:"Only odd integers will result in powers of 2" is not a sufficient criterion to be sure it will not go to infinity.
I meant odd integers using my function, not any function, obviously. But you're right, I haven't proven (only demonstrated) anything. I'm also not sure it isn't sufficient criterion (with my function), though, as you say, I haven't proven it is.