[PYTHON] Projecet Euler 12 Ermitteln Sie die Anzahl der Brüche ohne Division.

Problem

Die Folge von Dreiecken wird durch die Summe der natürlichen Zahlen dargestellt, das siebte Dreieck ist 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Die ersten 10 Terme des Dreiecks sind:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Wird sein.

Das Folgende ist eine Liste der Kürzungen für die ersten sieben Begriffe.

1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28

Daraus ist ersichtlich, dass das siebte Dreieck 28 das erste Dreieck mit mehr als fünf Verkleinerungen ist.

Also, was sind die ersten Dreiecke mit mehr als 500 Reduzierungen? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2012

Mathematische Überlegung

Es ist schwierig, eine Dreieckszahl zu sagen, aber der Punkt ist, dass eine Dreieckszahl eine Zahl ist, die durch die Summe der natürlichen Zahlen von 1 bis n dargestellt wird. Die Summe der natürlichen Zahlen von 1 bis n wird durch die folgende Formel ausgedrückt.

n * (n+1) /2

Und da n und (n + 1) zueinander Primzahlen sind (keinen gemeinsamen Primfaktor haben), sind n / 2 und n + 1 oder n und (n + 1) / 2 auch Primzahlen zueinander. Ob es n / 2 und n + 1 oder n und (n + 1) / 2 sein soll, hängt davon ab, welches gerade ist. Die Anzahl der Fraktionen, die durch Multiplizieren der natürlichen Zahlen n1 und n2 erhalten werden, die sich gegenseitig primieren, ist gleich der Anzahl, die durch Multiplizieren der Anzahl der Fraktionen von n1 und der Anzahl der Fraktionen von n2 erhalten wird.

Antwortrichtlinie 1

Basierend auf den obigen mathematischen Überlegungen werden wir diese Frage mit dem folgenden Algorithmus beantworten.

Erstellen Sie mit mymath eine Liste mit Primzahlen. 　mymath.py 　http://qiita.com/cof/items/45d3823c3d71e7e22920
Während die Anzahl der Brüche innerhalb von 500 liegt, wird die Variable n in der Schleifenschleife in der Reihenfolge von 1 inkrementiert.
Nachdem Sie festgestellt haben, ob n + 1 gerade ist oder nicht, führen Sie die Primfaktorisierung n + 1 oder (n + 1) / 2 unter Verwendung der Primzahlenliste durch.
Ermitteln Sie die Anzahl der Brüche von n + 1 unter dem erhaltenen Primfaktor und multiplizieren Sie sie mit der Anzahl der zuvor gespeicherten Brüche von n.
Merken Sie sich die multiplizierte Zahl als eine Zahl von ungefähr und kehren Sie zu 2 zurück.

Code

import mymath

def cof():
  pri = mymath.get_primes(10**4)
  n = 1
  num_fac = 1
  lim = 500
  n1_fac =  mymath.get_number_of_factor(n,pri)
  while num_fac < lim:
    n += 1
    if (n+1)%2:
      n2_fac =  mymath.get_number_of_factor(n+1,pri)
    else:
      n2_fac =  mymath.get_number_of_factor((n+1)/2,pri)
    num_fac = n1_fac * n2_fac
    n1_fac = n2_fac
  print n * (n+1) / 2

Entdeckung von Problemen und neues Bewusstsein

Als ich versuchte, es auszuführen, waren es 1,62 Sekunden pro Ausführung, was auf der Poop-Ebene langsam ist. Als ich mich fragte, ob ich es irgendwie beschleunigen könnte, wurde mir klar, dass die Faktorisierung in erster Linie die Ursache für die Langsamkeit war. Mir ist aufgefallen, dass dieselbe Methode wie Eratostenes verwendet werden kann, um den Bruchteil jeder Zahl ohne Division zu erhalten.

Antwortrichtlinie 2

Für mehr Details,

Erstellen Sie eine Liste für jede Nummer. "" "," ", ..."
Führen Sie eine Schleife von 1 zu einer geeigneten Anzahl durch und fügen Sie die Anzahl der Ziele als Element an einer Position hinzu, die ein Vielfaches der Anzahl der Ziele beträgt. Zum Beispiel, wenn 2 die Zielnummer ist [[]. [1], [1], [1], [1] ← Fügen Sie 2 zu der Liste hinzu, die dem Vielfachen 4 entspricht, wie 6,8,10 unten.
Wiederholen Sie 2 und seltsamerweise erhalten Sie eine Liste der wahren Brüche der entsprechenden Zahlen. [[].[1],[1],[1],[1,2],[1],[1,2,3],[1],[1,2,4],[1,3],[1,2,5],...]
Ermitteln Sie anhand dieser Liste der Reduzierungen die Anzahl der Reduzierungen von n in Antwortrichtlinie 1.

Code

Die folgenden Funktionen wurden zu mymath hinzugefügt.

def factor_seq(max):
  ret = [[0]]
  for i in range(max):
    ret += [[1]]
  seq = range(max+1)
  for i in seq[2:max//2+1]:
    for j in seq[i*2::i]:
      ret[j] += [i]
  return ret

Codiert mit den oben genannten

def cof2():
  fq = mymath2.factor_seq(10**5)
  n = 1
  num_fac = 1
  lim = 500
  n1_fac = len(fq[n])
  while num_fac < lim:
    n += 1
    if (n+1)%2:
      n2_fac =  len(fq[n+1])
    else:
      n2_fac =  len(fq[(n+1)/2])
    num_fac = n1_fac * n2_fac
    n1_fac = n2_fac
  print n * (n+1) / 2

Infolgedessen waren es 640 ms, ein Level, das ich ertragen konnte. Wenn Sie in factor_seq "ret [j] + = [i]" in "ret [j] + = 1" ändern, erhalten Sie möglicherweise eine Bruchzahl. Ich denke, es wird schneller, wenn Sie diese verwenden.