mersenneforum.org Python...
 Register FAQ Search Today's Posts Mark Forums Read

2004-02-10, 18:26   #1
Xyzzy

"Mike"
Aug 2002

2·29·137 Posts
Python...

I thought it would be fun to post bits of code every once in a while and discuss them...

http://www.ibiblio.org/obp/thinkCSpy/chap06.htm

Scroll down a bit...

Code:
def sequence(n):
while n != 1:
print n,
if n%2 == 0:        # n is even
n = n/2
else:               # n is odd
n = n*3+1
He then mentions:
Quote:
 Particular values aside, the interesting question is whether we can prove that this program terminates for all values of n. So far, no one has been able to prove it or disprove it!
I found that '-2' goes on forever, and '0' does too... (I'm surprised 0 works because it looks like it is undefined.)

Any thoughts on this? Is this interesting, from a math point of view, or just ordinary stuff?

Is anyone else learning/using Python out there? So far I like it a lot!

 2004-02-10, 19:19 #2 ET_ Banned     "Luigi" Aug 2002 Team Italia 2·3·17·47 Posts It's called Collatz Conjecture, or simply hailstone chain because the values tend to go up and down like hail. Code: For any positive integer N a sequence Si can be defined by putting S0 = N and for all i > 0: Si = Si-1 / 2 if Si-1 is even Si = Si-1 * 3 + 1 if Si-1 is odd It has leaded to only convergent successions up to x = 36,028 E+12 (about 255) More about it at http://personal.computrain.nl/eric/wondrous/ Luigi
2004-02-10, 20:08   #3
Xyzzy

"Mike"
Aug 2002

2×29×137 Posts

Quote:
 ...Special thanks to Luigi Morelli from Italy who was first to join...

This looks like a fun problem to investigate...

 2004-02-12, 15:59 #4 EricR   37×67 Posts Fun problem This problem is usually simply called the "3x+1" problem. If you want the code above to really stop at some point you should put in yet another line, something like: if n = 1 : stop Still, it is unknown whether all positive numbers yield 1 eventually, although there are very strong indications that this is the case. This is called the 3x+1 (or Collatz) conjecture. All numbers up to (almost) 300E+15 have now been shown to reach 1. It can also be shown (Terras Theorem) that if there are numbers not reaching 1 their density tends to zero. This problem looks so simple, but even the best mathematicians have been unable to prove the conjecture. Even the late great Paul ErdÃ¶s could not find any real advances. Even so, one can ask many more questions about these sequences: - which numbers take the longest time to reach 1 - which numbers take the longest time to reach a number less then their starting number - which numbers reach the highest 'peaks' before reachin 1. and so on. You can find much more data on all of these questions on the website mentioned above.
2004-02-12, 17:58   #5
Xyzzy

"Mike"
Aug 2002

2·29·137 Posts

Quote:
 Originally Posted by EricR All numbers up to (almost) 300E+15 have now been shown to reach 1.
Just for fun I ran through the first million and they all terminated...

Attached Files
 3x+1.py (171 Bytes, 268 views)

2004-02-12, 18:42   #6
ET_
Banned

"Luigi"
Aug 2002
Team Italia

12BA16 Posts

Quote:
 Originally Posted by Xyzzy Just for fun I ran through the first million and they all terminated...
Well done, Mike!

Anyway, I think the most interesting numbers are those whose paths are bigger.

Here is a short Delphi program with a fast ASM subroutine to check the best path record of each number in ascendent order.

It creates a list of increasing path records and the number associated with the path. For instance,

Code:
C:\Articoli\Dev\ASM>collatz2 100000000
0             0
3             7
6             8
7            16
9            19
18            20
25            23
27           111
54           112
73           115
97           118
129           121
171           124
231           127
313           130
327           143
649           144
703           170
871           178
1161           181
2223           182
2463           208
2919           216
3711           237
6171           261
10971           267
13255           275
17647           278
23529           281
26623           307
34239           310
35655           323
52527           339
77031           350
106239           353
142587           374
156159           382
216367           385
230631           442
410011           448
511935           469
837799           524
1117065           527
2234130           528
2978841           531
3433215           586
5425327           597
5649499           612
7532665           615
10043553           618
18064027           622
21409215           630
23682175           641
31576233           644
40096999           649
46340775           690
52970523           746
62779879           754
83706505           757
As you can see, the best path record in the range 1-100,000,000 is 757 iterations, obtained with the start number 83,706,505

Usage: collatz <number of elements to test>

Enjoy it! ;-)

