6
\$\begingroup\$

The Collatz's Conjecture states that any number can either be halved (if it is even) or multiplied by three and added one to (if it is odd) and eventually reach 1.

I was wondering if there was a more efficient way to work out the series that a number takes to get to one and the amount of steps it takes. The Python (3.x) code is:

i, k = 1, 1
fh=open("results.txt", "w")
print("Started")
def colapatz(x):
    seq = [x]
    j = 0
    while x > 1:
       if x % 2 == 0:
         x = x / 2
         j = j + 1
       else:
         x = 3 * x + 1
         j = j + 1
       seq.append(x)
    fh.write("Value number " + str(i) + " takes "+ str(j) + " steps.\n")
    fh.write("It takes the sequence: " + str(seq) + "\n")

#Call the function
while k<10000:
    k+=1
    i+=1
    colapatz(i)
print("Finished")
fh.close()

The is one of my first python programs that I've ever written, so any improvements would be great.

\$\endgroup\$
7
\$\begingroup\$

One possible improvement is to use recursion and memoization to implement a "dynamic programming" solution. This uses the results of previous calculations to speed up the process, as you will end up calculating the same sub-sequences repeatedly. For example:

def memo(f):
    def func(*args):
        if args not in func.cache: 
            func.cache[args] = f(*args)
        return func.cache[args]
    func.cache = {}
    return func

@memo
def collatz(n):
    if n == 1:
        count, seq = 0, []
    elif n % 2:
        count, seq = collatz(3 * n + 1)
    else:
        count, seq = collatz(n // 2)
    return count + 1, [n] + seq

(Note the use of a decorator to implement the memoization.)

Now, once you've run:

>>> collatz(10)
7, [10, 5, 16, 8, 4, 2, 1]

then e.g. collatz(8) can just be looked up from the cache, so future calculations aren't needed:

>>> collatz.cache
{(1,): (1, [1]), (2,): (2, [2, 1]), (8,): (4, [8, 4, 2, 1]), 
 (4,): (3, [4, 2, 1]), (10,): (7, [10, 5, 16, 8, 4, 2, 1]), 
 (5,): (6, [5, 16, 8, 4, 2, 1]), (16,): (5, [16, 8, 4, 2, 1])}

The downsides of this are:

  1. It uses up a lot of space; and
  2. As it's recursive, a long sequence can hit the recursion limit and crash the program.

Also, note that count == len(seq), so you don't necessarily have to return (and store) both.

\$\endgroup\$
4
\$\begingroup\$

Style:

To get that out of the way: You don't follow the official python conventions. Please read the PEP-8 Styleguide and follow it.

Approach:

As mentioned in @jonrshape's answer you will most probably get a speedup if you cache the method's steps through this.

Naming:

What does colapatz mean anyway?? also... x, j, k, i are not really descriptive names. Consider making them more speaking.

Documentation:

If you were to "publish" this method as usable by the public I'd strongly suggest the use of docstrings.

def collatz(x):
   """returns number of collatz sequence steps.

   The collatz sequence is defined by perfoming mathematical operations 
   defined in the collatz conjecture on a positive number. 
   The conjecture states: If the current number is divisible by 2, divide it by 2,
   else multiply by 3 and add 1. If repeated sufficiently often, the end result is always 1.
   """
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.