Proving: 2 is the Limit for x>1

[Chris Miller]

TL;DR

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

 

[jedishrfu]

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

If you start with x=4 then it increases 4,6,9,5,3,2,3,2,3...

Is that right?

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

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.

 

[mfb]

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.

 

[TeethWhitener]

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?

 

[mfb]

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.

 

[TeethWhitener]

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.

 

[mfb]

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.

 

[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.

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]

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.

 

[mfb]

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?

 

[TeethWhitener]

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$.

 

[mfb]

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?

 

[mfb]

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.