Tägliches Codierungsproblem: Dreieckszahlen und große Teiler

Willkommen zurück, alle, die ein anderes Problem zu lösen haben! Heute sprechen wir über Dreieckszahlen und ihre Teiler: insbesondere über große!

Während wir meine fabelhafte künstlerische Darstellung von Dreieckszahlen in der Natur bewundern können, lassen Sie uns unsere üblichen Haftungsausschlüsse vornehmen:

1. Dieses Problem wird von der wunderbaren Website bereitgestellt ProjektEuler.net , den Sie abonnieren können Hier ! Es gibt mehr als 800 Mathematik- und Programmieraufgaben zu lösen und ein umfangreiches Archiv an Diskussionen darüber. Es ist im wahrsten Sinne des Wortes das perfekte Werkzeug, um den Kopf zu zerbrechen und etwas Neues zu lernen! Probieren Sie es aus und versuchen Sie, auch Ihre Herausforderungen zu lösen!

   
   

2. Ich bin kein erfahrener Programmierer, sondern nur ein Typ, der gerne über solche Dinge schreibt und seine Aufnahmen gerne teilt. Ich bin mir sicher, dass dies nicht die optimale Lösung ist. Wenn Sie also eine bessere Lösung oder eine Idee zur Optimierung haben, sind Sie herzlich willkommen, wenn Sie diese mit uns teilen möchten!

Genug geredet, mal sehen, was das heutige Problem zu bieten hat:

Die Folge der Dreieckszahlen entsteht durch Addition der natürlichen Zahlen. Die Zahl des siebten Dreiecks wäre also 1+2+3+4+5+6+7=28. Die ersten zehn Begriffe wären:1,3,6,10,15,21,28,36,45,55,…

Lassen Sie uns die Faktoren der ersten sieben Dreieckszahlen auflisten:

Wir können sehen, dass 28 die erste Dreieckszahl ist, die mehr als fünf Teiler hat.

Welchen Wert hat die erste Dreieckszahl mit mehr als fünfhundert Teilern?

Das Problem ist ganz einfach: Wir sollen verstehen, was die erste Dreieckszahl ist, die mehr als 500 Teiler hat. Schauen wir uns zunächst einmal genauer an, was eine Dreieckszahl und ein Teiler ist.

Dreieckszahlen

Dreieckszahlen sind eine bestimmte Teilmenge von Zahlen, die durch die Summe aller natürlichen Zahlen bis zu einer bestimmten Zahl gebildet werden. Sie werden dreieckig genannt, weil man sie immer als Dreieck anordnen kann . Hier sind einige Beispiele:

Im Bild oben sind es die 3., die 4. und die 5. Dreieckszahl. So wird beispielsweise die 3. Zahl als 1+2+3 = 6 gebildet, die 4. als 1+2+3+4 = 10 und so weiter. Im Allgemeinen ist die nᵗʰ-Dreieckszahl Tₙ gleich

Dies ist natürlich eine der berühmtesten Reihen in der Mathematik, die auch von Gauß vorgestellt wurde, der feststellte, dass die Summe aufeinanderfolgender ganzer Zahlen gleich ist:

Wenn wir also zum Beispiel die dritte Dreieckszahl berechnen wollen, berechnen wir einfach 3*4/2 = 6. Das wird sehr hilfreich sein, wenn wir mit dem Schreiben unserer Lösung beginnen!

Die Teiler

Den Teiler (oder Faktor ) einer Zahl n zu definieren, ist ganz einfach: Es handelt sich um eine Zahl j , die mit einer anderen ganzen Zahl k multipliziert werden kann, um wieder n zu erhalten. Beispielsweise ist 3 ein Teiler von 18, da wir 3 und 6 multiplizieren können, um wieder 18 zu erhalten.

Allerdings ist 5 kein Teiler von 18, da es keine Zahl k gibt, die multipliziert mit 5 18 ergibt.

Durch die Definition erhalten wir auch eine wichtige Eigenschaft: Wenn j ein Teiler von n ist, weil es mit k multipliziert werden kann, um n zu erhalten, dann ist auch k ein Teiler von n , weil es mit j multipliziert werden kann, um n zu erhalten.

Auf diese Weise können wir sicher sein, dass eine Zahl n immer mindestens zwei Teiler j und k hat (tatsächlich kann j immer 1 und k immer n sein).

Anders ausgedrückt ist eine Zahl j ein Teiler der Zahl n , wenn der Rest von n / j gleich 0 ist . Also zum Beispiel 18/3 = 6 und der Rest ist 0.

