mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2004-02-10, 18:26   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

170138 Posts
Default 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!

More reading: http://www.linuxjournal.com/article.php?sid=3882
Xyzzy is offline   Reply With Quote
Old 2004-02-10, 19:19   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

129E16 Posts
Default

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
ET_ is online now   Reply With Quote
Old 2004-02-10, 20:08   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

7,691 Posts
Default

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


This looks like a fun problem to investigate...
Xyzzy is offline   Reply With Quote
Old 2004-02-12, 15:59   #4
EricR
 

111110001002 Posts
Cool 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.
  Reply With Quote
Old 2004-02-12, 17:58   #5
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

7,691 Posts
Default

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
File Type: py 3x+1.py (171 Bytes, 235 views)
Xyzzy is offline   Reply With Quote
Old 2004-02-12, 18:42   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112368 Posts
Default

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
File Type: zip collatz.zip (7.9 KB, 207 views)

Last fiddled with by ET_ on 2004-02-12 at 18:53
ET_ is online now   Reply With Quote
Old 2004-02-13, 00:30   #7
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

170138 Posts
Default

Very cool!

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

Xyzzy is offline   Reply With Quote
Old 2004-02-19, 20:59   #8
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

7,691 Posts
Default

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
File Type: py collatz.py (303 Bytes, 204 views)
Xyzzy is offline   Reply With Quote
Old 2004-02-20, 00:51   #9
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2×137 Posts
Default

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.
Maybeso is offline   Reply With Quote
Old 2004-10-31, 00:25   #10
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

7,691 Posts
Default

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

Xyzzy is offline   Reply With Quote
Old 2004-10-31, 09:31   #11
marc
 
marc's Avatar
 
Jun 2004
UK

139 Posts
Default

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
marc is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Python Diver for GMP-ECM... WraithX GMP-ECM 114 2020-06-18 12:05
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

All times are UTC. The time now is 17:53.

Sun Sep 20 17:53:58 UTC 2020 up 10 days, 15:04, 1 user, load averages: 2.57, 2.01, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.