import time
import numpy as np

def get_sequence(seed):
	"""
	return a list of the chain generated by the Collatz sequence starting at seed
	"""
	assert seed >= 1
	if seed == 1:
		return [1,4,2,1]
	S = [seed]
	while seed != 1:
		if seed%2:
			seed = 3*seed + 1
		else:
			seed /= 2
		S.append(seed)
	return S
	
def find_longest_chain(N):
	"""
	Find the longest collatz sequence chain generated by a number less than N
	"""
	maxlength = 4
	seed = 1
	for i in range(1,N,1):
		j = len(get_sequence(i))
		if j > maxlength:
			seed = i
			maxlength = j
	return (seed, maxlength)
	
def find_longest_chain_alt(N):
	"""
	One line version of previous routine. Runs in roughly the same amount of time. Disadvantage is having to create entire list of sequence lengths and then take the max.
	"""
	return np.argmax([len(get_sequence(i)) for i in range(1,N,1)])+1
	
def find_longest_chain_alt2(N):
	"""
	alternate approach using dictionary objects {seed: chain length}. Much more efficient since it doesn't need to proceed further once the sequence reaches a term which is a previously computed seed
	"""
	import operator
	r = {}
	r[1] = 1
	r[2] = 2
	for i in range(1,N):
		num = i
		chain = 0
		while num not in r:
			if num % 2 == 0:
				num /= 2
			else:
				num = 3*num + 1
			chain += 1
		r[i] = chain + r[num]
	return (max(r.items(), key=operator.itemgetter(1)))
	
def test1():
	S = get_sequence(837799)
	print(S)
	print(len(S))
	
	
def test2():
	start = time.time()
	print(find_longest_chain_alt2(10**6))
	end = time.time()
	print(end-start)

	start = time.time()
	print(find_longest_chain(10**6))
	end = time.time()
	print(end-start)
	
	start = time.time()
	print(find_longest_chain_alt(10**6))
	end = time.time()
	print(end-start)
	
def main():
	start = time.time()
	print(find_longest_chain(10**6))
	end = time.time()
	print(end-start)

if __name__ == "__main__":
	#test1()
	#test2()
	main()