Wir können dieses Konzept mit modularer Arithmetik besser formalisieren und sagen, dass j ein Teiler von n ist, wenn n % j = 0. Mit anderen Worten, wir erhalten diese zweite Eigenschaft:

Die dritte und letzte Eigenschaft, die uns interessiert, ist, dass es außer n selbst keinen Teiler einer Zahl n größer als n/2 geben kann. Das ist ziemlich einfach zu verstehen. Aus der ersten Eigenschaft wissen wir, dass Faktoren im Bereich 1,…,n irgendwie „verknüpft“ sind.

Dies liegt wiederum daran, dass, wenn j \ n, j * k = n ist. Daher auch k\n. Nehmen wir noch einmal 18 als Beispiel, finden seine Teiler und färben sie ein, um diese Eigenschaft widerzuspiegeln.

Wenn also beispielsweise j = 3, k = 6 und umgekehrt, wenn j = 6, k = 3, bedeutet dies, dass das kleinste j, das wir verwenden können, neben 1 2 ist, was uns das größte k ergibt möglich, n/2 (9 in unserem Fall) . Das funktioniert:

• für gerade Zahlen, in diesem Fall ist der größte Faktor genau gleich der Hälfte von n;

• für ungerade Zahlen: wenn wir n nicht durch 2 teilen können (weil ungerade eine rationale Zahl ergibt); das bedeutet, dass wir nur j > 2 verwenden können, was uns immer Ergebnisse k < n/2 liefert.

  
  

Schließlich gibt es nur einen Fall, in dem j und k gleich sein können: wenn n eine Quadratzahl ist. Wenn beispielsweise n = 36 ist, erzeugt ein möglicher Faktor j = 6 einen weiteren Faktor k = 6. Wir werden diesen Fall später im Codeteil näher besprechen.

Diese Konzepte sind natürlich ziemlich trivial, aber sie werden für unsere Lösung sehr wichtig sein!

Der Code

Der Code wird in Go geschrieben, da es sich wirklich um eine schnelle Sprache handelt, die dennoch ein hohes Maß an Lesbarkeit beibehält. Wir werden die Lösung in zwei Teile aufteilen: Zuerst erstellen wir eine Funktion, um die Teiler einer Zahl zu finden, und dann wenden wir sie auf die Dreieckszahlen an .

Schauen wir uns zunächst die Funktion an:

Wir erstellen unsere Funktion, die eine Ganzzahl n akzeptiert und ein Array von Ganzzahlen out , das unsere Teiler enthält. Danach hängen wir die trivialen Faktoren out , nämlich 1 und n selbst.

Dann beginnen wir mit der Schleife j von 2 bis n/2 (von der zweiten Eigenschaft aus; beachten Sie auch, dass wir nicht an n/2 selbst interessiert sind, da für den Fall, dass n gerade ist, k = n/2 durch j = 2 zu den Teilern addiert wird j = 2 Iteration: Deshalb stoppen wir bei j<n/2 und nicht j≤ n/2 ).

Auf diese Weise können wir nur in der ersten Hälfte von n nach Teilern suchen, was den Prozess erheblich beschleunigt.

Bei jeder Schleife prüfen wir drei Dinge:

• Die dritte if-Anweisung prüft tatsächlich, ob n%j==0 , mit anderen Worten, ob 0 ≡ n (mod j). Wenn ja, haben wir einen Faktor gefunden und fügen j zur Liste hinzu. Wir können auch sein Gegenstück k an die Liste anhängen, indem wir n/j berechnen und dann mit dem nächsten j fortfahren;

• Die zweite if-Anweisung prüft, ob n ein Quadrat ist und j also die Wurzel von n ist. Wenn ja, wird nur ein Teiler j zu out hinzugefügt, um Duplikate zu vermeiden, und dann geht der Algorithmus weiter.

  
  

  Angenommen, n = 36 : Wenn dieser kleine Block fehlen würde, würde die dritte if-Anweisung ausgelöst, wodurch out j = 6 und k = n/j = 36/6 = 6 empfangen würde und somit ein Duplikat erstellt würde.

• Die erste if-Anweisung ist die komplexeste: Ihr Zweck besteht darin, zu überprüfen, ob wir beginnen, sich wiederholende JK- Paare zu haben. Wenn ja, können wir die Schleife sofort durchbrechen, da unser Faktor bereits in out vorhanden ist.

  
  

