N=3x+1

If N is even: N = N/2
If N is odd: N = 3N + 1
Prove the result/cycle does not end (or contain) 1.

Example:



The question/problem is -- do ALL numbers end/result in 1 at some point in the cycle? Can this be proven?

Quote: RS

If N is even: N = N/2
If N is odd: N = 3N + 1
Prove the result/cycle does not end (or contain) 1.

The question/problem is -- do ALL numbers end/result in 1 at some point in the cycle? Can this be proven?

Yes, of course, the Collatz conjecture. This was already a big unknown problem when I was a Ph.D. student over 35 years ago. I thought about solving this problem using the fact that 3-adic integers are compact. Nope.

https://en.wikipedia.org/wiki/Collatz_conjecture

The question of provability is unknown. Your question ventures into Godel territory, that there are Theorems that are not provably true.

Back when I taught Java at UCSB, it was one of my favorite programming problems to have students use the BigInteger class to explore this and search for a counter example. From the Wiki article, this conjecture has been shown to be true for N up to 2^60.

I don't know how to prove this mathematically to the standard of proof needed. You all know this about me, so let's stipulate it.

I think N has to be limited to positive integers, though, not just "numbers" as RS stated above. Maybe that was implied, or maybe "ALL numbers" is a word trap in the problem as presented; not sure which.

However, given the constraints of N, where N, if it is odd of any value, is made even (+1), then divided by 2 until it is again odd of any value, it must logically loop down to 1, then repeat. The 3N is the element that makes it eventually total a power of 2 (with the +1 each time), no matter how many intermediate steps are taken.

That's because every other number generated will be divisible by 2, but every so often that number will also be divisible by a power of 2 (the interval of "so often" will be dictated by the starting number). When it's just going even/odd/even/odd, N is gaining +1N in value (disregarding the +1 addition) each time, but any number that can /2 twice is a cumulative -1N, any number /2 3x is a cumulative -5N, any number /2 4x is a cumulative -13N, etc. The shape of the formula forces N to eventually dwindle, since the odd side of it can only gain a net 1 per operation, while the evens can more than negate that gain. And as N dwindles, the power-of-2 numbers get closer together in occurrence; at some point, the formula forces N into one of them.

I tried the following number: 34445333343437 , as a 12-digit prime. It took approx. 260 (sorry, I lost count) operations, but eventually it reduced to a power-of-two, then to 1 (repeating), as in RS's example above. Just FWIW; it could have been any number (positive integer).

Quote: beachbumbabs

I don't know how to prove this mathematically to the standard of proof needed. You all know this about me, so let's stipulate it.

I think N has to be limited to positive integers, though, not just "numbers" as RS stated above. Maybe that was implied, or maybe "ALL numbers" is a word trap in the problem as presented; not sure which.

It is common in number theory to phrase questions like RS did, with the assumption that the question is for positive integers.

For example, find all X, Y and Z such that X^2 + Y^2 = Z^2. (Classify all Pythagorean triples).

Quote:

However, given the constraints of N, where N, if it is odd of any value, is made even (+1), then divided by 2 until it is again odd of any value, it must logically loop down to 1, then repeat.

Sorry, there is no logic known that solves this problem. I am not sure if you thought you were giving an argument in favor of the statement. But just in case you thought you were, you didn't.

Threads like this make me realize how much of a dult that I am.

Quote: GWAE

Threads like this make me realize how much of a dult that I am.

Yeah, two many numbers (and letters, I mean x, y, n, w, t, f).

HINT: I know what the last three letters are.

