Problem 14 "Spalte mit der längsten Collat-Nummer"
Definieren Sie eine Zahlenfolge, die wiederholt mit der folgenden Formel für eine positive Ganzzahl generiert wird.
n → n/2 (n ist gerade)\\ n → 3n + 1 (n ist ungerade)Ab 13 sieht diese Zahlenfolge folgendermaßen aus:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1Es gibt 10 Terme von 13 bis 1. Es wird angenommen, dass diese Sequenz bei 1 endet, egal mit welcher Zahl Sie beginnen, aber das wurde noch nicht bewiesen (Colats-Problem).
Welche der Zahlen unter 1 Million sollte nun gestartet werden, um die längste Folge von Zahlen zu generieren?
Hinweis: Kann über 1 Million in der Mitte einer Reihe sein
Python
n = 1000000
seq = range(1, n)
collatz_dict = {1: [1]}
def compute_collatz(i):
if(i not in collatz_dict):
if(i % 2 == 0):
collatz = [i] + compute_collatz(i / 2)
else:
collatz = [i] + compute_collatz(3 * i + 1)
collatz_dict[i] = collatz
return collatz_dict[i]
collatz_lenghs = {}
for i in seq:
collatz = compute_collatz(i)
collatz_lenghs[i] = len(collatz)
max_length = max(collatz_lenghs.values())
max_index = collatz_lenghs.values().index(max_length)
max_length_collatz_key = collatz_lenghs.keys()[max_index]
max_length_collatz = collatz_dict[max_length_collatz_key]
result = max_length_collatz_key
print result
print result == 837799
print max_length
print max_length_collatz[:6]
Ergebnis
837799
True
525
[837799, 2513398, 1256699, 3770098, 1885049, 5655148]
Es ist etwas spät, aber ich kann mir keinen guten Weg vorstellen.
Recommended Posts