Speziell zu diesem dritten Punkt müssen zwei Fälle überprüft werden: ob out[len(out)-1] == j oder out[len(out)-2] == j .

Der erste Fall ist der klassische: Nehmen wir zum Beispiel die Zahl T₇ = 28:

Wenn j = 7 ist, entspricht es dem zuletzt eingefügten Wert. Daher können wir die Schleife durchbrechen.

Der zweite Fall tritt nur auf, wenn wir ein Quadrat n gefunden haben. Nehmen Sie zum Beispiel noch einmal 36:

Wenn j = 9 ist, entspricht es dem letzten Wert, der vor der Quadratwurzel von n angehängt wird, die nur einmal vorkommt. Daher können wir an dieser Stelle die Schleife durchbrechen.

Schließlich können wir einfach return out , um unsere Teiler zu erhalten.

Anwenden der Ergebnisse

Da wir nun unsere Funktion haben, können wir sie auf jede Dreieckszahl anwenden. Wir werden einen Zähler c erstellen, der als Generator für unsere Dreieckszahlen dient. Wir berechnen die zugehörige Dreieckszahl tn mit der Gauß-Gleichung und prüfen, wie viele Teiler sie hat.

Wenn es mehr als 500 ist, geben wir diesen tn als Ergebnis zurück.

Aber da ist ein Fang!

ProjectEuler.net ist wirklich ein schönes Projekt: Neben der Präsentation von Mathe-Rätseln und -Problemen liegt ihr Hauptaugenmerk darauf, ein Werkzeug bereitzustellen, mit dem man mit dem Lernen, Nachdenken und Nachdenken über Mathematik beginnen kann .

Und ich liebe das: Sie sind so engagiert, dass die Veröffentlichung von Ergebnissen und Leitfäden für ihre Probleme eigentlich verboten ist (dies ist eines der ersten 100 Probleme, daher ist es meines Wissens erlaubt).

Vor diesem Hintergrund halte ich es nicht für fair, die Lösung einfach zum Kopieren und Einfügen herauszugeben und den Erfolg zu erhalten . Aus diesem Grund gebe ich Ihnen nicht die eigentliche Lösung: Probieren Sie es selbst aus und versuchen Sie, einen besseren Algorithmus als meinen zu finden (davon gibt es viele). Tut mir leid, Leute! 😅

Zeitkomplexität

Ich bin zuversichtlich, dass es viele bessere Lösungen gibt, denn meiner Meinung nach ist dies ein ziemlich schrecklicher Schuss!

Die FindDivisor Funktion wird in linearer Zeit ausgeführt: da sie von der Größe der Instanz n abhängt und außerdem höchstens n/2 Schleifen ausführt; wir können es als ein O(n) betrachten.

Allerdings müssen wir zuerst jede Dreieckszahl berechnen, was ebenfalls O(tn) Zeit in Anspruch nimmt, wobei tn das Ergebnis ist (das letzte, das wir tatsächlich berechnen). Vor diesem Hintergrund sollte die zeitliche Komplexität des gesamten Algorithmus ungefähr O(tn*n) betragen.

Da tn zum Argument oder unserer Funktion wird und wir höchstens n/2 Schleifen darin ausführen, können wir die Zeitkomplexität als O(tn*tn/2) = O(tn²/2) = O(tn²) umschreiben. Also leider eine quadratische Zeitlösung !

Ich war jedoch überrascht, dass der Algorithmus trotz dieser Komplexität dennoch ziemlich schnell läuft. Um auf meinem Rechner (AMD Ryzen 5, durchschnittlich 2700 MHz) ein Ergebnis auszugeben, dauerte es 322,564227 ms.

Der Versuch, die erste Dreieckszahl zu finden, die 1000 Teiler überschreitet, dauerte jedoch 3,827144472 Sekunden, sodass deutlich zu erkennen ist, dass der Zeitverbrauch rapide ansteigt.

Abschluss

Wir haben es endlich geschafft! Ich hoffe, euch hat der Artikel gefallen und ich hoffe, dass ihr etwas Interessantes daraus mitnehmen könnt: Wenn ja, lasst bitte ein oder zwei Klatscher da und teilt den Artikel mit jemandem, der an diesem Thema interessiert sein könnte!

Nochmals ein großes Lob an ProjectEuler für die fantastische Arbeit: Ich möchte Ihnen wirklich empfehlen, sich anzusehen, was sie zu bieten haben. Ich bin mir sicher, dass du es super interessant finden wirst!

Und wie immer vielen Dank fürs Lesen.

Nicola