Definieren Sie eine Zahlenfolge, die wiederholt durch die folgende 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 → 1 Es 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 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
In Bezug auf die Zahlenfolge von ist die Länge der durch 13 erzeugten Zahlenfolge die Länge der durch 40 plus eins erzeugten Zahlenfolge. Mit anderen Worten wird die Länge der durch 13 erzeugten Zahlenfolge rekursiv berechnet. Darüber hinaus kann der Rechenaufwand reduziert werden, indem das Ergebnis in der Mitte gespeichert wird.
def next(n):
if n % 2:
return n*3 + 1
else:
return n / 2
def add(dict,n1):
n2 = next(n1)
if not n2 in dict:
dict = add(dict,n2)
dict[n1] = dict[n2]+1
return dict
def main():
dict = {1:1}
(max_i,max) = (1,1)
for i in range(2,10**6):
if not i in dict:
dict = add(dict,i)
if dict[i] > max:
(max_i,max) = (i,dict[i])
print (max_i,max)
Das Ergebnis war 2,87 Sekunden, was so langsam war wie ein Dämon. Als ich im Internet suchte, fand ich einen Code, der die Geschwindigkeit verbesserte, indem ich mich nicht an Zahlen (1 Million) erinnerte, die größer als eine bestimmte Zahl waren.
Recommended Posts