Threaded Mode | Linear Mode

Gamo · 07-06-2018, 10:16 AM

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

Thomas Klemm · 07-06-2018, 06:59 PM

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

Dieter · (This post was last modified: 07-06-2018 07:21 PM by Dieter.)

(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

Dieter · 07-06-2018, 07:25 PM

(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

Joe Horn · (This post was last modified: 07-06-2018 09:50 PM by Joe Horn.)

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.

Thomas Klemm · 07-06-2018, 10:31 PM

(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

Gamo · 07-07-2018, 01:51 AM

Thanks to Dieter and Thomas Klemm

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

Gamo Smile

Joe Horn · 07-07-2018, 03:10 AM

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

Dieter · 07-07-2018, 07:36 AM

(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

Thomas Klemm · 07-07-2018, 08:37 AM

(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

Joe Horn · 07-07-2018, 02:24 PM

(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

Dieter · (This post was last modified: 07-07-2018 05:00 PM by Dieter.)

(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

Joe Horn · (This post was last modified: 07-07-2018 07:05 PM by Joe Horn.)

(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".