I saw a YouTube video (I think by Numberphile) about this problem. I found it interesting. I was hoping someone who hadn't heard of the problem would give it a shot....then I realized, anyone who's probably math-literate enough to seriously attempt this, probably already knows about it. =(

My thought for proving this would be to work in reverse, instead of starting at N (ie: N = 12)....start at 1. Then solve for what N could have been on the previous step (N = 1, so previous N = 2, so previous N = 4, so previous N = 8 or 1, so previous N = 16 [forget the N=1 branch], so Previous N = 32 or 5....so previous N = 64 or 10....so previous N = 128, 20, or 3....so Previous N = 256, 40, or 6....so Previous N = 512 or 85 (both from N=256), 80 (from N=40), or 12 (from N=6)....etc.

From this, we know the following numbers do not "win" (end in non-1):
1
2
3
4
5
6
8
10
12
16
20
32
40
80
85
128
256
512
<and any other number listed above...perhaps I missed one or two...and I think I didn't find each possible previous N, ie: N=64 could have also gone to prevN = 21>

But, that still doesn't get us anywhere, I don't think. But using the above method, you should be able to get every number for N...and if you can't, then proof by contradiction (I think? been a while since I took a Logic course...never liked those!).

Not a formal proof, but I run similar to beach babs. every odd number will be turned even, and roughly be tripled. every even number will be cut in half, and then have a 50/50 chance of being even or being odd. The expected number of times you will cut in half on an even number will be 2. So the typical branch from odd to another odd will cost you 0.75, thus all numbers will tend towards 1. In the case of 34445333343437, the expected result would be 103.5 odd to odd cycles are expected to be needed to get to 4, for a total of 310.6 expected iterations to get to 4 (where the loop forms). Pretty close to the 260 beachbumbabs got

Quote: teliot

It is common in number theory to phrase questions like RS did, with the assumption that the question is for positive integers.

For example, find all X, Y and Z such that X^2 + Y^2 = Z^2. (Classify all Pythagorean triples).

Sorry, there is no logic known that solves this problem. I am not sure if you thought you were giving an argument in favor of the statement. But just in case you thought you were, you didn't.

No, I was talking it through "out loud", not trying to make any definitive statements. (That was what I meant by saying "FWIW" at the end.) I found it interesting. I can "see" how it's true in every case, but I don't have the vocabulary to prove it to a certainty.

Thanks for your polite restraint. I almost followed the discussion and its links you provided on wiki, but they lost me towards the end.

Quote: beachbumbabs

Thanks for your polite restraint.

Yep. You know how I get triggered by math around here. At least this question is interesting (unlike the endless threads devoted to 0^0, .9999 = 1, etc.) It is particularly interesting to me because (1) I tried to solve it, and (2) I used to give it as a programming exercise. I am a bit baffled by the manner the OP posted this, as-if anything about it was an answerable question. This question may essentially be the halting problem (Wiki that!)

I wish I hadn't read this because I dreamed about this all night.

If you have already determined that 1 to n will have 1 in the sequence, and you are now testing n+1, you must only find one number in its sequence that is less than n+1. This means you don't need to test even numbers, since the next number in the sequence will be lower, and you can also skip every other odd number (starting with 3) because the third number in the sequence will be lower.

For instance, if you have shown that 1 to 1000 all have 1 in the sequence, then you don't need to test 1001 (sequence 3004, 1502, 751) or 1002 (sequence 501), since 751 and 501 are both < 1001.

To test 1003, follow the sequence 1003, 3010, 1505, 4516, 2258, 1129, 3388, 1694, 847. We can stop at 847, since it is less than 1003.
Now, we don't have to test 1004, 1005, 1006.

If you can show for any number that its sequence will contain a lower number, then it will be proven that all numbers will have 1 in their sequence.

If there is to be a solution, then there will either be infinite solutions or there will be a finite number of solutions that form a loop, that is the number will have itself in its sequence (besides the 1, 4, 2, 1 sequence) . If it can be shown that a number can never be in it's own sequence, then the looped sequences must not exist, leaving only an infinite number of solutions.

I really thought this would get it off my mind, but I don't think I'm so fortunate.

so, if every N that's even is eliminated by being immediately divisible by 2 to a lower value, and every N that is odd is immediately made even via 3N+1, how can any number not eventually become divisible not just by 2, but by some power of 2, and gradually decrease? It's like tuning a sine wave, splitting the amplitude to a harmonic, re-tuning, splitting, etc. Eventually they all flat-line. The structure of the equation forces the inequality to the original N.

the issue is that to use that shortcut, ALL numbers up to N have to be solved. So if 3N+1 is not divisible by 4, you have to cycle through until you hit a number smaller than N.

Quote: GamerMan

the issue is that to use that shortcut, ALL numbers up to N have to be solved. So if 3N+1 is not divisible by 4, you have to cycle through until you hit a number smaller than N.

Sorry if I didn't make myself clear. I was taking what CM said into account; it's a beautiful deduction.

Interesting question. I've been playing around with this in Excel for a few hours. Whatever large starting number you pick, you get about 2/3 evens and 1/3 odds in the series. This makes sense because an odd will always lead to an even, but an even can lead to an odd or even with 50/50 chance, at least for random numbers. The average even streak will be two in length -- so one would expect two evens for every odd.

3*(1/2)*(1/2) = 3/4, so it would seem obvious to expect a decreasing series. Since the numbers are all integers, it would seem likely to end up at 1 eventually. However, I can't explain why there are not exceptions.

I do like the decreasing sequence rationale…but it doesn’t say anything about if a number can return to itself before reaching 1 (creating an infinite cycle).

Like how we know this doesn’t work for ‘5N+1’ since 13 has a sequence of [13,66,33,166,83,416,208,104,52,26,13,…..]

Quote: PeeMcGee

I do like the decreasing sequence rationale…but it doesn’t say anything about if a number can return to itself before reaching 1 (creating an infinite cycle).

Like how we know this doesn’t work for ‘5N+1’ since 13 has a sequence of [13,66,33,166,83,416,208,104,52,26,13,…..]

I took it that the formula was unique to 3N. I think it matters that N only increases by 1N+1 at most every full cycle. I could be wrong.

I guess there could be other N multipliers, but I think you'd have to adjust the other side as well.

Quote: GWAE

Threads like this make me realize how much of a dult that I am.

I know just what you mean. I some how got some sort of paper cut on my thumb and even with the band-aid thingamajing on it, it remains a bit sensitive so now I have to start all my mathematical calculations on a different finger.

I am so reminded of the student who wrote on the test paper following the instructions to "find x" an arrow and the words 'there is it'. I saw a tee shirt the other day (snorgtees) Another day goes by where I don't use any algebra! Ofcourse those Snorgtees are always very attractive for other reasons as well.

So here I sit, at a keyboard wearing a tee shirt from the Riveria that reads WINNER. Maybe I'll win enough money to get together a passline bet in a two dollar game.

Quote: PeeMcGee

I do like the decreasing sequence rationale…but it doesn’t say anything about if a number can return to itself before reaching 1 (creating an infinite cycle).

That I find to be the more intriguing way of asking the question too.

For any number to occur in its own sequence, we must find n and m that satisfy 2^n-3^m=1. The only solution I'm aware of is n=2, m=1, which is a loop which contains 1 multiplication and 2 divisions (specifically, this loop: 1, 4, 2, 1).

If it can be shown that no other n and m satisfy this, then it can be shown there is no other solution that loops back to itself.

Quote: CrystalMath

For any number to occur in its own sequence, we must find n and m that satisfy 2^n-3^m=1.

I'd be interested to see the proof.

Quote: Wizard

I'd be interested to see the proof.

Pretty sure it was faulty logic.