Post Reply 
(12C) 3n + 1 conjecture
07-06-2018, 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:

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
Find all posts by this user
Quote this message in a reply
07-06-2018, 06:59 PM
Post: #2
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
Find all posts by this user
Quote this message in a reply
07-06-2018, 07:13 PM (This post was last modified: 07-06-2018 07:21 PM by Dieter.)
Post: #3
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
Find all posts by this user
Quote this message in a reply
07-06-2018, 07:25 PM
Post: #4
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
Find all posts by this user
Quote this message in a reply
07-06-2018, 09:50 PM (This post was last modified: 07-06-2018 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-
Visit this user's website Find all posts by this user
Quote this message in a reply
07-06-2018, 10:31 PM
Post: #6
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
Find all posts by this user
Quote this message in a reply
07-07-2018, 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 Smile
Find all posts by this user
Quote this message in a reply
07-07-2018, 03:10 AM
Post: #8
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-
Visit this user's website Find all posts by this user
Quote this message in a reply
07-07-2018, 07:36 AM
Post: #9
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
Find all posts by this user
Quote this message in a reply
07-07-2018, 08:37 AM
Post: #10
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
Find all posts by this user
Quote this message in a reply
07-07-2018, 02:24 PM
Post: #11
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-
Visit this user's website Find all posts by this user
Quote this message in a reply
07-07-2018, 04:57 PM (This post was last modified: 07-07-2018 05:00 PM by Dieter.)
Post: #12
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
Find all posts by this user
Quote this message in a reply
07-07-2018, 07:04 PM (This post was last modified: 07-07-2018 07:05 PM by Joe Horn.)
Post: #13
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-
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 




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