Luigi
Attached Files
 collatz.zip (7.9 KB, 243 views)

Last fiddled with by ET_ on 2004-02-12 at 18:53

 2004-02-13, 00:30 #7 Xyzzy     "Mike" Aug 2002 2×29×137 Posts Very cool! My goal tonight is to make a Python program to do this...
2004-02-19, 20:59   #8
Xyzzy

"Mike"
Aug 2002

1F0A16 Posts

Quote:
 Originally Posted by Xyzzy My goal tonight is to make a Python program to do this...
Well, it took me longer than expected...

According to this link the program I wrote does not return path records... I don't exactly understand his explanation of what a path record is...

Obviously, since Python is interpreted, my program is very slow... On a P3-450 it took ~15 minutes to get through 1,000,000...

If anyone wants to comment on my program (structure, possible simplifications) please do!
Attached Files
 collatz.py (303 Bytes, 239 views)

 2004-02-20, 00:51 #9 Maybeso     Aug 2002 Portland, OR USA 2×137 Posts Mike, You (and ET I think) are both looking for path length or D(N), delay records. The path record is the maximum value reached for all M <= N. It will always be > 3N + 1 for odd N. I looked at your code - it's such a simple search, I can't see too many ways to improve it. If you're still looking for delay records - I find them much more interesting than path records: * D(2N) = D(N) + 1, so 2N sets the record only if N holds it. * So you could skip the even numbers and check if 2N sets new one Code: loop = 1 largestsofar = 0 holder = 6 while loop <= 1000000: flag = 0 if loop > holder: largestsofar = largestsofar + 1 print holder, largestsofar holder = holder*2 x = loop while x != 1: flag = flag + 1 if x % 2 == 0: x = x / 2 else: x = x * 3 + 1 if flag > largestsofar: largestsofar = flag holder = loop*2 print loop, flag loop = loop + 2 * You could also try doing as much as you can in each loop: Code:  while x != 1: flag = flag + 1 if x % 2 == 0: x = x / 2 else: x = (x * 3 + 1)/2 flag = flag + 1 * This can be extended by doing a case on x mod 4, or even x mod 8. But it get very difficult to check for x = 1. And later if you want to track path records, odd counts, even counts, etc, it gets really ugly.
2004-10-31, 00:25   #10
Xyzzy

"Mike"
Aug 2002

2·29·137 Posts

Quote:
 Originally Posted by Xyzzy Obviously, since Python is interpreted, my program is very slow... On a P3-450 it took ~15 minutes to get through 1,000,000...
It only takes ~1.5 minutes on a 2.4GHz K8...

 2004-10-31, 09:31 #11 marc     Jun 2004 UK 139 Posts Code: largestsofar= 0 for x in xrange(1,1000000): flag, X = 0, x while x != 1: if x&1: x = (x*3 + 1)>>1 flag += 2 else: x >>= 1 flag += 1 if flag > largestsofar: largestsofar = flag print X, flag Try that. It should be slightly faster since it doesn't do any actual divisions and uses a for loop instead of checking while x < 1000000 since comparisons are slow in Python. Also I put the flag += 1/2 inside the if odd/if even cases since that assures you of only doing 1 addition per loop instead of doing 2 when the number is odd. You could add cases for x & 3 or x & 7 but this turns out to be slower than just letting the loop take its course. Last fiddled with by marc on 2004-10-31 at 09:32

 Similar Threads Thread Thread Starter Forum Replies Last Post WraithX GMP-ECM 114 2020-06-18 12:05 kelzo Programming 3 2016-11-27 05:16 daxmick Programming 2 2014-02-10 01:45 yqiang GMP-ECM 2 2007-04-22 00:14 a216vcti Programming 7 2005-10-30 00:37

All times are UTC. The time now is 13:33.

Wed Jan 27 13:33:12 UTC 2021 up 55 days, 9:44, 0 users, load averages: 5.92, 6.15, 5.83