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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#!/usr/bin/env python3
###########################################################################
# script name: ch-2.py #
# #
# https://github.com/user-person #
# #
# https://perlweeklychallenge.org/blog/perl-weekly-challenge-054/ #
# #
# 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.perl #
# #
###########################################################################
import os
import re
import sys
def msgExit():
print(os.path.basename(sys.argv[0]), "requires one positive integer as an argument (or extracredit).")
exit(1)
high = {}
def checkHighKeys(key,keyCount,highKeys):
if len(highKeys) == 20:
highKeys = {k: v for k, v in sorted(highKeys.items(), key=lambda item: (item[1],item[0]))}
if highKeys[list(highKeys)[0]] < keyCount:
del highKeys[list(highKeys)[0]]
highKeys[key] = keyCount
elif highKeys[list(highKeys)[0]] == keyCount:
if list(highKeys)[0] < key:
del highKeys[list(highKeys)[0]]
highKeys[key] = keyCount
else:
highKeys[key] = keyCount
return highKeys
if len(sys.argv) != 2:
msgExit()
n = sys.argv[1]
extraCredit = False
ecPattern = re.compile(r'-{0,2}extra[-~`!@#$%^&*=+|\\;:",.?/ ]?credit', flags=re.IGNORECASE)
if ecPattern.search(str(n)):
n = 2
extraCredit = True
sys.stderr.flush()
sys.stderr.write('Allow time for calculations.\n')
sys.stderr.write(" They finish when '#'s reach this point-> |\n")
elif re.search(r'\A\d+\Z',str(n)):
n = int(n)
if n < 1:
msgExit()
if n == 1:
print(1)
exit()
else:
msgExit()
MAX = 1000000
i = n
while i <= MAX:
count = 0
while n != 1:
if extraCredit:
count += 1
else:
print(int(n),'-> ', end='',flush=True)
if n % 2 == 0: # EVEN
n /= 2
else: # ODD
n = 3*n + 1
if extraCredit:
high = checkHighKeys(i, count, high)
i += 1
n = i
if n % 20000 == 0:
sys.stderr.write('#')
sys.stderr.flush()
else:
print(1)
break
if extraCredit:
sys.stderr.write('\n\n')
high = {k: v for k, v in sorted(high.items(), key=lambda item: (item[1],item[0]),reverse=True)}
for thisKey in high.keys():
print('Starting number:', thisKey, 'with sequence length:', high[thisKey])
|
