blob: 860174b483dc0fbb749654c97f6f0d2e773deeb6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#!/usr/bin/env python3
# Challenge 054
#
# TASK #2
# Collatz Conjecture
# Contributed by Ryan Thompson
# It is thought that the following sequence will always reach 1:
#
# $n = $n / 2 when $n is even
# $n = 3*$n + 1 when $n is odd
# For example, if we start at 23, we get the following sequence:
#
# 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8
# -> 4 -> 2 -> 1
#
# Write a function that finds the Collatz sequence for any positive integer.
# Notice how the sequence itself may go far above the original starting number.
#
# Extra Credit
# Have your script calculate the sequence length for all starting numbers up to
# 1000000 (1e6), and output the starting number and sequence length for the
# longest 20 sequences.
import sys
def collatz_seq(n):
out = [n]
while n != 1:
if n % 2 == 0:
n = int(n/2)
else:
n = 3*n + 1
out.append(n)
return out
def print_longest():
longest = []
for n in range(1, int(1e6)+1):
count = len(collatz_seq(n))
longest.append([n, count])
longest.sort(key=lambda x:x[0])
longest = longest[::-1]
longest.sort(key=lambda x:x[1])
longest = longest[::-1]
if len(longest) > 20:
longest.pop()
for i in longest:
print(str(i[0])+" "+str(i[1]))
if sys.argv[1] == "-l":
print_longest()
else:
n = int(sys.argv[1])
seq = collatz_seq(n)
print(" -> ".join([str(x) for x in seq]))
|
