RS
RS
  • Threads: 62
  • Posts: 8626
Joined: Feb 11, 2014
December 17th, 2015 at 7:11:51 AM permalink
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:

N = 12
Because 12 is even: N/2 = 12/2 = 6
Now N = 6
Because 6 is even, N/2 = 6/2 = 3
Now N = 3
Because 3 is odd, 3N + 1 = 3*3 + 1 = 10
Now N = 10
Because 10 is even, N/2 = 10/2 = 5
Now N = 5
Because 5 is odd, 3N + 1 = 3*5 + 1 = 16
Now N = 16
Because 16 is even, N/2 = 16/2 = 8
Now N = 8
Because 8 is even, N/2 = 8/2 = 4
Now N = 4
Because 4 is even, N/2 = 4/2 = 2
Now N = 2
Because 2 is even, N/2 = 2/2 = 1
Now N = 1
So now we know, N = 12 gives us a result of 1 [at least in some part of the cycle....as the cycle continues...]
Because 1 is odd, 3N + 1 = 3*1 + 1 = 4
Now N = 4
Because 4 is even, N/2 = 4/2 = 2
Now N = 2
Because 2 is even, N/2 = 2/2 = 1
Now N = 1 [and the cycle repeats]



The question/problem is -- do ALL numbers end/result in 1 at some point in the cycle? Can this be proven?
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
Thanked by
MichaelBluejay
December 17th, 2015 at 7:48:59 AM permalink
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.
Climate Casino: https://climatecasino.net/climate-casino/
beachbumbabs
beachbumbabs
  • Threads: 100
  • Posts: 14260
Joined: May 21, 2013
December 17th, 2015 at 9:48:44 AM permalink
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).
If the House lost every hand, they wouldn't deal the game.
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 17th, 2015 at 2:41:08 PM permalink
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.
Climate Casino: https://climatecasino.net/climate-casino/
GWAE
GWAE
  • Threads: 93
  • Posts: 9854
Joined: Sep 20, 2013
December 17th, 2015 at 2:46:24 PM permalink
Threads like this make me realize how much of a dult that I am.
Expect the worst and you will never be disappointed. I AM NOT PART OF GWAE RADIO SHOW
darkoz
darkoz
  • Threads: 296
  • Posts: 11419
Joined: Dec 22, 2009
December 17th, 2015 at 2:54:03 PM permalink
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.
For Whom the bus tolls; The bus tolls for thee
RS
RS
  • Threads: 62
  • Posts: 8626
Joined: Feb 11, 2014
December 17th, 2015 at 3:20:29 PM permalink
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!).
GamerMan
GamerMan
  • Threads: 6
  • Posts: 21
Joined: Mar 12, 2010
December 17th, 2015 at 6:39:26 PM permalink
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
beachbumbabs
beachbumbabs
  • Threads: 100
  • Posts: 14260
Joined: May 21, 2013
December 17th, 2015 at 6:52:09 PM permalink
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.
If the House lost every hand, they wouldn't deal the game.
teliot
teliot
  • Threads: 43
  • Posts: 2871
Joined: Oct 19, 2009
December 17th, 2015 at 7:17:40 PM permalink
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!)
Climate Casino: https://climatecasino.net/climate-casino/
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 18th, 2015 at 12:09:34 PM permalink
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.
I heart Crystal Math.
beachbumbabs
beachbumbabs
  • Threads: 100
  • Posts: 14260
Joined: May 21, 2013
December 18th, 2015 at 1:31:54 PM permalink
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.
If the House lost every hand, they wouldn't deal the game.
GamerMan
GamerMan
  • Threads: 6
  • Posts: 21
Joined: Mar 12, 2010
December 18th, 2015 at 3:31:43 PM permalink
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.
beachbumbabs
beachbumbabs
  • Threads: 100
  • Posts: 14260
Joined: May 21, 2013
December 18th, 2015 at 7:00:29 PM permalink
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.
If the House lost every hand, they wouldn't deal the game.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 18th, 2015 at 7:18:28 PM permalink
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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
PeeMcGee
PeeMcGee
  • Threads: 1
  • Posts: 115
Joined: Jul 23, 2014
December 20th, 2015 at 6:13:10 PM permalink
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,…..]
beachbumbabs
beachbumbabs
  • Threads: 100
  • Posts: 14260
Joined: May 21, 2013
December 20th, 2015 at 7:05:04 PM permalink
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.
If the House lost every hand, they wouldn't deal the game.
FleaStiff
FleaStiff
  • Threads: 265
  • Posts: 14484
Joined: Oct 19, 2009
December 20th, 2015 at 9:10:24 PM permalink
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.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 20th, 2015 at 9:18:44 PM permalink
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 with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 20th, 2015 at 9:59:13 PM permalink
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.
I heart Crystal Math.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
December 21st, 2015 at 4:13:55 AM permalink
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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
CrystalMath
CrystalMath
  • Threads: 8
  • Posts: 1909
Joined: May 10, 2011
December 21st, 2015 at 9:25:18 AM permalink
Quote: Wizard

I'd be interested to see the proof.


Pretty sure it was faulty logic.
I heart Crystal Math.
  • Jump to: