Python...

Xyzzy · 2004-02-10, 18:26

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!

More reading: http://www.linuxjournal.com/article.php?sid=3882

ET_ · 2004-02-10, 19:19

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 2⁵⁵)

More about it at http://personal.computrain.nl/eric/wondrous/

Luigi

Xyzzy · 2004-02-10, 20:08

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

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.

Xyzzy · 2004-02-12, 17:58

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

ET_ · 2004-02-12, 18:42

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

Xyzzy · 2004-02-13, 00:30

Very cool!

My goal tonight is to make a Python program to do this...

Xyzzy · 2004-02-19, 20:59

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!

Maybeso · 2004-02-20, 00:51

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.

Xyzzy · 2004-10-31, 00:25

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

marc · 2004-10-31, 09:31

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.

2004-02-10, 19:19	#2
ET_ Banned "Luigi" Aug 2002 Team Italia 2×7×347 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 2⁵⁵) More about it at http://personal.computrain.nl/eric/wondrous/ Luigi

2004-02-12, 15:59	#4
EricR 2³·823 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-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 = holder2 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 = loop2 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, 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 = (x3 + 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
A Python Diver for GMP-ECM...	WraithX	GMP-ECM	122	2023-01-24 04:18
Python Coding Help?	kelzo	Programming	3	2016-11-27 05:16
PHP vs. Python vs. C (all with GMP)	daxmick	Programming	2	2014-02-10 01:45
using libecm from python	yqiang	GMP-ECM	2	2007-04-22 00:14
Help w/ python.	a216vcti	Programming	7	2005-10-30 00:37

2004-02-13, 00:30	#7
Xyzzy Aug 2002 8,563 Posts	Very cool! My goal tonight is to make a Python program to do this...