Cardano Drillinge

Neue Frage »

Nasenstein Auf diesen Beitrag antworten »
Cardano Drillinge
Meine Frage:
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 unglücklich
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Nasenstein
Ich weiß mittlerweile, dass a in der Form 3t+2, t >= 0, besteht. Das hilft aber nur bedingt weiter.

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. Augenzwinkern


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. . Augenzwinkern
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.
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. Big Laugh
Nasenstein Auf diesen Beitrag antworten »

Alle Wetter geschockt

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!!!
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 verwirrt
 
 
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 Augenzwinkern

Zitat:
Original von Nasenstein
Und bei einer Obergrenze von 110 Mio. ist mein t_max > 36 Mio., was im Rahmen der Konstruktion den 64-bit-Rahmen sprengt.

Das kann man auch anders organisieren, so dass alles noch im Rahmen bleibt. Augenzwinkern

Und tatsächlich muss man die nur bis ca. 16.3 Millionen untersuchen, was nochmal Zeit spart.
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. Augenzwinkern

Fachliche Fragen beantworte ich nur im Thread, sollen ja alle was davon haben ( Big Laugh ) :

Zitat:
Original von Nasenstein
Auch hab ich grad Zementbrocken an den Augen und kann irgendwie nicht erkennen, warum t_max ca. 16,3 Mio ist.

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. smile

--------------------------------------------------------------------------------------------------------

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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
// LLONG sind 64-Bit-Integerzahlen - unter GNU-C wäre das "long long", unter MS Visual Studio eher "__int64".

int CountTriplets (LLONG qT, LLONG qLimit)
{
    LLONG   qNumber1 = qT;
    LLONG   qNumber2 = 8*qT-3;
    LLONG   qA = 3*qT-1;
    LLONG   qB;
    double  fC;
    double  fBBC = ((double)qT)*((double)qT)*((double)qNumber2);
    double  fLimit = qLimit + 0.5;
    LLONG   qPrime;
    LLONG   qPrime2;
    LLONG   qPrimes[16];
    int     nExponent[16];
    int     nCheck[16];
    int     nPrimeIndex = 0;
    int     nPrimeSize;
    int     nPrimeLoop;
    int     nTriplets = 0;
    int     nCount = 0;
    int     nCount2;
    // Simultane Primfaktorzerlegung von qT sowie (8*qT-3) (bei letzterer Zahl nur doppelte Faktoren)
    // Erstmal Primfaktor 2
    while ((qNumber1 & 1) == 0)
    {
        nCount++;
        qNumber1 >>= 1;
    }
    if (nCount > 0)
    {
        qPrimes[0] = 2;
        nExponent[0] = nCount;
        nPrimeIndex++;
    }
    // Nun die ungeraden Primfaktoren, bis maximal zur Wurzel
    qPrime = 3;
    qPrime2 = 9;
    while ((qPrime2 <= qNumber1) || (qPrime2 <= qNumber2))
    {
        nCount = 0;
        if (qNumber1 > 1)
        {
            qB = qNumber1 / qPrime;
            while (qNumber1 == qPrime*qB)
            {
                nCount++;
                qNumber1 = qB;
                qB = qNumber1 / qPrime;
            }
        }
        if (qNumber2 > 1)
        {
            nCount2 = 0;
            qB = qNumber2 / qPrime;
            while (qNumber2 == qPrime*qB)
            {
                nCount2++;
                qNumber2 = qB;
                qB = qNumber2 / qPrime;
            }
            // Primteiler von (8*qT-3) zählen nur im Doppel
            nCount += (nCount2>>1);
        }
        if (nCount > 0)
        {
            // Erfassen in Tabelle
            qPrimes[nPrimeIndex] = qPrime;
            nExponent[nPrimeIndex] = nCount;
            nPrimeIndex++;
        }
        // naechster (eventueller) Primteiler und dessen Quadrat
        qPrime += 2;
        qPrime2 = qPrime*qPrime;
    }
    if (qNumber1 > 1)
    {
        // diese Primzahl kommt noch in die Rechnung
        qPrimes[nPrimeIndex] = qNumber1;
        nExponent[nPrimeIndex] = 1;
        nPrimeIndex++;
        // eine evtl. Primzahl in qNumber2 ist irrelevant fuer die weitere Rechnung
    }
    nPrimeSize = nPrimeIndex;
    // So, nun alle Teiler qB durchtesten (zeitmässig der geringere Teil)
    // Wir beginnen mit qB = 1
    memset(nCheck, 0, nPrimeSize*sizeof(int));
    while (nPrimeIndex >= 0)
    {
        // Summand qB als Teiler zusammenbasteln
        qB = 1;
        for (nPrimeLoop= 0; nPrimeLoop < nPrimeSize; nPrimeLoop++)
        {
            nCount = nCheck[nPrimeLoop];
            while (nCount > 0)
            {
                qB *= qPrimes[nPrimeLoop];
                nCount--;
            }
        }
        // Summand fC ergibt sich als Quotient
        // ACHTUNG: Wegen möglicher Int64-Bereichsüberschreitungen besser als double definiert!
        fC = (fBBC/qB)/qB;
        if (qA+qB+fC <= fLimit)
        {
            // Ok, wir sind noch im Rahmen
            nTriplets++;
        }
        // naechster Teiler
        nPrimeIndex = nPrimeSize-1;
        while (nPrimeIndex >= 0)
        {
            nCheck[nPrimeIndex]++;
            if (nCheck[nPrimeIndex] <= nExponent[nPrimeIndex])
            {
                break;
            }
            nCheck[nPrimeIndex] = 0;
            nPrimeIndex--;
        }
    }
    return nTriplets;
}

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. smile


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. Big Laugh
Nasenstein Auf diesen Beitrag antworten »

Ooooookay. Das klingt nach Durchfuchsen smile

Trotzdem ein riesiges Danke! Freude
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »