(12C) 3n + 1 conjecture

07062018, 10:16 AM
Post: #1




(12C) 3n + 1 conjecture
This program allows to test the 3n + 1 conjecture.
Consider an integer n. If it's even, divide it by 2 (n÷2) If it's odd, multiply by 3 and add 1 (3n + 1) No matter what value of n, the sequence will always reach 1. The question is: if we start with an arbitrary integer will we always reach 1? Nobody knows. Example: Start with integer 17 17 R/S > 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 Program: Collatz conjecture Code:
Gamo 

07062018, 06:59 PM
Post: #2




RE: (12C) 3n + 1 conjecture
A bit shorter and without using registers:
Code: 01 43 31 PSE Cheers Thomas 

07062018, 07:13 PM
(This post was last modified: 07062018 07:21 PM by Dieter.)
Post: #3




RE: (12C) 3n + 1 conjecture
(07062018 10:16 AM)Gamo Wrote: This program allows to test the 3n + 1 conjecture. What? More than 30 steps? And even R0 is used? Waaaayyyy too complicated. ;) Code: 01 FIX 0 Hint: if you want to check if n is even there is no need to check if 2*frac(n/2) is zero. Testing frac(n/2) will do. This again means that n/2 still is in LastX, so 6*LastX yields 3*n.... Still too long? Replace the final lines 13...18 with LstX GTO 00. The numbers are then displayed with [R/S]. Dieter 

07062018, 07:25 PM
Post: #4




RE: (12C) 3n + 1 conjecture  
07062018, 09:50 PM
(This post was last modified: 07062018 09:50 PM by Joe Horn.)
Post: #5




RE: (12C) 3n + 1 conjecture
I'm not familiar with programing the 12C, but perhaps the following "trick" can be used to shrink the program even further. The following sequence changes any even X to X/2, and any odd X to (3X+1)/2, which is valid for this conjecture since 3*odd+1 is always an even number.
01 ENTER 02 ENTER 03 2 04 / 05 ENTER 06 FRAC 07 x=0? 08 GTO 10 09 + 10 + Putting this into a loop which pauses at each iteration, and exits when it reaches 1, is left as an exercise for the programmer. <0ɸ0> Joe 

07062018, 10:31 PM
Post: #6




RE: (12C) 3n + 1 conjecture
(07062018 09:50 PM)Joe Horn Wrote: I'm not familiar with programming the 12CMe neither. It took me way longer that I like to admit to write that program. Quote:The following sequence changes any even X to X/2, and any odd X to (3X+1)/2, which is valid for this conjecture since 3*odd+1 is always an even number.That's true, but the number 3X+1 is missing. So instead of 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, ... we get: 27, 41, 62, 31, 47, 71, 107, 161, ... Cheers Thomas 

07072018, 01:51 AM
Post: #7




RE: (12C) 3n + 1 conjecture
Thanks to Dieter and Thomas Klemm
Both programs are good example to learn on how to code efficiently. Gamo 

07072018, 03:10 AM
Post: #8




RE: (12C) 3n + 1 conjecture
(07062018 10:31 PM)Thomas Klemm Wrote:(07062018 09:50 PM)Joe Horn Wrote: The following sequence changes any even X to X/2, and any odd X to (3X+1)/2, which is valid for this conjecture since 3*odd+1 is always an even number.That's true, but the number 3X+1 is missing. Correct, but if the goal is to "to test the 3n + 1 conjecture" (OP), then there is no need to show 3X+1, since every 3X+1 will always be even. So the program is not only shorter but also faster. <0ɸ0> Joe 

07072018, 07:36 AM
Post: #9




RE: (12C) 3n + 1 conjecture
(07062018 09:50 PM)Joe Horn Wrote: I'm not familiar with programing the 12C, but perhaps the following "trick" can be used to shrink the program even further. The following sequence changes any even X to X/2, and any odd X to (3X+1)/2, which is valid for this conjecture since 3*odd+1 is always an even number. OK, but if you want to show the complete sequence (both x/2 and 3x+1) two more steps are required: Code: 01 ENTER (07062018 09:50 PM)Joe Horn Wrote: Putting this into a loop which pauses at each iteration, and exits when it reaches 1, is left as an exercise for the programmer. Adding this makes the program as long as Thomas' and my version. ;) Dieter 

07072018, 08:37 AM
Post: #10




