(12C) 3n + 1 conjecture
07-06-2018, 10:16 AM
Post: #1
 Gamo Senior Member Posts: 711 Joined: Dec 2016
(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.

17 R/S --> 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Program: Collatz conjecture
Code:
 01 ENTER 02 ENTER 03 STO 0 04 RCL 0 05   2 06   ÷ 07 FRAC 08   2 09   x 10 X=0? 11 GTO 13 12 GTO 23 13 RCL 0 14   2 15   ÷ 16 PSE 17 STO 0 18   1 19 X<>Y 20 X≤Y? 21 GTO 31 22 GTO 01 23 RCL 0 24   3 25   x 26   1 27   + 28 PSE 29 STO 0 30 GTO 01 31 RCL 0

Gamo
07-06-2018, 06:59 PM
Post: #2
 Thomas Klemm Senior Member Posts: 1,545 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
A bit shorter and without using registers:
Code:
01-   43 31   PSE 02-       2   2 03-      10   ÷ 04-   43 24   FRAC 05-   43 35   x=0 06-43,33 13   GTO 13 07-   43 36   LSTx 08-       6   6 09-      20   × 10-       1   1 11-      40   + 12-43,33 01   GTO 01 13-       1   1 14-   43 36   LSTx 15-   43 34   x≤y 16-43,33 00   GTO 00 17-43,33 01   GTO 01

Cheers
Thomas
07-06-2018, 07:13 PM (This post was last modified: 07-06-2018 07:21 PM by Dieter.)
Post: #3
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-06-2018 10:16 AM)Gamo Wrote:  This program allows to test the 3n + 1 conjecture.
...
17 R/S --> 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Program: Collatz conjecture

What? More than 30 steps? And even R0 is used? Waaaayyyy too complicated. ;-)

Code:
01  FIX 0 02  2 03  ÷ 04  FRAC 05  x=0?    // check if n was even, n/2 now is in LastX 06  GTO 13 07  LstX    // for odd n... 08  6 09  *       // ...calculate 6*n/2 = 3n... 10  1 11  +       // ...+1 12  1/x     // this moves 3n+1 to LastX 13  1 14  LstX    // at this point LastX is either n/2 (if n was even) or 3n+1 (if n was odd) 15  x<=y? 16  GTO 00  // quit if n is 1 (or less) 17  PSE     // else display new n 18  GTO 01  // and repeat

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
07-06-2018, 07:25 PM
Post: #4
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-06-2018 06:59 PM)Thomas Klemm Wrote:  A bit shorter and without using registers:

I see we both got the same idea. ;-)

Dieter
07-06-2018, 09:50 PM (This post was last modified: 07-06-2018 09:50 PM by Joe Horn.)
Post: #5
 Joe Horn Senior Member Posts: 1,822 Joined: Dec 2013
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-
07-06-2018, 10:31 PM
Post: #6
 Thomas Klemm Senior Member Posts: 1,545 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-06-2018 09:50 PM)Joe Horn Wrote:  I'm not familiar with programming the 12C
Me 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
07-07-2018, 01:51 AM
Post: #7
 Gamo Senior Member Posts: 711 Joined: Dec 2016
RE: (12C) 3n + 1 conjecture
Thanks to Dieter and Thomas Klemm

Both programs are good example to learn on how to code efficiently.

Gamo
07-07-2018, 03:10 AM
Post: #8
 Joe Horn Senior Member Posts: 1,822 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-06-2018 10:31 PM)Thomas Klemm Wrote:
(07-06-2018 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.
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, ...

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-
07-07-2018, 07:36 AM
Post: #9
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-06-2018 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 02 ENTER 03 2 04 / 05 ENTER 06 FRAC 07 x=0? 08 GTO 12 09 + 10 + 11 ENTER 12 +

(07-06-2018 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
07-07-2018, 08:37 AM
Post: #10
 Thomas Klemm Senior Member Posts: 1,545 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-07-2018 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
07-07-2018, 02:24 PM
Post: #11
 Joe Horn Senior Member Posts: 1,822 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-07-2018 07:36 AM)Dieter Wrote:
(07-06-2018 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...

Ah, but the OP did not state that the entire sequence needs to be displayed, but rather only that the conjecture be tested.

(07-07-2018 08:37 AM)Thomas Klemm Wrote:  In this case we can use this short and very fast program instead:
Code:
01   1

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 02 ENTER 03 2 04 / 05 ENTER 06 FRAC 07 X=0 08 GTO 10 09 + 10 + 11 PSE 12 1 13 X<>Y 14 X<=Y 15 GTO 00 16 GTO 01

<0|ɸ|0>
-Joe-
07-07-2018, 04:57 PM (This post was last modified: 07-07-2018 05:00 PM by Dieter.)
Post: #12
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-07-2018 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 02 ENTER 03 2 04 / 05 ENTER 06 FRAC 07 X=0? 08 GTO 12 09 + 10 + 11 ENTER 12 + 13 1 14 X<>Y 15 X<=Y? 16 GTO 00 17 PSE 18 GTO 01

...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
07-07-2018, 07:04 PM (This post was last modified: 07-07-2018 07:05 PM by Joe Horn.)
Post: #13
 Joe Horn Senior Member Posts: 1,822 Joined: Dec 2013
RE: (12C) 3n + 1 conjecture
(07-07-2018 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:
(07-07-2018 02:24 PM)Joe Horn Wrote:  You might be thinking, "...why not just eliminate the PSE entirely..."

(07-07-2018 04:57 PM)Dieter Wrote:  But the fun is watching the numbers go up und down. ;-)

Which is exactly why I wrote this:
(07-07-2018 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?

(07-07-2018 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.

(07-07-2018 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)