I'm trying to use Python to solve the Project Euler problem regarding the Collatz sequence. With some research online, I have come up with the code below. However, it still takes a long time to find the maximum length of the Collatz sequence of the numbers from one to a million after the following improvements.
- Using a list in order to keep track of numbers that are in the Collatz sequence of preceding numbers so that they won't be tested
Not testing any of the numbers in the lower half of interval and not testing any numbers that would make this expression true:
Any criticism is appreciated.
""" 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. """ a= def collatz(n): if n%2==0: return int(n/2) else: return int(3*n+1) def collatz_length(n): b=n c=0 while collatz(b)!=1: a.append(b) b=collatz(b) c=c+1 if collatz(b)==1: break return c d=0 e=0 for g in range(500000,1000000,1): f=g+2 if (f in a) == False and ((f%9==2)or(f%9==4)or(f%9==5)or(f%9==8)or(f%8==5)): print(len(a)) print(f) if collatz_length(f)>e: d=f e=collatz_length(f) print(d) print(e)