Ich bin kürzlich sehr süchtig nach Project Euler geworden und versuche, das zu tun Nächster! Ich habe mit einer Analyse begonnen und das Problem bereits erheblich reduziert. Hier ist meine Arbeit:
A = pqr und
1 / A = 1 / p + 1 / q + 1 / r so pqr / A = pq + pr + qr
Und wegen der ersten Gleichung:
pq + pr + qr = 1
Da genau zwei von p, q und r haben um negativ zu sein, können wir das vereinfachen Gleichung bis zum Finden:
abc für welches ab = ac + bc + 1
Lösen für c erhalten wir:
ab-1 = (a + b) c
c = (ab-1) / (a + b)
Das heißt, wir müssen a und b für finden was:
ab = 1 (mod a + b)
Und dann unser A-Wert mit denen a und b ist:
A = abc = ab (ab-1) / (a + b)
Tut mir leid, wenn das eine Menge Mathe ist! Aber jetzt müssen wir uns nur mit einer Bedingung und zwei Gleichungen befassen. Jetzt, da ich die 150.000ste kleinste Ganzzahl finden muss, die als ab (ab-1) / (a + b) mit ab = 1 (mod a + b) geschrieben wird, möchte ich idealerweise nach (a, b) suchen, für die A ist so klein wie möglich.
Zur Vereinfachung habe ich ein & lt; b und ich habe auch festgestellt, dass gcd (a, b) = 1.
Meine erste Implementierung ist unkompliziert und findet sogar 150.000 Lösungen schnell genug. Es dauert jedoch viel zu lange, um die 150.000 kleinsten Lösungen zu finden. Hier ist der Code trotzdem:
%Vor%Mein nächster Gedanke war, Stern-Brocot-Bäume zu verwenden, aber das ist einfach zu langsam, um Lösungen zu finden. Mein endgültiger Algorithmus war, den chinesischen Restsatz zu verwenden, um zu überprüfen, ob verschiedene Werte von a + b Lösungen ergeben. Dieser Code ist kompliziert und obwohl er schneller ist, ist er nicht schnell genug ...
Ich habe also absolut keine Ideen mehr! Hat jemand irgendwelche Ideen?
Wie bei vielen Project Euler-Problemen besteht der Trick darin, eine Technik zu finden, die die Brute-Force-Lösung in etwas direkteres reduziert:
%Vor%Also,
%Vor%Ohne Verlust der Allgemeinheit, 0 & lt; p & lt; -q & lt; -r
Es existiert k, 1 & lt; = k & lt; = p
%Vor%Aber r ist eine ganze Zahl, also trennt k p ^ 2 + 1
%Vor%Um A zu berechnen, müssen wir also über p iterieren, und k kann nur Werte annehmen, die Teiler von p squared plus 1 sind.
Wenn wir jede Lösung zu einer Menge hinzufügen, können wir aufhören, wenn wir die erforderliche 150000. alexandrische Ganzzahl finden.
Dieser Artikel über den chinesischen Rest, schnelle Implementierung, kann Ihnen helfen: www.codeproject.com/KB/recipes/CRP.aspx
Dies ist mehr Links für Werkzeuge und Bibliotheken:
Extras:
Maxima Ссылка Maxima ist ein System zur Manipulation von symbolischen und numerischen Ausdrücken, einschließlich Differenzierung, Integration, Taylor-Reihen, Laplace-Transformationen, gewöhnlichen Differentialgleichungen, linearen Gleichungssystemen, Polynomen und Mengen, Listen, Vektoren, Matrizen und Tensoren. Maxima liefert numerische Ergebnisse mit hoher Genauigkeit, indem exakte Brüche, Ganzzahlen mit beliebiger Genauigkeit und Gleitkommazahlen mit variabler Genauigkeit verwendet werden. Maxima kann Funktionen und Daten in zwei und drei Dimensionen darstellen.
Mathomatic Ссылка Mathomatic ist eine kostenlose, portable, universelle CAS (Computer Algebra System) und Rechner-Software, die Gleichungen symbolisch lösen, vereinfachen, kombinieren und vergleichen kann, komplexe Zahlen- und Polynomarithmetik durchführen kann, etc. Es ist etwas Kalkül und sehr einfach zu handhaben benutzen.
Scilab www.scilab.org/download/index_download.php Scilab ist ein numerisches Berechnungssystem ähnlich Matlab oder Simulink. Scilab enthält Hunderte von mathematischen Funktionen und Programme aus verschiedenen Sprachen (wie C oder Fortran) können interaktiv hinzugefügt werden.
Mathematikstudio mathstudio.sourceforge.de Ein interaktiver Gleichungseditor und Schritt-für-Schritt-Solver.
Bibliothek:
Armadillo C ++ Bibliothek Ссылка Die Armadillo C ++ Library zielt darauf ab, eine effiziente Basis für lineare Algebra-Operationen (Matrix- und Vektormathematik) bereitzustellen, während sie eine einfache und einfach zu verwendende Schnittstelle besitzt.
Blitz ++ Ссылка Blitz ++ ist eine C ++ Klassenbibliothek für wissenschaftliches Rechnen
BigInteger C # Ссылка
libapmath Ссылка Willkommen auf der Homepage des APMath-Projekts. Ziel dieses Projektes ist die Implementierung einer beliebigen C ++ - Bibliothek, die am einfachsten zu verwenden ist. Das bedeutet, dass alle Operationen als Operator-Overlaimings implementiert sind. Die Benennung ist meistens die gleiche wie die von.
libmat Ссылка MAT ist eine C ++ - Klassenbibliothek für mathematische Vorlagen. Verwenden Sie diese Bibliothek für verschiedene Matrixoperationen, um Polynome zu finden, Gleichungen zu lösen usw. Die Bibliothek enthält nur C ++ - Header-Dateien, so dass keine Kompilierung erforderlich ist.
Animath Ссылка Animath ist eine vollständig in C ++ implementierte Finite-Elemente-Methodenbibliothek. Es eignet sich für die Simulation von Fluid-Struktur-Wechselwirkungen und basiert mathematisch auf tetraedrischen Elementen höherer Ordnung.
OK. Hier ist etwas mehr mit meiner chinesischen Remainder-Theorem-Lösung. Es stellt sich heraus, dass a + b nicht das Produkt einer Primzahl sein kann, es sei denn p = 1 (mod 4) . Dies ermöglicht eine schnellere Berechnung, da wir nur a + b überprüfen müssen, die Vielfache von Primzahlen sind, wie 2, 5, 13, 17, 29, 37 ...
Hier ist ein Beispiel für mögliche a + b Werte:
%Vor%Und hier ist das vollständige Programm, das den chinesischen Restsatz verwendet:
%Vor%Das ist besser, aber ich hoffe, es weiter zu verbessern (zum Beispiel scheinen a + b = 2 ^ n niemals Lösungen zu sein).
Ich habe auch angefangen, grundlegende Substitutionen wie:
in Erwägung zu ziehena = u + 1 und b = v + 1
ab = 1 (mod a + b)
uv + u + v = 0 (mod u + v + 2)
Allerdings kann ich damit nicht viel Verbesserung sehen ...
Tags und Links algorithm math python-3.x diophantine