RE: (12C) 3n + 1 conjecture
(07072018 03:10 AM)Joe Horn Wrote: Correct, but if the goal is to "to test the 3n + 1 conjecture" (OP), then there is no need to show 3X+1, since every 3X+1 will always be even. So the program is not only shorter but also faster. In this case we can use this short and very fast program instead: Code: 01 1 From On the 3x + 1 problem: Quote:In 2017 the yoyo@home project checked all numbers up to 87.260 (± 1.003E+20) for convergence. Cheers Thomas 

07072018, 02:24 PM
Post: #11




RE: (12C) 3n + 1 conjecture
(07072018 07:36 AM)Dieter Wrote:(07062018 09:50 PM)Joe Horn Wrote: I'm not familiar with programing the 12C, but perhaps the following "trick" can be used to shrink the program even further. The following sequence changes any even X to X/2, and any odd X to (3X+1)/2, which is valid for this conjecture since 3*odd+1 is always an even number. Ah, but the OP did not state that the entire sequence needs to be displayed, but rather only that the conjecture be tested. (07072018 08:37 AM)Thomas Klemm Wrote: In this case we can use this short and very fast program instead: Heh heh! Cute, but it does not actually do what the OP requested, which is test the conjecture. The following program does so, and is shorter and faster than the programs above. You might be thinking, "But if not displaying the 3X+1 terms in the sequence can be tolerated, then why not just eliminate the PSE entirely, reducing the program to 15 steps? This would still test the hypothesis, and run MUCH faster, but it would be really boring to watch!" To which I would reply, "Quite right." Code: 01 ENTER <0ɸ0> Joe 

07072018, 04:57 PM
(This post was last modified: 07072018 05:00 PM by Dieter.)
Post: #12




RE: (12C) 3n + 1 conjecture
(07072018 02:24 PM)Joe Horn Wrote: Ah, but the OP did not state that the entire sequence needs to be displayed, but rather only that the conjecture be tested. In this case you can omit the PSE completely and wait until the program finishes with a "1". But the fun is watching the numbers go up und down. ;) Regarding the program: it does not display 3x+1 but (3x+1)/2. That's why I suggested the two additional steps in my last post. If you modify your program accordingly... Code: 01 ENTER ...it will return the correct sequence: 17 => 52 26 13 40 20 10 5 16 8 4 2 1 Note: the position of the PSE has been changed so that the final 1 is not displayed twice. Dieter 

07072018, 07:04 PM
(This post was last modified: 07072018 07:05 PM by Joe Horn.)
Post: #13




RE: (12C) 3n + 1 conjecture
(07072018 04:57 PM)Dieter Wrote: In this case you can omit the PSE completely and wait until the program finishes with a "1". Which is exactly why I wrote this: (07072018 02:24 PM)Joe Horn Wrote: You might be thinking, "...why not just eliminate the PSE entirely..." (07072018 04:57 PM)Dieter Wrote: But the fun is watching the numbers go up und down. ;) Which is exactly why I wrote this: (07072018 02:24 PM)Joe Horn Wrote: "This would still test the hypothesis, and run MUCH faster, but it would be really boring to watch!" To which I would reply, "Quite right." Of course, my program DOES show the numbers going up and down. It merely skips the unnecessary 3X+1 terms, since EVERY 3X+1 must always be even, so you might as well save time by dividing those by 2 right away, no? (07072018 04:57 PM)Dieter Wrote: Regarding the program: it does not display 3x+1 but (3x+1)/2. But that's PRECISELY what my goal is. I don't want to display those terms, because they are unnecessary to attain all the stated goals of this program! My program does what the OP asked for, AND it shows the numbers going up and down (like hailstones in a storm), AND it's shorter and faster. (07072018 04:57 PM)Dieter Wrote: If you modify your program accordingly ... it will return the correct sequence. "Correct sequence"? The Wikipedia page about the Collatz Conjecture says, "The standard Collatz map defined above is optimized by replacing the relation 3n+1 with the common substitute 'shortcut' relation (3n+1)/2." That's "correct" enough for me. Disclaimer: The above is near and dear to my heart because it was the subject of my HHC 2014 talk, "Hailstone Numbers: A Pattern Has Been Found", in which the above "shortcut" was called the "Modified Syracuse Algorithm" which can be used to test the original Collatz Conjecture more efficiently than using the original 3x+1 "Syracuse Algorithm". <0ɸ0> Joe 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)