Cardano Drillinge |
21.03.2015, 16:49 | Nasenstein | Auf diesen Beitrag antworten » | |||||||
Cardano Drillinge Ich habe das Problem 251 auf Project Euler gefunden und mich an den Versuch gemacht, den Fall zu lösen. Reinfall, was sonst. Es geht um folgende Gleichung: Eine Lösung ist (2;1;5), für (a+b+c) <= 1000 bestehen 149 Lösungen. Ich weiß mittlerweile, dass a in der Form 3t+2, t >= 0, besteht. Das hilft aber nur bedingt weiter. Ist es möglich die Formel zu vereinfachen, so dass die ein oder andere Wurzel verschwindet? Meine Ideen: Ich hatte bereits versucht, die Wurzeln verschwinden zu lassen bzw. zu minimieren. Leider ohne Erfolg; das Ergebnis war danach noch komplizierter |
|||||||||
21.03.2015, 17:50 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Ich kann allenfalls dieses passend ergänzen, so dass man einige Lösungstripel erhält. kannn ein beliebige positiver Teiler von sein, und dazu passt dann . Ob das nun alle Lösungstripel sind, vermag ich (noch) nicht zu überblicken. Erklärung: Ermittelt "heuristisch", und zwar über den Ansatz mit einer "passenden" ganzen Zahl folgt durch Bildung der dritten Potenz . Die Auflösung ergibt dein genanntes , also und damit sowie aus der zweiten Gleichung dann , was dann die genannten Tripelergänzungen erklärt. Wie gesagt, alles nur Heuristik - keine Beweiskraft hinsichtlich Vollständigkeit. EDIT: Und es ist sicher nicht vollständig - für z.B. ist und bei lässt sich ja auch "in der anderen Richtung" als bisher von mir oben betrachtet ein Faktor aus der Wurzel ziehen, d.h. . |
|||||||||
21.03.2015, 18:32 | Nasenstein | Auf diesen Beitrag antworten » | |||||||
Danke, HAL!!! Der ersten Aussage zufolge, läuft es also prinzipiell darauf hinaus, (t+1) für b zu faktorisieren, wodurch ich für jedes b an ein c komme. a, b und c gehören dann in die Formel eingesetzt und, falls (a+b+c) <= Limit, ergeben u. U. ein positives Ergebnis. Voraussetzung wird sein, durch den vielen Wurzelschnickschnack einen minimalen Spielraum zu lassen (epsilon = 10^8 sollte reichen). Das klingt nach einem Plan; ich muss dann nur noch rausfinden, ob alle möglichen Faktoren in Frage kommen oder nur Primfaktoren. |
|||||||||
21.03.2015, 19:35 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Ok, (leicht indexverschoben) nochmal zusammengefasst: Für betrachtet die eindeutige Zerlegung mit quadratfreiem (offenbar ist , siehe oben). Dann ist für einen beliebigen positiven Teiler von das Tripel eine Lösung von . Das ist mit obigen Weg bewiesen. Die Frage ist, sind alle Lösungen so darstellbar? Zumindest habe ich mal alle so konstruierten Tripel mit gezählt, es sind tatsächlich 149. Für sind es 1632, für dann 16916 Tripel. Für taugt mein einfaches MuPAD-Bruteforce-Programm dann sicher nicht mehr - dauert zu lange. War sicher die Absicht der Problemsteller, dass man das Brett nicht derart dünn bohren kann. |
|||||||||
21.03.2015, 19:45 | Nasenstein | Auf diesen Beitrag antworten » | |||||||
Alle Wetter In dem Problem auf PE ist die Obergrenze 110.000.000. Rum wie num. Ich muss das alles erstmal auf- und verarbeiten. Es macht für mich den Eindruck, als ob man nach den Formeln ein Space Shuttle bauen könnte. Dicken fetten Dank nochmals, HAL!!! |
|||||||||
21.03.2015, 21:16 | Nasenstein | Auf diesen Beitrag antworten » | |||||||
Ich hab meine erste Idee umgesetzt (das ist alles gar nicht so einfach für mein simples Niveau): Ich bilde (a) aus 3*t - 1 (optimiert als 2*t + t - 1, wenigstens etwas). Ich bilde (c) aus t^2 * (8*t - 3). Ich faktorisiere (c) und suche in den Faktoren nach Quadratzahlen. Aus denen, die vorhanden sind, ziehe ich die Wurzel und konstruiere ein Triple, was dann den Anforderungen entsprechen muss. Leider dauert das lange wegen der Faktorisierung. Und bei einer Obergrenze von 110 Mio. ist mein t_max > 36 Mio., was im Rahmen der Konstruktion den 64-bit-Rahmen sprengt. Naja |
|||||||||
Anzeige | |||||||||
|
|||||||||
22.03.2015, 12:05 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Ich hab mal meinen brandneuen PC (i7 4790K) rechnen lassen: solche Tripel mit Rechenzeit dank C-Multithreading-Programm noch erträglich: 41 Sekunden
Das kann man auch anders organisieren, so dass alles noch im Rahmen bleibt. Und tatsächlich muss man die nur bis ca. 16.3 Millionen untersuchen, was nochmal Zeit spart. |
|||||||||
01.04.2015, 14:03 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Hallo Nasenstein, hab leider meine PN vernachlässigt und erst jetzt deine Nachricht vom 26.03. gelesen - hoffentlich schaust du bei Gelegenheit mal wieder hier vorbei. Fachliche Fragen beantworte ich nur im Thread, sollen ja alle was davon haben ( ) :
Wir waren oben ja bei der Darstellung der Lösungstripel mit Zahlen , die erfüllen. Mit AMGM kann man abschätzen , d.h. insgesamt gilt daher für die Tripelementsumme . Insofern folgt aus notwendig , das ist eine brauchbare obere Schranke für die zu untersuchenden . Für bedeutet dies , ist schon eine deutliche Zeitersparnis, zumal große immer "teurer" in der Berechnung werden. -------------------------------------------------------------------------------------------------------- Was "große" betrifft ist dein Code m.E. reichlich ineffizient. Ich liste mal auf, wie ich für festes die möglichen Tripel bestimmt habe:
Dass die Primfaktor- und -exponenten-Felder nur 16 Einträge fassen, ist keine wirkliche Einschränkung in der Praxis - das reicht bis zu Zahlen kleiner als das genügt für den vollen Bereich der 64Bit-Integerzahlen. EDIT: Mit einem "vorberechneten" Array der zum Testen benötigten Primzahlen (etwa per Eratosthenes-Sieb rasch berechnet) kann man die Rechenzeit nochmals von 41 auf 19 Sekunden drücken. Da schafft man dann auch die Anzahl der Tripel mit in 405 Sekunden. |
|||||||||
10.04.2015, 19:27 | Nasenstein | Auf diesen Beitrag antworten » | |||||||
Ooooookay. Das klingt nach Durchfuchsen Trotzdem ein riesiges Danke! |
|||||||||
14.08.2020, 09:46 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Angeregt durch diese Wurzelei möchte ich nach über 5 Jahren (!) mal noch die Beweislücke in obiger Herangehensweise schließen, d.h., warum es so ein ganzzahliges geben muss. Mit dem Ansatz mit zunächst beliebig reellem folgt , aufgeschlüsselt Offenkundig ist ganzzahlig. Die Annahme, dass dieser Wert nicht durch 3 teilbar ist, führt mit der zweiten Gleichung und daraus folgend zum Widerspruch, da dann die linke Seite durch 3 teilbar ist und die rechte nicht. ist somit tatsächlich eine ganze Zahl. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|