Find out the number under 1 million which produces the largest Collatz Sequence

Question

So, I have written a code which calculates the number under n( 1 million in this case) which produces the largest Collatz Sequence in that range().

The problem is given in detail below:

---

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

---

My code:

def main(n):
    list = [1,2]
    for i in range(3,n):
        count = 0
        while i > len(list):
            if i % 2 == 0:
                i = i/2
            else:
                i = 3*i+1
            count += 1
        list.append(count + list[int(i)-1])
    return list.index(max(list))+1

print(main(1000000))

So, what are the ways in which I can make my code more efficient since it takes quite a lot of time to execute?

Answer 1

I changed your main function a little bit to LargestCollatz which runs a bit faster on my machine. I'm not sure but I think the biggest improvement is in comparing two integers (c < i) instead of the len function (i > len(list)). Futhermore I used the impopular break statement and used // (which might be faster) instead of / so i could eliminate an int function.

def LargestCollatz(n):

    # Collatz lengths, first entries are 'hand calculated'
    cl = [0, 1, 2]

    for i in range(3, n):
        c = i
        length = 0
        while True:
            if c % 2 == 0:
                c = c//2
            else:
                c = 3*c+1
            length += 1

            if c < i:
                cl.append(length + cl[c])
                break

    return cl.index(max(cl))

Answer 2

The idea of reusing previous computations is correct, but you should use it to the full extent. As written, the code effectively throws away the whole trace of i. For example, when tracing 7, (that is, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10), you may immediately conclude that all of those numbers are not worthy inspection, for 7 produces longer sequence.

So, instead of the list I recommend to have a dict mapping seen numbers to their respective sequence lengths.

It may also help to keep track of the largest sequence length as you go, rather than scan a very large list twice with list.index(max(list))+1.

Answer 3

def main(n):
    list = [1,2]
    for i in range(3,n):
        count = 0
        while i > len(list):
            if i % 2 == 0:
                i = i/2
            else:
                i = 3*i+1
            count += 1
        list.append(count + list[int(i)-1])
    return list.index(max(list))+1

print(main(1000000))

Looking at your code, it's clear that it is going to take long to execute. First of all, allocations need to change quite often, and for instance collatz(12) will be calculated often. Far from ideal.

As a list:

• Variable named list, don't do that, it's a built-in data-type.
• Spacing around commas and binary operators (+, -) does not follow PEP8. range(3,n) needs to be range(3, n). Also, 3*i+1 should be 3 * i + 1.
• Collatz-ing should be a separate function, instead of doing it inline.
• The list you built is increased with length 1 all the time, which is kinda expensive.

The algorithm itself.

Your algorithm is also far from optimal, calculating collatz(16) several times. First, when trying to add 3, it goes

3 -> 10 (not known) -> 5 -> 16 -> 8 -> 4 -> 2 (I know that!)
4 -> 2 (I know that!)
5 -> 16 -> 8 -> 4 (I know that!)
6 -> 3 (I know that!)

(where I know that! means: the result is stored in list.

See how it does does 5 -> 16 -> 8 -> 4 twice, (and 4 -> 2 twice).

I don't have a current suggestion for a better algorithm, but please think about it.

Answer 4

Based on some of @Jan Kuiken recommendations Instead of using list.index(max(list))+1 which takes a bit of time and len(list) i created three more variables index_position = 0 , list_length = 2 and result in order to keep track of these numbers without having to calculate them again.

def LargestCollatz(n):
    lc_list = [1,2]
    index_position = 0
    list_length = 2

    for i in range(3,n):

        count = 0
        while i > list_length:
            if i % 2 == 0:
                i = i/2
            else:
                i = 3*i+1
            count += 1


        lc_new_item = count + lc_list[int(i)-1]
        lc_list.append(lc_new_item)
        list_length += 1

        if lc_new_item > index_position:
            index_position = lc_new_item
            result = list_length

    return result