Projekt Euler Problem 245
Ich bin jetzt auf Problem 245 , habe aber einige Probleme. Ich habe schon etwas daran gearbeitet, aber ich habe nicht das Gefühl, dass ich wirklich etwas unternommen habe, um es zu lösen. Folgendes habe ich bis jetzt:
Wir müssen n = ab mit a und b positiven ganzen Zahlen finden. Wir können auch annehmen, dass gcd (a, b) = 1 ohne Verlust der Allgemeinheit und somit phi (n) = phi (ab) = phi (a) phi (b).
Wir versuchen zu lösen:
Daher:
An diesem Punkt dachte ich, es wäre eine gute Idee, tatsächlich zu sehen, wie diese Zahlen verteilt wurden. Ich habe ein brutales Programm zusammengehackt, mit dem ich alle (zusammengesetzten) Lösungen bis 10 4 gefunden habe:
%Vor%Wichtig scheint es dort zu sein sind nicht zu viele weniger als die 10 11 Grenze, die das Problem verlangt. Das interessanteste / nützlichste Bit, das ich entdeckte, war, dass k selbst für die großen Werte von n ziemlich klein war. Tatsächlich war das größte k nur 138. (Außerdem scheint es, dass k immer gerade ist.)
In Anbetracht dessen würde ich annehmen, dass es möglich ist, jeden Wert von k zu betrachten und herauszufinden, welcher Wert (s) n mit diesem Wert von k sein kann.
Wenn Sie zu der ursprünglichen Gleichung zurückkehren, beachten Sie, dass sie wie folgt umgeschrieben werden kann:
Da wir k wissen:
Und das ist ungefähr so weit wie ich habe; Ich verfolge immer noch einige meiner Routen, aber ich frage mich, ob ich den Punkt vermisse! Mit einem Brute-Force-Ansatz habe ich die Summe bis zu 10 8 gefunden, also 5699973227 (nur 237 Lösungen für n).
Ich habe ziemlich viele Ideen; Kann jemand Hinweise geben?
Update : Viele Leute haben viel gearbeitet und zusammen konnten wir mehrere Dinge beweisen. Hier ist eine Liste:
n ist immer ungerade und k ist immer gerade. k & lt; = 10 5,5 . n muss quadratfrei sein.
Ich habe jede Lösung gefunden, wenn n = pq (2 Primfaktoren) mit p & gt; q. Ich benutzte die Tatsache, dass für 2 Primzahlen q = k + Faktor (k ^ 2-k + 1) und p = k + [k ^ 2-k + 1] / Faktor (k ^ 2-k + 1). Wir wissen auch für 2 Primzahlen k & lt; q & lt; 2k.
Für n mit zwei oder mehr Primfaktoren sind alle Primzahlen von n größer als k.
6 Antworten
Multiplizieren Primzahlen. Was ich getan habe, ist zunächst jedes 2-Prime-Produkt zu überprüfen; Speichern Sie diejenigen, die Erfolge sind. Dann mit den gespeicherten Produkten, überprüfen Sie diejenigen mit mehr Primzahlen (jedes 3-Prime-Produkt in Ihrer rohen Gewalt gezeigt hat eine 2-Prime-Teilmenge, die funktioniert). Verwenden Sie diese gespeicherten Produkte und versuchen Sie es erneut mit 4 Primzahlen, 5 Primzahlen etc.
Der einzige Nachteil ist, dass Sie ein gutes Sieb oder eine Liste von Primzahlen brauchen.
Hier ist eine Liste der für N & lt; = (10 ^ 7):
2 Primzahlen 15,85,259,391,589,111,319,34,141,4369,1231,17473,25429,28243,47989,52537,65641, 68377, 83767, 91759,100777,120019,144097, 186367, 268321, 286357, 291919, 316171, 327937 , 346063,353029,360301,404797,406867,524851,531721,558013,563767,633727,705667,73 8607, 910489, 970141, 1013539, 1080769, 1093987, 1185433, 1185421, 1223869, 1233823, 12618 07,126,4593,1455889,1487371,1529641,1574383,1612381,1617379,1657531,1793689,20163 79,2095087,2130871,2214031,2299459,2500681,2553709,2609689,2617963,2763697,304475 21,3146677,3397651,3514603,3539017,3820909,3961219,4078927,4186993,4197901,44997 07,4552411,4935883,4975687,5103841,5299351,5729257,5829877,5864581,6017299,62364 01,6802531,6856609,8759011,9059233,9203377,9301603,9305311,9526747,9536899,95832 79,9782347,9900217 3 Primzahlen 255,21845,335923,3817309 4 Primzahlen 65535 5 Primzahlen 83623935
Projekt Euler diskutiert nicht gern Probleme in öffentlichen Foren wie StackOverflow. Alle Aufgaben werden solo erledigt, wenn Sie Probleme haben, können Sie Hilfe für ein bestimmtes mathematisches oder Programmierungskonzept anfordern, aber Sie können nicht einfach entscheiden, wie Sie das Problem lösen können - das bringt Euler aus dem Konzept.
Ziel ist es, selbst zu lernen und Lösungen zu finden und neue Konzepte zu lernen.
Lass mich weitermachen, was ich angefangen habe, aber versuche einen etwas anderen Ansatz. Das Ziel ist wiederum, nur die Zahlen zu finden, die zwei verschiedene Faktoren n = pq haben. Wie Sie bereits festgestellt haben, suchen wir nach den Zahlen, so dass n-phi (n) n-1 teilt. Das heißt, wenn n = pq, dann bedeutet das, dass wir nach p suchen, q so, dass
%Vor%Nehmen wir an, wir fixieren p und suchen nach allen Primzahlen q, die die obige Gleichung erfüllen. Die obige Gleichung sieht nicht sehr leicht zu lösen aus, daher besteht der nächste Schritt darin, q so weit wie möglich zu eliminieren. Insbesondere verwenden wir, dass, wenn a b teilt, auch a b + ka für jede ganze Zahl k teilt. Daher
%Vor%und vereinfacht dies führt zu der Bedingung
%Vor%Wir können annehmen, dass p der kleinere Primfaktor von n ist. Dann ist p kleiner als die Quadratwurzel von 10 11 . Daher ist es möglich, alle Zahlen mit zwei Faktoren zu finden, indem man alle Primzahlen p unterhalb der Quadratwurzel von 10 i durchläuft, dann die Teiler von p ^ 2-p + 1 findet, nach q aufliest und prüft wenn q prim ist und pq eine Lösung des Problems ist.
Dies lässt natürlich immer noch die ganzen Zahlen mit mehr als zwei Primfaktoren übrig. Ein ähnlicher Ansatz funktioniert auch hier, ist aber komplizierter und bedarf weiterer Optimierungen.
Eine Frage, die ich nicht beantworten kann, ist, warum dieses Problem so kompliziert formuliert ist. Konnten die Autoren nicht einfach die Summe der zusammengesetzten ganzen Zahlen verlangen, wobei n-phi (n) n-1 dividiert. Vielleicht verpasse ich da einen großen Hinweis.
Nun, da die Lösungen mit zwei Primfaktoren bekannt sind, werde ich versuchen, einen möglichen Algorithmus zu finden, um Lösungen mit mehr als zwei Primfaktoren zu finden. Das Ziel ist es, einen Algorithmus zu finden, der bei einer zusammengesetzten ganzen Zahl m alle Primzahlen q findet, so dass mq eine Lösung ist. I.e., q muss so sein, dass
%Vor%Lassen Sie
%Vor%Dann natürlich
%Vor%Wie im Fall von zwei Primfaktoren ist es möglich, eine Bedingung für F zu finden, indem man q von der linken Seite der obigen Gleichung eliminiert. Da F mq-1 teilt, teilt es auch
%Vor%und daher auch
%Vor%Also, indem wir alle Teiler F von m phi (m) + m - phi (m) finden und indem wir prüfen, ob (F - phi (m)) / (m - phi (m)) ist prim, es ist möglich, alle Lösungen mq für ein gegebenes m zu finden. Da genügen nur die Teiler F, die
erfüllen %Vor%kann zu neuen Lösungen führen, diese Tatsache kann manchmal genutzt werden, um die Faktorisierung zu optimieren mphi (m) + m - phi (m).
Um nicht zu viel zu verraten, würde ich zwei Dinge vorschlagen:
-
Analysieren Sie die Reihenfolge der Zahlen, die Sie mit Brute-Force erstellt haben: Sie alle haben ein gemeinsames Merkmal. Wenn Sie finden, was es ist, können Sie dann eine Brutalität erzwingen, die Ihren Weg zu einer Lösung zwingt.
-
Suchen Sie einen komplexeren Factoring-Algorithmus. Oder noch besser: Anstatt die Faktoren aus den Zahlen zu finden, bauen Sie die Zahlen aus den Faktoren auf ...
BEARBEITEN: Die Muster, die Sie finden werden, werden nur zu Ihrem Versenken beitragen und Ihnen hoffentlich zeigen, wie Sie durch eine angemessene Manipulation des analytischen Ausdrucks dieselbe Menge an Wissen hätten erreichen können. Ohne dieses Muster zu kennen, fürchte ich, dass es keinen Weg zu einer Lösung gibt. Plus, dies ist wahrscheinlich eines der schwierigsten Probleme von Project Euler, also müssen Sie sich keine Sorgen machen, die Lösung ohne viel Schweiß und Mühe zu finden ...
keine direkte Hilfe für dieses Problem, aber vielleicht interessant für zukünftige Mathematikprojekte: Anstatt WolframAlpha zu verwenden, um die Sequenz zu analysieren, würde ich " Die Online-Enzyklopädie der Integer-Sequenzen " auf research.att.com.
Viel Spaß beim Lösen aller Euler-Probleme!
Ich habe keine vollständige Lösung gefunden, aber ich möchte meine Gedanken teilen. Vielleicht könnte jemand helfen.
Ich glaube, dass man versuchen sollte, das Problem auf
zu reduzierenO (sqrt (n) http: // www.texify.com/img/%5CLARGE%5C%21O%28%5Csqrt%7Bn%7D%29.gif
Komplexität.Die folgenden Fakten können verwendet werden, um die Suche effektiver zu machen:
- Jede Lösung muss eine ungerade Zahl sein
- Jede Lösung muss ein Vielfaches von verschiedenen Primzahlen sein (keine Quadratzahl-Faktoren sind erlaubt)
Andere haben darauf hingewiesen, und es ist einfach, sie nur anhand der grundlegenden Eigenschaften der totient-Funktion zu beweisen.
Ich beginne damit, alle Primzahlen und zusammengesetzten Zahlen bis zu sqrt (10 ^ 11) zu analysieren. Dies ist keine große Aufgabe und die benötigte Zeit sollte deutlich unter der 1-Minuten-Anforderung liegen. Alle Lösungen oberhalb der Quadratwurzel haben die Form:
%Vor%Beim Iterieren des Bereichs 0..sqrt (10 ^ 11) suche ich nach Vielfachen der Anzahl in der Iteration, die Lösungen sind. Ich werde nur den Fall der Multiplikation einer Zahl unterhalb der Quadratwurzel mit einer einzigen Primzahl behandeln. Die Lösungsmenge, die ich auf diese Weise erhalten werde, wird eine Obermenge der Lösungssätze mit zwei Primfaktoren sein. Es wird immer noch nicht die vollständige Lösungsmenge sein, wie Lösungen der Form p1 * p2 * p3, wobei p1p2, p2p3, p1p3 & gt; sqrt (10 ^ 11) nicht gefunden werden.
Sei b die Zahl unter der Quadratwurzel und a die Primzahl, um sie zu multiplizieren.
Wir haben:
Basierend auf den Fakten, dass
%Vor%wir haben
Der Modulo-Teil rechts kann wie folgt geschrieben werden:
Lass mich das vorübergehend akzeptieren
Dann könnte ich die obige Gleichung für a (m = 1) lösen, verifizieren, dass das Ergebnis prim ist und dann habe ich die einzige Lösung, die ein Vielfaches von b ist. Wenn das m nicht innerhalb der Grenzen liegt, um der tatsächliche Modulo zu sein, dann muss ich entweder die Gleichung für verschiedene Werte von k lösen:
(k Werte müssen irgendwie begrenzt sein) oder beweisen, dass in diesem Fall der höhere b & lt; sqrt (10 ^ 11), um dies abzudecken.
Es gibt einen Sonderfall für b prim oder b composite und mb = 0. In diesem Fall:
m = - (kb - 1) b http://www.texify.com/img/%5CLARGE%5C%21m%20%3D%20-%28k_%7Bb%7D%20-%201%29b.gif
Dies kann berechnet werden. Für b eine Primzahl:
m = - ( b-1) b http://www.texify.com/img/%5CLARGE%5C%21m%20%3D%20-%28b%20-%201%29b.gif
Ich muss eine Primzahl a finden, die die Gleichung erfüllt:
Zum Beispiel sei b = 3, phi (b) = 2.
Ich muss lösen:
k [3a-2 (a-1)] - 6 = 1 = & gt; k (a + 2) = 5
Für k = 1, a = 7, eine Primzahl (Lösung) Für alle anderen Werte von k kann die obige Gleichung nicht erfüllt werden.