20040210, 18:26  #1  
Aug 2002
61·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 Quote:
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! More reading: http://www.linuxjournal.com/article.php?sid=3882 

20040210, 19:19  #2 
Banned
"Luigi"
Aug 2002
Team Italia
2×2,417 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 = Si1 / 2 if Si1 is even Si = Si1 * 3 + 1 if Si1 is odd More about it at http://personal.computrain.nl/eric/wondrous/ Luigi 
20040210, 20:08  #3  
Aug 2002
61×137 Posts 
Quote:
This looks like a fun problem to investigate... 

20040212, 15:59  #4 
1001011010011_{2} 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. 
20040212, 17:58  #5  
Aug 2002
61×137 Posts 
Quote:


20040212, 18:42  #6  
Banned
"Luigi"
Aug 2002
Team Italia
2·2,417 Posts 
Quote:
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 Usage: collatz <number of elements to test> Enjoy it! ;) Luigi Last fiddled with by ET_ on 20040212 at 18:53 

20040213, 00:30  #7 
Aug 2002
61×137 Posts 
Very cool!
My goal tonight is to make a Python program to do this... 
20040219, 20:59  #8  
Aug 2002
61×137 Posts 
Quote:
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 P3450 it took ~15 minutes to get through 1,000,000... If anyone wants to comment on my program (structure, possible simplifications) please do! 

20040220, 00:51  #9 
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 Code:
while x != 1: flag = flag + 1 if x % 2 == 0: x = x / 2 else: x = (x * 3 + 1)/2 flag = flag + 1 And later if you want to track path records, odd counts, even counts, etc, it gets really ugly. 
20041031, 00:25  #10  
Aug 2002
61×137 Posts 
Quote:


20041031, 09:31  #11 
Jun 2004
UK
10001011_{2} 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 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 20041031 at 09:32 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Python Diver for GMPECM...  WraithX  GMPECM  115  20210830 22:54 
Python Coding Help?  kelzo  Programming  3  20161127 05:16 
PHP vs. Python vs. C (all with GMP)  daxmick  Programming  2  20140210 01:45 
using libecm from python  yqiang  GMPECM  2  20070422 00:14 
Help w/ python.  a216vcti  Programming  7  20051030 00:37 