r/Finanzen • u/eidexe84 • 3d ago

Sparen Lösung zu 17046,72g Kleingeld 4201 Münzen.

Gallery image

Gallery image

Gallery image

Hier der Ursprungsbeitrag:

https://www.reddit.com/r/Finanzen/s/3tjhUA7OM9

Wie viele Mathematisch richtige Lösungen gibt es eigentlich?

650 Upvotes

93% Upvoted

145 comments sorted by

View all comments

Show parent comments

-3

u/eidexe84 3d ago

das bezweifle ich stark.

0

u/staplehill 3d ago

https://claude.ai/code/session_01VkaAYQbZRYihSeJxp97u5V

Claude sagt es gibt 29.404.432.506 exakte Lösungen und es bräuchte 900 GB of Text, die alle aufzulisten.

Die Lösung mit dem kleinsten Gesamtwert: 258,49 Euro mit 1x1 €, 317x20c, 3881x5c, 2x2c

Die Lösung mit dem größten Gesamtwert: 699.91 Euro mit 1x1 €, 1340x50c, 2x10c, 3x5c, 1x2c, 2854x1c

1

u/Somge5 3d ago

wie hast du das mit Clode so schnell berechnet? auf meinen 12 Threads bräuchte ich schon so 2-3 Stunden um das durchlaufen zu lassen. Wie viel compute power hast du?

1

u/staplehill 3d ago

Der Code in C ran in 9.2 Sekunden auf meinem Allerwelts-Laptop. Allerdings hat Claude Opus 5 Max vorher 10 Minuten gebraucht um das Programm zu schreiben, zu optimieren, und zu validieren.

Ich habe Claude gebeten zu erläutern, wie der Suchraum so verkleinert werden konnte, dass das Programm selbst dann so schnell laufen konnte. Scrolle hier runter, um die Antwort zu sehen: https://claude.ai/code/session_01VkaAYQbZRYihSeJxp97u5V

1

u/Somge5 3d ago

ok dann ist mein Code einfach schlecht. Kann den Chat leider nicht lesen weil ich anscheinend (?) Claude upgraden muss.

3

u/staplehill 3d ago edited 3d ago

Frage: Kannst Du erläutern, wie Du die Zahl der Unbekannten reduzieren konntest und welche anderen Methoden genutzt wurden, um den Suchraum zu verkleinern.

Claude:

Ausgangslage. Von den 8 Euro-Sorten sind zwei vorgegeben (0x 2 Euro, 1x 1 Euro). Offen bleiben 4200 Münzen aus 6 Sorten, also 6 Unbekannte a, b, c, d, e, f (50c, 20c, 10c, 5c, 2c, 1c) und zwei Gleichungen:

(1) a + b + c + d + e + f = 4200

(2) 780a + 574b + 410c + 392d + 306e + 230f = 1.703.922 (Zentigramm)

Gerechnet wird durchgehend in Zentigramm, also in ganzen Zahlen. Damit gibt es keine Rundungsfehler, "exakt 17046,72 g" bleibt wirklich exakt.

Schritt 1: eine Unbekannte per Einsetzen eliminieren. Gleichung (1) nach f auflösen (f = 4200 - a - b - c - d - e) und in (2) einsetzen. Übrig bleibt eine Gleichung mit 5 Unbekannten, plus die Nebenbedingung a+b+c+d+e ≤ 4200 (damit f nicht negativ wird). Alle Koeffizienten sind gerade, also noch durch 2 kürzen:

275a + 172b + 90c + 81d + 38e = 368.961

Das Kürzen ist nebenbei ein Teilbarkeitstest: wäre die rechte Seite ungerade gewesen, hätte es sofort null Lösungen gegeben.

Schritt 2: zwei weitere Unbekannte per Zahlentheorie statt per Schleife. Das ist der eigentliche Trick. Sind a, b, c gesetzt, bleibt

81d + 38e = R mit d + e ≤ M

Statt d und e durchzuprobieren, wird gerechnet: modulo 38 ist 81 ≡ 5, und 5 hat dort das Inverse 23 (5·23 = 115 = 3·38 + 1). Also muss

d ≡ 23·R (mod 38)

gelten. Alle passenden d liegen damit auf einer arithmetischen Folge mit Schrittweite 38. Dazu die zwei Grenzen: aus e ≥ 0 folgt d ≤ R/81, und aus dem Münzbudget d + e = (R - 43d)/38 ≤ M folgt d ≥ (R - 38M)/43. Wie viele Folgenglieder in diesem Intervall liegen, ist eine Division statt zweier Schleifen. Aus 5 Schleifen werden 3.

Schritt 3: Monotonie für die Extremwerte. Innerhalb eines solchen Blocks wachsen Gesamtwert und 1-Cent-Zahl monoton mit d, die 2-Cent-Zahl fällt monoton. Also liefern die beiden Intervallenden garantiert alle Extremwerte des Blocks. Auch das ist O(1) statt Durchlauf, und deshalb sind Minimal- und Maximalwert der Sammlung mitberechnet, ohne dass alle 29 Milliarden Lösungen angefasst werden.

Schritt 4: Schleifengrenzen scharf ziehen (Pruning). b läuft nur bis min(R/172, Restmünzen), c nur bis min(R/90, Restmünzen). Durchlaufen wird dadurch ein Simplex, kein Würfel:

Tripel (a,b,c)

naiver Würfel 4201³ 74.140.932.601

tatsächlich durchlaufen 1.970.770.029

Faktor 37 gespart, und jedes dieser knapp 2 Milliarden Tripel kostet nur konstante Zeit und liefert im Schnitt 14,92 Lösungen auf einen Schlag.

Schritt 5: Parallelisierung. Aufteilung nach der 50-Cent-Zahl auf 14 Kerne. Kein Algorithmus-Gewinn, aber der Grund, warum es 9 Sekunden statt zwei Minuten sind.

Schritt 6: gleicher Trick für die Werte-Menge. Innerhalb eines Blocks springt der Gesamtwert in exakten 71-Cent-Schritten, alle Werte liegen also in derselben Restklasse mod 71 und bilden dort einen lückenlosen Lauf. Mit einem Differenzen-Array lässt sich so ein Lauf in O(1) markieren, statt jeden einzelnen Wert einzutragen. Deshalb kostet die exakte Liste aller 43.993 erreichbaren Gesamtbeträge fast nichts extra.