Project Euler
(Ein Mathe - Marathon)

http://projecteuler.net

[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] [121] [124] [155] [165]

Ein Hinweis am Rande: Mit der Zeit (mit den sich im Internet ansammelnden Lösungen und Diskussionen dazu) werden die Aufgabenstellungen auf ProjectEuler eventuell leicht geändert, so daß Sie die hier gezeigten Lösungen als Testdatensätze verwenden können, aber auf jeden Fall gezwungen sind, eigene Überlegungen zu investieren und die Ergebnisse zu verifizieren. Viel Spaß!

Code anzeigen!
Werkzeug

1 Summe der Vielfachen von 3 und 5 unter 1000

Aufgabe im Euler-Projekt
Das ist:
= Summe(Vielfache von 3) + Summe(Vielfache von 5) - Summe(Vielfache von kgV(3,5)) = 3 * Summe(1...333) + 5 * Summe(1...195) - 15 * Summe(1...66) mit Summe(Vielfache von n) = n * Summe(Vielfache von 1) mit Summe(1...n) = (1+n)*n/2 = 3*55611 + 5*19900 - 15*2211 = 233168

2 Summe der geraden Terme der Fibonacci-Reihe <= 1'000'000

Aufgabe im Euler-Projekt
Die Fibonacci-Reihe hat immer alle drei Zahlen ein gerades Mitglied (wenn zwei ungerade Terme addiert werden).

Ach was, Brute-Force: 2 + 8 + 34 + 144 + 610 + 2584 + 10946 + 46368 + 196418 + 832040 + = 1089154

3 Größter Primfaktor von 317584931803

Aufgabe im Euler-Projekt
Es handelt sich um eine Zahl innerhalb von 64 Bit. Das Zeug geht trivial mit Brute Force (factorize aus der HACL übernommen...):
Faktoren von 317584931803array...
67integer1
829integer1
1459integer1
3919integer1
Kontrolle: 317584931803

4 Größtes Palindrom aus zwei dreistelligen Zahlen

Aufgabe im Euler-Projekt
Was teste ich, wenn ich nicht direkt Brute Force nehme? Die Palindrome selbst als Ausgangswert zu nehmen, könnte weniger Aufwand bedeuten als die Faktoren, oder?

Mit Faktoren (Brute Force) wären es etwa 1 Mill. Tests. Geht.
Das läßt sich aber einschränken, wenn die größten Faktoren weit oben erwartet werden.
Mit Mannipulierung der Ziffern (nur drei Freiheiten) wären es maximal genau 900 Varianten. Wobei auch hier von oben begonnen wird.
Das geht dann auch rux fix auszuführen, allerdings sehr zäh zu programmieren (die Brute Force - Variante benötigt ne Sekunde und war eh zur Fehlersuche notwendig, aber die Aufgaben dienen ja dem Sinn des Übens)...:

Erfolgreiche Zerlegung: 993 * 913 = 906609

5 KGV von 1...20

Aufgabe im Euler-Projekt
Naja, trivial: Primfaktoren zerlegen + vereinen:
ZahlPrimfaktoren
22
33
42 * 2
55
62 * 3
77
82 * 2 * 2
93 * 3
102 * 5
1111
122 * 2 * 3
1313
142 * 7
153 * 5
162 * 2 * 2 * 2
1717
182 * 3 * 3
1919

Primfaktoren vereint:
factorsarray...
2integer4
3integer2
5integer1
7integer1
11integer1
13integer1
17integer1
19integer1
Ergebnis = 232792560

6 Sum^2(1...100) - Sum(1^2...100^2)

Aufgabe im Euler-Projekt
DAS (Element von Statistik / Ausgleichrechnung) soll schwerer sein als das bisherige?!? Unklar!

Delta = 25502500 - 338350 = 25164150

7 10001te Primzahl

Aufgabe im Euler-Projekt
Wir holen uns eine Abschätzung, wo sie zu finden sein wird, und sieben sie einfach geradeheraus (da war die Zerlegung vorhin ohne 64-bit-Integer schwieriger)...

Im Bereich bis 110000 erwartete Primzahlmenge: 11892.9779016 (reicht)
Die 10001te Primzahl lautet: 104743

8 Größtes Produkt von 5 aufeinanderfolgenden Ziffern in...

Aufgabe im Euler-Projekt
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Das ist jetzt aber nur reine Fleißarbeit, gelle?
Ergebnis: 40824

9 Produkt des Triplets a < b < c mit a^2 + b^2 = c^2 und a+b+c = 1000

Aufgabe im Euler-Projekt
Allzuviele Freiheitsgrade haben wir ja nicht:
-> Brute Force... (zu viele Flüchtigkeitsfehler -> funktioniert nicht)

-> Smart Force: Aufstellung der 2 Gleichungen und Umstellung auf direkte Abhängigkeit zwischen a und b -> Lineares Problem, weniger Rundungsfehler...

a: 200, b: 375, c: 425; a+b+c = 1000; a*b*c = 31875000

10 Summe der Primzahlen unter 1 Millionen

Aufgabe im Euler-Projekt
Trivial: 37550402023 (...allerdings kostet das hier schon mächtig Zeit (mehrere Sekunden).

11 Größtes Produkt von 4 Zahlen horiz/vert/diag gesucht

Aufgabe im Euler-Projekt
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

OK: Immer noch reine Fleißarbeit... Die Schwierigkeitsgrade sind eindeutig falsch sortiert. Vielleicht sollten die Jungs mal eine Sortierfunktion in Auftrag geben?

Ergebnis: 70600674

12 Kleinste Summe der natürlichen Zahlen, die über 500 Teiler hat

Aufgabe im Euler-Projekt
OK, die Zahl könnte so um ein paar Tausend herum liegen.

Die "Teilermenge" ermitteln wir durch Kombinatorik aus der Primzahlzerlegung:
Es werden bei gegebenen n Primzahlen alle "Kombinationen" davon mit jeder möglichen Stärke (0 bis n Elemente) gezählt.
Sofern es gleiche Primfaktoren mehrfach gibt, werden alle Kombinationen, die sich unter diesen bilden lassen, abgezogen. Was aber nicht ganz trivial ist. Und was sich als das eigentlich interessante Element erweist...

Der lange Weg zur Erkenntnis:

Sofern KEINE gleichen Faktoren dabei sind, ist es trivial: JEDER Primfaktor kann unabhängig von den anderen in die Kombination eingehen oder nicht. Damit ist die Kombinationsmenge == 2 ^ (Anzahl der Faktoren). Also:
Eine Zahl mit n unterschiedlichen Primfaktoren hat 2^n unterschiedliche Teiler.
Der Fall "kein Faktor" ist mit der Teiler-Variante "1" ebenfalls eingeschlossen.

Hmmm... Pauschal können wir sofort sagen, daß wir 8 Primfaktoren benötigen. Für die Kleinste Zahl, die sich daraus basteln läßt, müßten das die ersten 8 Primzahlen sein (2,3,5,7,11,13,17,19).
Wir können aber 12 Kombinationsplätze verschenken. Daher darf eventuell eine Ziffer (welche?) doppelt vorkommen, also z.B. (2,3,5,7,11,13,17,17).
Wieviel wird jetzt GENAU abgezogen? -> Das reicht bereits: Es geht mehr von den 512 Varianten flöten als erlaubt, um über 500 zu bleiben.
-> Die gesuchte Zahl muß zwingend 2*3*5*7*11*13*17*19 = 9699690 sein! Oder?
Ähhhh... Nein: DAS ist nur die kleinste Zahl, ab der wir mit der Suche beginnen brauchen...
Wir suchen ja nun eine Zahl aus der Reihe der Summen von natürlichen Zahlen, die größer als diese Zahl ist.

Was ich benötige, ist eine kombinatorische Funktion, die mir angibt, wieviele Kobinationsmöglichkeiten bei eventuell mehrfachen Wiederholungen von Auswahl-Kandidaten es gibt. Ich weiß, daß ich das sogar schon mal in der Schule behandelt hatte. Vor vielen, vielen Jahren...

Erste Anlaufstelle:
http://de.wikipedia.org/wiki/Kombinatorik#Ausw.C3.A4hlen_ohne_Beachtung_der_Reihenfolge_.28Kombinationen.29
Das hilft allerdings nicht weiter, weil dort keine für Einzelelemente unterschiedliche Wiederholung betrachtet wird.

Immerhin hilft die Wikipedia auf den Weg der üblichen Terminologie...
Ich habe hier einen Fall der Kombination von Teilen einer Ausgangsmenge von N Teilen zu Gruppen von 0...M Elementen ohne Zurücklegen, wobei Elemente der Ausgangsmenge gleich sein können (so daß das auch ausgedrückt werden kann als K Elemente (K < N), die jedes einen individuellen Wiederholungsfaktor haben, so daß die Summe aller Wiederholfaktoren geich N ist.

Das als Google-Suche zu definieren dürfte unter Zauberei fallen!
Mit dem Begriff '+kombinatorik +wiederholung +"ohne zurücklegen"' finde ich auf den ersten 9 Treffern grundsätzlich identisch genau die Standardfälle erklärt, wo NICHT individuell unterschiedliche Mengen von Ausgangs-Elementen behandelt werden. DIESE Seiten sind allgemeinverständlich formuliert.
Die ERSTE Seite, die VIELLEICHT in die Richtung gehen könnte, die ich benötige, ist: http://www.fernuni-hagen.de/www2bonsai/WTHEORIE/ds/node2.html. Leider drücken DIE sich so aus, daß man halbjahreweise Studienzeit benötigt, nur um die Grundbegriffe einordnen zu können. Von der Problemlösung ganz zu schweigen.

...Die triviale Lösung:

Jeder Primfaktor steht für eine eigene Ziffer in einer Zahl, in der die Ziffern unterschiedliche Varianz (Werte, die sie annehmen können alias Basen) haben dürfen:
Jede individuelle Stelle hat für diese Zahl eine Basis, die 1+Exponent des Primfaktors entspricht.

Also, um mal ein Beispiel zu bringen: Die Zahl 232792560 (aus Aufgabe 5) zerlegt: 2^4 * 3^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1
Das entspricht (4+1)*(2+1)*(1+1)*(1+1)*(1+1)*(1+1)*(1+1)*(1+1) Teilervarianten.
Zusammengefaßt: 5 * 3 * 2^6 = 960 Teilervarianten

DAMIT ist die Lösung per Brute Force echt einfach:
Resultat: höchster getesteter Folgenwert: 76576500 (12376 tes Glied); maximal soweit gefunden: 576 Teiler

13 Erste 10 Ziffern der Summe der folgenden Zahlen

Aufgabe im Euler-Projekt
Siehe bigints.txt

Hmmm....: vorn oder hinten? Wir werden probieren...

OK: Ein bißchen Zeichenketten-Arithmetik in Eigenregie oder mit Hilfe von vorhandenen Bibliotheken...
Für PHP haben wir da was: BCMath und GMP. Ersteres scheint besser zu passen...

Resultat: 5537376230390876637302048746832985971773659831892672

Da der Aufgabensteller sich aber nicht eindeutig ausgedrückt hat, was er denn nun genau haben will, bleibt uns nichts als die Versuch-und-Irrtum-Methode...
Aha, es waren die höchstwertigen: 5537376230

14 Längste Folge

Aufgabe im Euler-Projekt
...für die Bildungsvorschrift: n[next] = ((n & 1) ? n*3+1 : n/2)
und eine Startzahl unter 1 Millionen

Letztlich ist es doch nur ein linearer Test.. Vielleicht ein bißchen quadratisch angehaucht. -> Erstmal Brute Force...

Maximalwert: 837799 -> 525; Primzahlzerlegung: 653 * 1283

15 Menge der möglichen graphische Routen

Aufgabe im Euler-Projekt
Und zwar immer von einer Ecke monoton in Richtung der anderen Ecke...

Das ganze für ein 20*20-Feld...

Ist wieder ein Kombinatorik-Problem:
Damit ergeben sich z.B.:
(n+1 + n + n-1 + ... + 1) + (n + n-1 + ... + 1) + (n-1 + ... + 1) + ... + 1
für die letzten drei Spalten, solange der Rest oben bleibt.
Mit jeder Spalte kommt eine Dimension an Summanden hinzu, während gleichzeitig der Maximalwert um eins fällt.

Das Denken muß mal wieder ein bißchen verbogen werden, alldieweil das auf eine Standard-Aufgabe der Kombinatorik paßt.

Klick: Eine Art Pascalsches Dreieck (na ja, eher ein ganz anderes Zahlendreieck)...
Mit nicht mehr als 400 Elementen...

In der folgenden Tabelle lasse ich feststellen, wieviele Positioniermöglichkeiten es gibt, wenn das Kästchenfeld die Ausdehnung von ganz links oben in der Tabelle bis zu dem betrachteten Tabellenelement hat.
Die Tabelle wird von oben nach unten linear durchaddiert.

111111111111111111111
123456789101112131415161718192021
13610152128364555667891105120136153171190210231
1410203556841201652202863644555606808169691140133015401771
15153570126210330495715100113651820238030603876484559857315885510626
16215612625246279212872002300343686188856811628155042034926334336494250453130
1728842104629241716300350058008123761856427132387605426474613100947134596177100230230
18361203307921716343264351144019448318245038877520116280170544245157346104480700657800888030
1945165495128730036435128702431043758755821259702034903197704903147354711081575156227522200753108105
1105522071520025005114402431048620923781679602939304974208171901307504204297531245504686825690690010015005
1116628610013003800819448437589237818475635271664664611440661961256326876053117358436285131231102003001030045015
112783641365436812376318247558216796035271670543213520782496144445740077261601303789521474180345972905462730084672315
11391455182061881856450388125970293930646646135207827041565200300965770017383860304217555189593586493225141120525225792840
11410556023808568271327752020349049742011440662496144520030010400600200583003744216067863915119759850206253075347373600573166440
115120680306011628387601162803197708171901961256445740096577002005830040116600775587601454226752651825254714356008188092001391975640
11613681638761550454264170544490314130750432687607726160173838603744216077558760155117520300540195565722720103715832018559675203247943160
11715396948452034974613245157735471204297553117351303789530421755678639151454226753005401956010803901166803110220396143040599289507307872110
11817111405985263341009473461041081575312455084362852147418051895935119759850265182525565722720116680311023336062204537567650859749660015905368710
11919013307315336491345964807001562275468682513123110345972908649322520625307547143560010371583202203961430453756765090751353001767263190033578000610
1202101540885542504177100657800222007569069002003001054627300141120525347373600818809200185596752040599289508597496600176726319003534526380068923264410
121231177110626531302302308880303108105100150053004501584672315225792840573166440139197564032479431607307872110159053687103357800061068923264410137846528820

Da die Sache symmetrisch ist, hätte ich mir auch die Hälfte davon ersparen können.
Aber was soll's...

16 Summe der Ziffern von 2 ^ 1000

Aufgabe im Euler-Projekt
Wieder eine triviale Aufgabe (wobei: Wir KÖNNTEN uns anstrengen und diese in nur knapp über 10 Iterationen berechnen, aber das wäre hier noch Overkill...)...

2 ^ 1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
Resultat: 1366

17 Schreibweise von englischen Zahlwörtern

Aufgabe im Euler-Projekt
Hmmmm... Das hat ja nun mal gar nichts mit Mathematik zu tun, oder?

Buchstabenmenge(1...1000) = 21124


von: (1...9999) bis: (1...9999) anzeigen:

18 Maximale Summe auf einem von vielen Pfaden

Aufgabe im Euler-Projekt
Und zwar in folgendem Zahlendreieck... (Ich stelle das Zahlendreieck mal als linksbündig dar...)

75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 00 70 98 73 93 38 53 60 04 23

Wir dürfen uns im Zahlendreieck entweder direkt nach unten oder schräg nach rechts unten bewegen.
Da die Aufgabe eh nochmal in größer kommt, mache ich erstmal Brute Force...

Ergebnis: 1074

19 Menge der Sonntage am Monatsanfang zwischen 1.1.1901 und 31.12.2000

Aufgabe im Euler-Projekt
Einfach zusammenzählen... (soviele sind's ja nicht)

Ergebnis: 171

20 Summe der Ziffern in Fakultät(100)

Aufgabe im Euler-Projekt
Sollte trivial sein...

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Ergebnis: 648

21 Summe aller 'befreundeten Zahlen' unter 10000

Aufgabe im Euler-Projekt
Junge, Junge, die können aber auch abstrakte Spielchen machen!
Bei Aufgabe 12 hatten wir was Verwandtes. Aber da gings nicht darum, die Teiler direkt alle zu ermitteln. Das müssen wir jetzt wohl machen...

Ich gehe erst alle Zahlen durch, um die Teilersumme zu ermitteln. Dann nochmal, um auf die befreundeten Zahlen zu testen...

befreundet: 220, 284 befreundet: 1184, 1210 befreundet: 2620, 2924 befreundet: 5020, 5564 befreundet: 6232, 6368 Ergebnis: 31626

22 Wortspielereien

Aufgabe im Euler-Projekt
Die Summe der Bewertungen von Zeichenketten aus names.txt.

Die Bewertung einer Zeichenkette ist gleich dem Produkt aus der Summe der Buchstabenwerte und der 1-basierten Position der Zeichenkette nach alphabetischer Sortierung. Die Bewertung eines Buchstaben ist gleich der 1-basierten Position desselben im englischen Alphabet.

OK, mal wieder eine Fleißarbeit zum Entspannen...

Ergebnis: 871198282

23 Sieb mit überfüllten Zahlen

Aufgabe im Euler-Projekt
Keine Ahnung, wie Mathematiker dazu sagen. Ist mal wieder hochgradig vom praktischen Leben abgehoben...

Wir benötigen zuerst alle "überfüllten Zahlen", um dann auf Basis von denen alle Zweierkombinationen von denen durchzugehen und im vorgegebenen Bereich von 1...28123 alles zu streichen, was sich mit solchen Kombinationen darstellen läßt.

Läuft momentan auf reine Fleißarbeit hinaus...
Besser wäre eine Aufgabe, die eine Art von praktischem Nutzeffekt solcher Sachen zeigen könnte.

Der schon recht betagte Rechner knabbert daran in PHP schon über eine Minute...
Es wird Zeit, daß ich auf C++ umsteige...

Ergebnis: 4179871

24 1 Millionste der sortierten Permutationen der 10 Dezimalziffern

Aufgabe im Euler-Projekt
Weil die Aufgabe so schön symmetrisch ist, wird sie trivial:
Es handelt sich um eine Art Pseudo-Division, wobei die verfügbaren Stellenwertigkeiten den Fakultäten der (Null-basierten) Stellenposition entsprechen.

Soll schöngeistig erklärt heißen: Solange z.B. eine Ziffer ganz vorn steht, veranstalten die 9 anderen Ziffern auf den hinteren Stellen 9! Permutationen. Wenn unsere gesuchte Position (1 Mill) INNERHALB dieser 9! liegt, bleibt vorn die "0" stehen. Sonst blättern wir für diese erste Stelle soviele Ziffern hoch, wie die 9! in unsere Position reinpassen.
Anschließend verteilen wir die übrig gebliebenen 9 Ziffern auf die übriggebliebene Differenz zwischen unserer Position und den nach dem Umblättern der höchsten Stelle übriggebliebenen Permutations-Varianten.

Wir müssen in unserem Progrämmchen noch aufpassen, weil wieder mal 1-basiertes gegen 0-basiertes Zählen auszutauschen ist...

Ergebnis: 2783915460

25 Erster Fibonacci-Term mit 1000 Ziffern

Aufgabe im Euler-Projekt
Weil die betreffende Reihe exponentiell wächst (mit etwas weniger als Basis 2), kommen wir nach schätzungsweise 5000 Iterationen am Ziel an.
-> Brute Force alias wieder reine Fleißarbeit...

Ergebnis: 4782

26 Dezimalbruch mit langem Zyklus

Aufgabe im Euler-Projekt
Hmmmm, da muß ich erstmal nach Bruchrechnungs-Arithmetk gucken...
OK, bcmath funktioniert...

An Bruchstellen sollten 11 genügen, um einen Zyklus erkennen zu können, oder?
Weil: Ein Zyklus kann doch nur 10 Stellen lang sein, oder?
Nein: http://de.wikipedia.org/wiki/Dezimalsystem#Periode
Tja: Schon lange her, die Schul-Mathematik...

Erst nochmal ein bißchen Analyse: Wenn ich das richtig verstanden habe, werden die Primzahlen, die dicht unter dem vorgegebenen Grenzwert liegen, die längsten Perioden erzeugen. Und zwar wird diejenige davon die längste Periode haben, die am spätesten in einer Zahl 10^n-1 als Faktor auftaucht. Und jenes soll wohl spätestens bei einem n von maximal eins weniger als dem Primzahlwert auftreten.
Die Menge der Periodenstellen, die wir zu betrachten hätten, sollte also nicht größer als der Wert des Nenners sein. Oder besser: Statt die Brüche zu bestimmen, könenn wir ja auch den Nenner primzerlegen und für die Primzahlen den Wert n bestimmen, für den 10^n-1 durch die Primzahl teilbar wird. DAS allerdings ist in PHP wieder einfacher, indem wir einfach den Bruch ausrechnen...

Ich betrachte einfach alle Primzahlen bis 1000... (und davon nur die ersten paar...)
OK, also: Nachvollziehbar ist, daß die maximal langen Perioden genau um eine Stelle kürzer sind als der Wert der verursachenden Primzahl. Und daß die Primzahl 983 wohl diejenige mit der längsten Periode sein dürfte.

997 -> 168 : 0.0010030090270812437311935807422266800401203610832497492477432296890672016048144433299899699097291875626880641925777331995987963891675025075225677031093279839518555667001003009027081243731193580742226680040120361083249749247743229689067201604814443329989969909729187562688064192577733199598796389167502507522567703109327983951855566700100300902708124373119358074222668004012036108324974924774322968906720160481444332998996990972918756268806419257773319959879638916750250752256770310932798395185556670010030090270812437311935807422266800401203610832497492477432296890672016048144433299899699097291875626880641925777331995987963891675025075225677031093279839518555667001003009027081243731193580742226680040120361083249749247743229689067201604814443329989969909729187562688064192577733199598796389167502507522567703109327983951855566700100300902708124373119358074222668004012036108324974924774322968906720160481444332998996990972918756268806419257773319959879638916750250752256770310932798395185556670010030 991 -> 497 : 0.0010090817356205852674066599394550958627648839556004036326942482341069626639757820383451059535822401614530776992936427850655903128153380423814328960645812310797174571140262361251261352169525731584258324924318869828456104944500504540867810292633703329969727547931382441977800201816347124117053481331987891019172552976791120080726538849646821392532795156407669021190716448032290615539858728557013118062563067608476286579212916246215943491422805247225025227043390514631685166498486377396569122098890010090817356205852674066599394550958627648839556004036326942482341069626639757820383451059535822401614530776992936427850655903128153380423814328960645812310797174571140262361251261352169525731584258324924318869828456104944500504540867810292633703329969727547931382441977800201816347124117053481331987891019172552976791120080726538849646821392532795156407669021190716448032290615539858728557013118062563067608476286579212916246215943491422805247225025227043390514631685166498486377396569122098890010090817356 983 -> 984 : 0.0010172939979654120040691759918616480162767039674465920651068158697863682604272634791454730417090539165818921668362156663275686673448626653102746693794506612410986775178026449643947100712105798575788402848423194303153611393692777212614445574771108850457782299084435401831129196337741607324516785350966429298067141403865717192268565615462868769074262461851475076297049847405900305188199389623601220752797558494404883011190233977619532044760935910478128179043743641912512716174974567650050864699898270600203458799593082400813835198372329603255340793489318413021363173957273652085452695829094608341810783316378433367243133265513733468972533062054933875890132248219735503560528992878942014242115971515768056968463886063072227873855544252288911495422177009155645981688708036622583926754832146490335707019328585961342828077314343845371312309257375381485249237029501525940996948118006103763987792472024415055951169888097660223804679552390640895218718209562563580874872838250254323499491353001017293997965412004 977 -> 978 : 0.0010235414534288638689866939611054247697031729785056294779938587512794268167860798362333674513817809621289662231320368474923234390992835209825997952917093142272262026612077789150460593654042988741044012282497441146366427840327533265097236438075742067553735926305015353121801432958034800409416581371545547594677584442169907881269191402251791197543500511770726714431934493346980552712384851586489252814738996929375639713408393039918116683725690890481064483111566018423746161719549641760491299897645854657113613101330603889457523029682702149437052200614124872057318321392016376663254861821903787103377686796315250767656090071647901740020470829068577277379733879222108495394063459570112589559877175025588536335721596724667349027635619242579324462640736949846468781985670419651995905834186284544524053224155578300921187308085977482088024564994882292732855680655066530194472876151484135107471852610030706243602865916069600818833162743091095189355168884339815762538382804503582395087001023541453428863868986693 971 -> 972 : 0.0010298661174047373841400617919670442842430484037075180226570545829042224510813594232749742533470648815653964984552008238928939237899073120494335736354273944387229660144181256436663233779608650875386199794026776519052523171987641606591143151390319258496395468589083419155509783728115345005149330587023686920700308959835221421215242018537590113285272914521112255406797116374871266735324407826982492276004119464469618949536560247167868177136972193614830072090628218331616889804325437693099897013388259526261585993820803295571575695159629248197734294541709577754891864057672502574665293511843460350154479917610710607621009268795056642636457260556127703398558187435633367662203913491246138002059732234809474768280123583934088568486096807415036045314109165808444902162718846549948506694129763130792996910401647785787847579814624098867147270854788877445932028836251287332646755921730175077239958805355303810504634397528321318228630278063851699279093717816683831101956745623069001029866117404737384140061791967 967 -> 324 : 0.0010341261633919338159255429162357807652533609100310237849017580144777662874870734229576008273009307135470527404343329886246122026887280248190279214064115822130299896587383660806618407445708376421923474663908996897621509824198552223371251292657704239917269906928645294725956566701137538779731127197518097207859358841778697001034126163391933815925542916235780765253360910031023784901758014477766287487073422957600827300930713547052740434332988624612202688728024819027921406411582213029989658738366080661840744570837642192347466390899689762150982419855222337125129265770423991726990692864529472595656670113753877973112719751809720785935884177869700103412616339193381592554291623578076525336091003102378490175801447776628748707342295760082730093071354705274043433298862461220268872802481902792140641158221302998965873836608066184074457083764219234746639089968976215098241985522233712512926577042399172699069286452947259565667011375387797311271975180972078593588417786970010341261633919338159255429162357807 953 -> 954 : 0.0010493179433368310598111227701993704092339979013641133263378803777544596012591815320041972717733473242392444910807974816369359916054564533053515215110178384050367261280167890870933892969569779643231899265477439664218258132214060860440713536201469045120671563483735571878279118572927597061909758656873032528856243441762854144805876180482686253934942287513116474291710388247639034627492130115424973767051416579223504721930745015739769150052465897166841552990556138509968520461699895068205666316894018887722980062959076600209863588667366211962224554039874081846799580272822665267576075550891920251836306400839454354669464847848898216159496327387198321091290661070304302203567681007345225603357817418677859391395592864637985309548793284365162644281217208814270724029380902413431269674711437565582371458551941238195173137460650577124868835257082896117523609653725078698845750262329485834207764952780692549842602308499475341028331584470094438614900314795383001049317943336831059811122770199370409233997901364 947 -> 475 : 0.0010559662090813093980992608236536430834213305174234424498416050686378035902851108764519535374868004223864836325237592397043294614572333685322069693769799366420274551214361140443505807814149947201689545934530095036958817317845828933474128827877507919746568109820485744456177402323125659978880675818373812038014783526927138331573389651531151003167898627243928194297782470960929250263991552270327349524815205913410770855332629355860612460401267159450897571277719112988384371700105596620908130939809926082365364308342133051742344244984160506863780359028511087645195353748680042238648363252375923970432946145723336853220696937697993664202745512143611404435058078141499472016895459345300950369588173178458289334741288278775079197465681098204857444561774023231256599788806758183738120380147835269271383315733896515311510031678986272439281942977824709609292502639915522703273495248152059134107708553326293558606124604012671594508975712777191129883843717001055966209081309398099260823653643083421330517423442449 941 -> 942 : 0.0010626992561105207226354941551540913921360255047821466524973432518597236981934112646121147715196599362380446333687566418703506907545164718384697130712008501594048884165781083953241232731137088204038257173219978746014877789585547290116896918172157279489904357066950053134962805526036131774707757704569606801275239107332624867162592986184909670563230605738575982996811902231668437832093517534537725823591923485653560042507970244420828905419766206163655685441020191285866099893730074388947927736450584484590860786397449521785334750265674814027630180658873538788522848034006376195536663124335812964930924548352816153028692879914984059511158342189160467587672688629117959617428267800212539851222104144527098831030818278427205100956429330499468650371944739638682252922422954303931987247608926673751328374070138150903294367693942614240170031880977683315621679064824654622741764080765143464399574920297555791710945802337938363443145589798087141339001062699256110520722635494155154091392136025504782146652497343 937 -> 938 : 0.0010672358591248665955176093916755602988260405549626467449306296691568836712913553895410885805763073639274279615795090715048025613660618996798292422625400213447171824973319103521878335112059765208110992529348986125933831376734258271077908217716115261472785485592315901814300960512273212379935965848452508004268943436499466382070437566702241195304162219850586979722518676627534685165421558164354322305229455709711846318036286019210245464247598719316969050160085378868729989327641408751334044823906083244397011739594450373532550693703308431163287086446104589114194236926360725720384204909284951974386339381003201707577374599786552828175026680896478121664887940234791889007470651013874066168623265741728922091782283884738527214514407684098185699039487726787620064034151547491995731056563500533617929562433297758804695837780149413020277481323372465314834578441835645677694770544290288153681963713980789754535752401280683030949839914621131270010672358591248665955176093916755602988260405549626467449306296691

Ergebnis: 983

27 Ausdruck zum Erzeugen von Primzahlketten

Aufgabe im Euler-Projekt
P[i] = x^2 + a*x + b |a| < 1000 |b| < 1000
Wir haben NICHT den Auftrag, bei 2 startende Primzahlen zu finden.
Und sie sollen auch nicht zwingend aufeinanderfolgen. Das "Aufeinanderfolgen" bezieht sich nur auf den Index "x", nicht auf die resultierenden Werte.
Ach ja: Und die müssen nicht zwingend steigen.

Für x == 0 muß die erste Primzahl entstehen, also muß b schon mal zu den Primzahlen gehören. Wir suchen also die Primzahlen kleiner 1000...
Anschließend muß (1+a) dazu addiert eine Folgeprimzahl für positives a und eine Vorgängerprimzahl für negatives a ergeben. Wir sollten also die Primzahlen bis etwas weiter vorbereiten, damit wir anschließend noch die Nachfolger untersuchen können... Wieviele davon wir brauchen, können wir auch im Laufe des Experiments korrigieren lassen.
Wenn wir immer noch in der Primzahlfolge sind, suchen wir die höchste Zahl des Terms, die noch einen Primzahlnachfolger darstellt.

Weil wir nicht daran gebunden sind, daß die Primzahlen aufeinander folgen müssen, kann a alle möglichen Differenzen zu Nachbarprimzahlen annehmen. Nach unten hin ist es durchaus begrenzt: Immerhin muß die Folge in den Bereich bis vor den Nullpunkt der Primzahlfolge bei "2" passen. Nach oben ist es ziemlich offen. Die Zahlen reichen bis xmax*xmax + a*xmax + b. Dabei wird xmax allerdings wahrscheinlich recht begrenzt bleiben (aus der Aufgabenstellung schlußfolgert eine Begrenzung xmax < 80).

Grenzwert für |a| und |b|: 999
bimax: 168 -> bmax: 1009
Ergebnis: a = -61, b = 971, Reihenlänge = 71

Reihe: 971 911 853 797 743 691 641 593 547 503 461 421 383 347 313 281 251 223 197 173 151 131 113 97 83 71 61 53 47 43 41 41 43 47 53 61 71 83 97 113 131 151 173 197 223 251 281 313 347 383 421 461 503 547 593 641 691 743 797 853 911 971 1033 1097 1163 1231 1301 1373 1447 1523 1601

Koeffizientenprodukt: -59231


Grenzwert für |a| und |b|: 9999
bimax: 1229 -> bmax: 10007
Ergebnis: a = -79, b = 1601, Reihenlänge = 80

Reihe: 1601 1523 1447 1373 1301 1231 1163 1097 1033 971 911 853 797 743 691 641 593 547 503 461 421 383 347 313 281 251 223 197 173 151 131 113 97 83 71 61 53 47 43 41 41 43 47 53 61 71 83 97 113 131 151 173 197 223 251 281 313 347 383 421 461 503 547 593 641 691 743 797 853 911 971 1033 1097 1163 1231 1301 1373 1447 1523 1601

Koeffizientenprodukt: -126479


Fazit: Wie wir schön aus dem Charakter der Reihen entnehmen können, sind sie praktisch wertlos, alldieweil die Zahlen nichts mit Folgen innerhalb von Primzahlen, sondern nur was mit Punkten auf einer quadratischen Kurve, die zufälligerweise prim sind, zu tun haben.

28 Summe der Diagonalen in einem speziellen magischen Quadrat

Aufgabe im Euler-Projekt
Für die Werte in diesem magischen Quadrat gilt eine Bildungsvorschrift, die keine Variabilität läßt. Da es ausgehend vom Mittelpunkt gebildet wird, gelten für alle Folgen auf vom Mittelpunkt ausgehenden Linien feste Bildungsvorschriften.

Nach rechts oben: x = (2*i+1)^2 Nach links oben: x = (2*i+1)^2 - 2*i Nach links unten: x = (2*i+1)^2 - 4*i Nach rechts unten: x = (2*i+1)^2 - 6*i

Die Summenbildung über die ganz analytische Summenbestimmung (Summe von Quadraten) erspare ich mir jetzt...
Summe der Diagonalen: 669171001

29 unterschiedliche Potenzen

Aufgabe im Euler-Projekt
99 Basen und 99 Exponenten ergeben erstmal 99*99 = 9801 Zahlen.

Deren Brute-Force-Berechnung und anschließender Vergleich wären schon mal trivial. Erfordern allerdings sowas wie Rechnen mit großen Zahlen und dauern entsprechend eventuell im Sekundenbereich.

Es geht aber viel kürzer (vom Rechenaufwand her): Die 99 Basen haben ihre Primzahlzerlegungen, deren Exponenten bei Potenzen der Basen halt nur vervielfacht werden. Von den resultierenden Potenzen können nur die gleich sein, die eine gleiche relative Primzahlzerlegung (Faktoren und deren Verhältnisse untereinander) haben. Ich nenne das mal "Fußabdruck" der Primzahlzerlegung.
Und von denen fallen dann genau die heraus, deren Exponenten-Vielfache schon durch kleinere Exponenten-Vielfache erzeugt werden.
LETZTERES ist mir momentan noch zu abstrakt. Das lasse ich mir mal anzeigen...

mit Überschneidungen: 4 = 2^2; factor-footprint: 2
mit Überschneidungen: 8 = 2^3; factor-footprint: 2
mit Überschneidungen: 9 = 3^2; factor-footprint: 3
mit Überschneidungen: 16 = 2^4; factor-footprint: 2
mit Überschneidungen: 25 = 5^2; factor-footprint: 5
mit Überschneidungen: 27 = 3^3; factor-footprint: 3
mit Überschneidungen: 32 = 2^5; factor-footprint: 2
mit Überschneidungen: 36 = 2^2 * 3^2; factor-footprint: 2 * 3
mit Überschneidungen: 49 = 7^2; factor-footprint: 7
mit Überschneidungen: 64 = 2^6; factor-footprint: 2
mit Überschneidungen: 81 = 3^4; factor-footprint: 3
mit Überschneidungen: 100 = 2^2 * 5^2; factor-footprint: 2 * 5

So, von DIESEN Fällen ist zu bestimmen, was alles rausfällt.
Es ist eine Art Anti-Primzahl-Sieb. Daraus schlußfolgere ich mal, daß ich es eh nicht systematisch in eine analytische Formel gepreßt kriege. Ich muß es also stur mit Durchprobieren der Varianten abhandeln.
Ich könnte wie beim Primzahlsieb einen Besetzungsvektor für den jeweiligen Fußabdruck mitführen. Aber da ich ja nicht die übrigbleibenden Elemente haben will, sondern die besetzten, und diese außerdem nach oben hin rasch dünner werden, bietet PHP mit seinen arrays eine bessere Ausdrucksweise...


Schließlich erhalten wir folgende Elementereduzierungen:
Primfaktor-Fußabdruck 2: tatsächlich besetzte Vielfache: 328 gegenüber unselektiert 594
Primfaktor-Fußabdruck 3: tatsächlich besetzte Vielfache: 240 gegenüber unselektiert 396
Primfaktor-Fußabdruck 5: tatsächlich besetzte Vielfache: 149 gegenüber unselektiert 198
Primfaktor-Fußabdruck 2 * 3: tatsächlich besetzte Vielfache: 149 gegenüber unselektiert 198
Primfaktor-Fußabdruck 7: tatsächlich besetzte Vielfache: 149 gegenüber unselektiert 198
Primfaktor-Fußabdruck 2 * 5: tatsächlich besetzte Vielfache: 149 gegenüber unselektiert 198

Damit ergibt sich eine Gesamtmenge der Varianten von: 9183.
Brute Force ergibt 9183

...Wenn wir uns die Reduktionen mal angucken, fällt auf, daß wir die erstens mal nicht extra für alle Fußabdrücke bestimmen müssen und zweitens das Zeug sicherlich auch irgendwie vereinfacht ermitteln können.
Aber für den Moment solls das erstmal gewesen sein...

Der ganz rohe Brute-Force-Aufwand steigt übrigens offenbar mit vierter Potenz. Die 100 scheint da tatsächlich eine obere Grenze darzustellen.

Basen von: (2...10000) bis: (2...10000) Exponenten von: (2...10000) bis: (2...10000)

30 Summe der Zahlen, die gleich der Summe ihrer (Ziffern hoch 5) sind

Aufgabe im Euler-Projekt
Betrachtete Potenz: 5
Abschätzung des Wertebereichs:
Maximaler Wert einer Ziffernpotenz = 9 ^ 5 = 59049
Anzahl der Ziffern, ab der die Zahl nicht mehr als Summe ihrer Ziffern darstellbar ist: 6
4150 4151 54748 92727 93084 194979
Ergebnis: 443839

31 Summenzerlegung

Aufgabe im Euler-Projekt
Für diese spezielle Aufgabe machen wir es speziell mit Brute Force...
Da die Reihenfolge der zerlegten Summanden nicht interessiert, organisieren wir, daß keine Vertauschung entsteht: Die Zerlegung wird immer mit den größten probierten Teilen begonnen (von 0 bis max) und rekursiv aufgefüllt in derselben Weise mit kleineren Teilen...

Ergebnis: 73682

32 Pandigitale Produkte

Aufgabe im Euler-Projekt
Das Problem scheint auf einen relativ geringen Zahlenbereich beschränkt zu sein.
Die Aufgabenstellung ist allerdings nicht eindeutig.
Da ich mit "pandigital" erstmal nichts anfangen kann, schlage ich bei http://en.wikipedia.org/wiki/Pandigital_number und http://mathworld.wolfram.com/Pandigital.html nach und entdecke, daß damit unendlich viele Freiheitsgrade gemeint sein können: Jede Ziffer kann danach durchaus beliebig oft vorkommen. Es muß lediglich gewährleistet sein, daß alle Ziffern der Basis vorkommen. Zusätzlich gibt es einen Freiheitsgrad bezüglich des Vorkommens der Null.
Die Aufgabenstellung sagt nichts diesbezüglich aus, was ich als nicht mathematische ausgebildeter Mensch schlußfolgern kann.

Der Begriff "Identität" ist für mich komplett schleierhaft.

Erahnen tue ich, daß gemeint ist, daß jede Dezimalziffer außer der Null genau einmal in allen an der Produktdarstellung beteiligten Zahlen vorkommen soll. Das resultiert schon daraus, daß ansonsten keinerlei Begrenzung angegeben ist.

Das Produkt kann nicht größer sein als 9876. Wenn es 5 Ziffern haben sollte, müßten in den Zahlen vorn auch mindestens 5 Ziffern vorkommen, was nach der vermuteten Voraussetzung nicht möglich ist.
Das Produkt kann nicht kleiner sein als 245*13=3185, weil in den Faktoren mindestens 5 Ziffern stehen müssen.

Damit können wir alle Zahlen in diesem Bereich blind durchtesten: 4396 = 28 * 157
5346 = 27 * 198
5796 = 42 * 138
6952 = 4 * 1738
7254 = 39 * 186
7632 = 48 * 159
7852 = 4 * 1963
Ergebnis: 45228

33 Teilerspielereien

Aufgabe im Euler-Projekt
Die Aufgabenstellung ist mal wieder uneindeutig. Aber wir sollten das korrekte im Laufe des Experiments erraten können: Immerhin soll es genau 4 Fälle geben...
Zuerst mal zu den vier Fällen:

16/64 = 1/4
19/95 = 1/5
26/65 = 2/5
49/98 = 4/8
Produkt: 387296/38729600 = 1/100

34 Summe der Zahlen, die gleich der Summe der Fakultäten ihrer Ziffern sind

Aufgabe im Euler-Projekt
Eine Zahl soll gleich der Summe der Fakultäten ihrer Ziffern sein...

Abschätzung des Wertebereichs:
Fakultät(9) = 362880
362880 * 7 = 2540160 < 9999999

Brute Force müßte immer noch gehen, auch wenn wir hier sicherlich einiges an Tests einsparen könnten...

145 40585
Ergebnis: 40730

35 Zirkulare Primzahlen unter 1 Million

Aufgabe im Euler-Projekt
Ergebnis: 55

36 Summe der Palindrome in Basis 10 und 2 unter 1 Million

Aufgabe im Euler-Projekt
33 = 100001
99 = 1100011
7447 = 1110100010111
9009 = 10001100110001
585585 = 10001110111101110001
313 = 100111001
717 = 1011001101
1 = 1
32223 = 111110111011111
53235 = 1100111111110011
15351 = 11101111110111
3 = 11
5 = 101
73737 = 10010000000001001
7 = 111
585 = 1001001001
53835 = 1101001001001011
39993 = 1001110000111001
9 = 1001

Ergebnis: 872187

37 Summe der links- und rechts-verkürzbaren Primzahlen

Aufgabe im Euler-Projekt
Zur Abschätzung des Wertebereichs:
Ich schaue also einfach mal, wie weit sich aus vorhandenen einstelligen Primzahlen zweistellige ergeben.
Wenn ich mehr als 11 Kandidaten (einschließlich aller, die sich nicht mehr verlängern lassen) übrig behalte, versuche ich gleiches mit dem Übergang auf dreistellige.
usw. usf.

23
37
53
73
313
317
373
797
3137
3797
739397

Ergebnis: 748317

38 Größte "Pandigitale 1-9" als Vielfachenfolge

Aufgabe im Euler-Projekt
Wertebereichsabschätzung:
918273645
192384576
219438657
273546819
327654981
672913458
679213584
692713854
726914538
729314586
732914658
769215384
792315846
793215864
926718534
927318546
932718654

Ergebnis: 932718654

39 Dreiecksumfang für ganzzahlige Seitenlängen bei maximale Variantenmenge

Aufgabe im Euler-Projekt
Wir haben ja nicht wirklich viele Variablen:
c^2 = a^2 + b^2 a+b+c = u führt zu bc = (u-a) c = (a^2/bc + bc) / 2

Ergebnis: Umfang: 840 -> 16 Lösungen

40 Ziffernspielerei

Aufgabe im Euler-Projekt
Das ist wohl weniger eine Aufgabe für den Computer...
Lösung: 1 * 1 * 5 * 3 * 7 * 2 * 1 = 210

41 Größte Primzahl, die außerdem pandigital ist

Aufgabe im Euler-Projekt
Hmmm... es dürfte doch kaum um was anderes gehen können als die 9-stelligen Primzahlen, oder? Alle anderen sind doch viel kleiner!
Das bedeutet, Primzahlen bis unter 1 Milliarde ermitteln und von oben ausgehend die erste ermitteln, die pandigital ist.
(Das dürfte aber in PHP recht lange dauern...)
Oder alternativ: Pandigitale basteln und gucken, welche sich davon nicht zerlegen läßt.
Letzteres bedeutet, Permutationen von "987654321" aus bilden, so daß deren Zahlenwert monoton fällt. Das bedeutet: Die letzten Stellen zuerst tauschen.

Ähmmmm: Die Quersumme der Ziffern bei Pandigitalität ist doch immer durch 3 teilbar! Damit kann die Annahme wohl kaum hinkommen...
Wenn ich die 9 wegnehme, bleibt die Quersumme immer noch durch 3 teilbar. Erst bei Verzicht auf die 8 ändert sich das.
Damit haben wir nur noch bis 10 Millionen zu testen. Das geht mit Brute Force...

Ergebnis: 7652413

42 Spielerei mit Zahlenreihen

Aufgabe im Euler-Projekt
Das ist wieder reine Fleißarbeit...
Die Zeichenketten aus words.txt, deren "Bewertung" einem Element einer quadratischen Zahlenreihe entspricht, sollen gezählt werden.
Wir hatten das schon mal ähnlich in Aufgabe 22...

Ergebnis: 162

43 Pandigitalen-Spielerei

Aufgabe im Euler-Projekt
Wir sollen lange Zahlen aus kurzen Stückchen zusammensetzen, die gewisse Anforderungen erfüllen. Na gut...
Ich probiere mal, den Term zeichenweise auszudehnen...

1406357289
1430952867
1460357289
4106357289
4130952867
4160357289

Ergebnis: 16695334890

44 Spielerei mit Zahlenreihen

Aufgabe im Euler-Projekt
Die Zahlenreihe, um die es geht, ist n(3n-1)/2. (Das "pentagonal" ist wohl mehr als akademische Wortspielerei von Mathematikern gemeint.)

Wir haben keine Wertebereichs-Begrenzung angegeben. Also muß es eine Begrenzung aus der Logik der Umstände geben.
Die Formulierung der Differenz und der Summe der gesuchten Zahlenreihenglieder führt auf
3(i^2 - j^2 - k^2) = (i - j - k) für minimales k und
3(i^2 + j^2 - l^2) = (i + j - l)

Wir brauchen erstmal ein k, für das es ein passendes ganzzahliges i und j gibt, und dann ein dazu passendes l...
Allerdings führt dies nicht wirklich zu einer Eingrenzung der Variabilität oder einer Vereinfachung von Gleichungen.

Brute Force liefert zunächst mal:
a: (2167,7042750), b: (1020,1560090), d: (1912,5482660), s: (2395,8602840)

Etwas intensiveres Nachdenken liefert die zweckmäßigere Vorgehensweise:
  1. Aufstellen der Tripel "a + b = c" mit "a < b < c", die alle Elemente der Reihe sind
  2. Heraussuchen zweier Tripel, bei denen "c1 == a2" oder "c1 == b2" ist
Aber wir haben ja schon die Lösung...

45 Spielerei mit Zahlenreihen

Aufgabe im Euler-Projekt
Der Wertebereich beginnt bei der vorgegebenen Zahl 40755, die dem Index 143 der "Hexagonal"-Reihe zugeordnet ist. Wenn wir die nächste gültige Zahl suchen, sollten wir die Reihe mit den größten Schritten zwischen ihren Elementen zur Grundlage nehmen... (...oder das Zeug analytisch angehen...)

Die "Hexagonal"-Reihe ist in der "Triangle"-Reihe enthalten (it = 2*ih-1). Die brauchen wir also nicht prüfen.
Der "Pentagonal"-Index, der sich aus dem getesteten Wert ergibt, muß ganzzahlig sein...

1 = T(1) = P(1) = H(1)
40755 = T(285) = P(165) = H(143)
1533776805 = T(55385) = P(31977) = H(27693)

46 Zahlenspielerei

Aufgabe im Euler-Projekt
Hmmmm...: Was ist eine "composite number"?

5777 ist innerhalb 10000 nicht wie gefordert darstellbar.
5993 ist innerhalb 10000 nicht wie gefordert darstellbar.

47 Die ersten 4 aufeinanderfolgenden Zahlen mit je 4 verschiedenen Primfaktoren

Aufgabe im Euler-Projekt

gesuchte Zahl: 134043

48 einfache Multiplikation/Addition

Aufgabe im Euler-Projekt
Was soll daran schwierig sein?

Ergebnis: 9110846700

49 Primzahlenspielerei

Aufgabe im Euler-Projekt

gefunden: 1487, 4817, 8147
gefunden: 2969, 6299, 9629

50 Primzahlenspielerei

Aufgabe im Euler-Projekt
Wir haben eine signifikante Wertebereichseinschränkung: Es werden nur unmittelbar aufeinanderfolgende Summanden gesucht. Die Gruppe der gesuchten Summanden muß außerdem möglichst weit unten anfangen, da wir die längstmögliche Summe suchen. Allerdings kann die Zerlegung auf verschiedene Weise möglich sein, indem die Summandenauswahl nach oben verschoben wird. Wir können solcherart Suche aber abbrechen, wenn die soweit gefundene Maximalmenge an Summanden eh nicht mehr überboten werden kann.

7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+ 127+131+137+139+149+151+157+163+167+173+179+181+191+193+197+199+211+223+227+229+233+239+241+251+ 257+263+269+271+277+281+283+293+307+311+313+317+331+337+347+349+353+359+367+373+379+383+389+397+ 401+409+419+421+431+433+439+443+449+457+461+463+467+479+487+491+499+503+509+521+523+541+547+557+ 563+569+571+577+587+593+599+601+607+613+617+619+631+641+643+647+653+659+661+673+677+683+691+701+ 709+719+727+733+739+743+751+757+761+769+773+787+797+809+811+821+823+827+829+839+853+857+859+863+ 877+881+883+887+907+911+919+929+937+941+947+953+967+971+977+983+991+997+1009+1013+1019+1021+1031+ 1033+1039+1049+1051+1061+1063+1069+1087+1091+1093+1097+1103+1109+1117+1123+1129+1151+1153+1163+ 1171+1181+1187+1193+1201+1213+1217+1223+1229+1231+1237+1249+1259+1277+1279+1283+1289+1291+1297+ 1301+1303+1307+1319+1321+1327+1361+1367+1373+1381+1399+1409+1423+1427+1429+1433+1439+1447+1451+ 1453+1459+1471+1481+1483+1487+1489+1493+1499+1511+1523+1531+1543+1549+1553+1559+1567+1571+1579+ 1583+1597+1601+1607+1609+1613+1619+1621+1627+1637+1657+1663+1667+1669+1693+1697+1699+1709+1721+ 1723+1733+1741+1747+1753+1759+1777+1783+1787+1789+1801+1811+1823+1831+1847+1861+1867+1871+1873+ 1877+1879+1889+1901+1907+1913+1931+1933+1949+1951+1973+1979+1987+1993+1997+1999+2003+2011+2017+ 2027+2029+2039+2053+2063+2069+2081+2083+2087+2089+2099+2111+2113+2129+2131+2137+2141+2143+2153+ 2161+2179+2203+2207+2213+2221+2237+2239+2243+2251+2267+2269+2273+2281+2287+2293+2297+2309+2311+ 2333+2339+2341+2347+2351+2357+2371+2377+2381+2383+2389+2393+2399+2411+2417+2423+2437+2441+2447+ 2459+2467+2473+2477+2503+2521+2531+2539+2543+2549+2551+2557+2579+2591+2593+2609+2617+2621+2633+ 2647+2657+2659+2663+2671+2677+2683+2687+2689+2693+2699+2707+2711+2713+2719+2729+2731+2741+2749+ 2753+2767+2777+2789+2791+2797+2801+2803+2819+2833+2837+2843+2851+2857+2861+2879+2887+2897+2903+ 2909+2917+2927+2939+2953+2957+2963+2969+2971+2999+3001+3011+3019+3023+3037+3041+3049+3061+3067+ 3079+3083+3089+3109+3119+3121+3137+3163+3167+3169+3181+3187+3191+3203+3209+3217+3221+3229+3251+ 3253+3257+3259+3271+3299+3301+3307+3313+3319+3323+3329+3331+3343+3347+3359+3361+3371+3373+3389+ 3391+3407+3413+3433+3449+3457+3461+3463+3467+3469+3491+3499+3511+3517+3527+3529+3533+3539+3541+ 3547+3557+3559+3571+3581+3583+3593+3607+3613+3617+3623+3631+3637+3643+3659+3671+3673+3677+3691+ 3697+3701+3709+3719+3727+3733+3739+3761+3767+3769+3779+3793+3797+3803+3821+3823+3833+3847+3851+ 3853+3863+3877+3881+3889+3907+3911+3917+3919+3923+3929+3931 = 997651 (543)

51 Primzahlenspielerei

Aufgabe im Euler-Projekt
Wir suchen 8 Primzahlen, die alle Ziffern gleich haben bis auf ein paar, die innerhalb einer Zahl alle untereinander gleich sind.
Wir brauchen nicht unterhalb von 5-ziffrigen Zahlen beginnen.

Die Suchzeit wächst quadratisch (bezogen auf die Menge der zu untersuchenden Primzahlen und damit exponentiell zur Basis 100 bezogen auf die Stellenmenge) und beträgt bereits im 5-ziffrigen Bereich mehrere Minuten. Das sollte sich doch einschränken lassen, oder?
Ja, es funktioniert... Wir haben eine Rechenzeit proportional zur Menge der Primzahlen und der Menge von Maskenvarianten...

Ergebnis: 121313

52 Zahlenspielerei

Aufgabe im Euler-Projekt
Wertebereichseinschränkung: Ob allerdings diese Kriterien helfen?

Ergebnis: 142857 285714 428571 571428 714285 857142

53 Kombinatorik

Aufgabe im Euler-Projekt
Hmmm, wir sollen ermitteln, wieviele der etwa 100*100/2 gültigen Wertekombinationen von Grundmenge und Auswahlmenge eine Kombinationsvielfalt von größer als eine Millionen haben, ja?
Wir könnten uns ja anstrengen, falls größere Wertebereiche gefragt wären, um das ganze linear zu ermitteln, aber Brute Force reicht auch...

Ergebnis: 4075

54 Pokerregeln

Aufgabe im Euler-Projekt
Dieses Problem war schon wieder etwas anspruchsvoller. Nicht von der prinzipiellen Logik her, sondern vom Versuch her, diese halbwegs effizient zu formulieren...

Ergebnis: Gewinne-1: 376, Gewinne-2: 624

55 Lychrel-Zahlen unter 10'000

Aufgabe im Euler-Projekt
Mann oh Mann - Die Jungs haben ja Probleme!
Also: Der letzte Satz in der Erläuterung ist nur Nebensache. Wir suchen lediglich diese "Lychrel-Zahlen"...
Und wir MÜSSEN MINDESTENS EINE solche "reverse"-Addition durchführen...
Die Aufgabenstellung ist aber wieder mal nicht eindeutig:
DÜRFEN auch einstellige Zahlen als Ausgangsmaterial herhalten?

...Wir müssen mit großen Zahlen rechnen, weil wir größenordnungsmäig bei einigen zig Stellen landen können...

Ergebnis: 249

56 Maximale Quersumme in a^b mit a,b < 100

Aufgabe im Euler-Projekt
Ergebnis: 972

57 Zahlenreihen-Spielerei

Aufgabe im Euler-Projekt
OK, Der Zähler und der Nenner sind einfache Zahlenreihen...
Nenner: n[i] = 2*n[i-1]+n[i-2]; Nullpunkt-Startwerte (an Indizes -2,-1): 0,1
Zähler: Formel genauso; Nullpunkt-Startwerte: 1,1

Ach ja: Wir brauchen wieder große Zahlen...

Ergebnis: 153

58 Zahlenspielerei mit Primzahlen und einfachen quadratischen Folgen

Aufgabe im Euler-Projekt
Das hatten wir doch schon mal, oder? Ja: 28 Summe der Diagonalen in einem speziellen magischen Quadrat
Also: Zu erwartender Wertebereich ist? Hmmmm... Keine Ahnung. Am besten, ich probiere einfach mit schrittweiser Erhöhung...
Ähmmmm... Das Anlegen der Primzahlen ist nicht sinnvoll... Besser auf Teilbarkeit testen...

Seitenlängen-Grenzwert: 26241, Primzahlenanteil: 5248 / 52481

59 Textanalyse

Aufgabe im Euler-Projekt

Na ja... Das ist keine "moderne" Verschlüsselung...
Implementation of Chosen-Ciphertext Attacks against PGP and GnuPG
-> Da geht's explizit um das Übertragen von einfach verxorten Plaintext, welcher - Nachrichten-AUSTAUSCH vorausgesetzt - eine Verwundbarkeit bei DAU's unter Ausnutzung von social engineering hervorruft.

Man überträgt in einem "modernen" Verschlüsselungssystem einfach keinen verxorten Plaintext. Basta!

Der Vorteil, daß man nicht reversible Rausch-Generatoren modular zur Verschlüsselung einsetzen kann, wird durch den Nachteil erkauft, daß praktisch jeder Geheimdienst oder Schurke mit hinreichend krimineller Energie praktisch jede solche Verschlüsselungsstrecke knacken kann, weil es in der Realität nirgendwo keine Volldussel gibt...

Ansonsten haben wir hier einen Brute-Force-Angriff auszuführen, den wir durchaus schon eingangs etwas entschärfen können, weil das hier nun WIRKLICH Welten von "moderner Verschlüsselung" entfernt ist...

Wir müssen eh identifizieren, ob wir einen normalen englischen Text vor der Nase haben. Allerdings hätte ich dabei gern darauf verzichtet, die Besonderheiten der englischen Sprache kennen zu müssen.
DAZU hätte ich gern eine neutrale Statistik der Zeichenverteilung analysiert, die bei "richtiger" Verschlüsselung auch nur dann von einer Normalverteilung abweichen würde, wenn man den Klartext gefunden hätte.
Na ja. Aber GERADE DAS geht mit der hier benutzten Methode ja nicht: Auch der Ciphertext weist alle statistischen Eigenschaften der benutzten Sprache auf, nur ein wenig stärker verteilt (über hier drei Schlüsselelemente aufgefächert).
Ich habe 26^3 = 17576 Varianten zu analysieren. Das ist nicht viel, aber zu viel, um es zu überfliegen...
Bleibt wohl nur eine Analyse...

Ähmmm...: Nein. Mit einem regulären Ausdruck rux fix auf wenige Möglichkeiten eingeschränkt. Es war nur nicht so offensichtlich, daß da auch Klammern gebraucht werden. Diese zusätzlichen Sonderzeichen haben ein paar Minuten einschließlich einer sinnlosen Fehlersuche extra gekostet...

Es ist offenbar ein Text aus der Bibel (ich kenne mich da leider nicht aus).
Und er verschwindet immer noch aus dem Filter, wenn ich ihn komplett greifen lasse...
Lichtblitz: Es geht aber ja jetzt auch OHNE das Filter...

(The Gospel of John, chapter 1) 1 In the beginning the Word already existed. He was with God, and he was God. 2 He was in the beginning with God. 3 He created everything there is. Nothing exists that he didn't make. 4 Life itself was in him, and this life gives light to everyone. 5 The light shines through the darkness, and the darkness can never extinguish it. 6 God sent John the Baptist 7 to tell everyone about the light so that everyone might believe because of his testimony. 8 John himself was not the light; he was only a witness to the light. 9 The one who is the true light, who gives light to everyone, was going to come into the world. 10 But although the world was made through him, the world didn't recognize him when he came. 11 Even in his own land and among his own people, he was not accepted. 12 But to all who believed him and accepted him, he gave the right to become children of God. 13 They are reborn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.14 So the Word became human and lived here on earth among us. He was full of unfailing love and faithfulness. And we have seen his glory, the glory of the only Son of the Father.

Ergebnis: 107359

60 Primzahlenspielerei

Aufgabe im Euler-Projekt
Erstmal schaue ich mir die einfachen Zwillinge bis zu einem Grenzwert an...

3 -> (7,11,17,31,37,59,67,73,109,137,191,229,271,331,359,373,449,467,499,541,557,607,613,617,673,701,719,733,739,823,929,947,)
7 -> (19,61,97,109,127,229,283,433,487,523,541,547,673,691,757,823,829,853,883,937,)
...

Unter denen ist jetzt eine Kombination gesucht, so daß sich eine möglichst lange Kette ergibt und alles mit allem zusammenpaßt.
Wenn wir eine Kette finden, wird die auf jeden Fall komplett zu einer Basis gehören, oder? Weil: Es soll ja JEDES Element der Kette mit JEDEM kombinierbar sein! Also immer AUCH mit dem ERSTEN...
-> Eine Datenstruktur eingeführt, die das Zeug hierarchisch aufnimmt...

Letztlich ist das hier allerdings in PHP nicht mehr im Sekundenbereich realisierbar. Jedenfalls nicht ohne Ausnutzung von ausführlichem Vorwissen, welches man eh erst im Laufe der Experimente mitkriegt. Die effektive Ermittlung des "prim-Seins" über ein Array von Primzahlen ist bei der Länge der verketteten Zahlen (wir müssen in den zwei mal vier - stelligen Bereich gehen) in PHP und auf meinem Rechner nicht mehr darstellbar (der Speicherbedarf geht in die Gigabyte, weil PHP für jedes Datenelement einige zig Bytes Verwaltungsdaten anlegt).

Ergebnis: 13,5197,5701,6733,8389
(12 Minuten)

61 Zahlenreihen-Spielerei

Aufgabe im Euler-Projekt
Hmmm... Wir haben gewissermaßen aus allen möglichen Vertretern jener 6 Zahlenreihen, die 4 Dezimal-Digits groß sind, irgendeine Folge herauszusuchen, die sich durch die spezielle hier beschriebene "Zyklizität" auszeichnet.
Wieviele Zahlen hätten wir gegeneinander zu testen?
Ich bin mal faul und stelle nicht quadratisch um...
Reihe 3: 96
Reihe 4: 68
Reihe 5: 56
Reihe 6: 48
Reihe 7: 43
Reihe 8: 40

Von denen brauchen wir nur die, irgendwie verkettet werden können.
Wobei allerdings angesichts dessen, daß wir eine Verkettung über zwei Ziffern vornehmen und jeweils (exponentiell betrachtet) rund 100 Varianten von Zahlen und damit recht wahrscheinlich unterschiedlichen Ziffernfolgen in den Anfangsziffern jeweils aller Mitglieder aller anderen Folgen existieren, die Wahrscheinlichkeiten für den Rauswurf von Mitgliedern auf dieser Betrachtungsebene recht gering sein dürften.

Zum Verketten: Dabei dürften dann wieder nicht mehr so viele Varianten existieren...
Allerdings können ja alle Reihentypen in beliebiger Reihenfolge in der Verkettung vorkommen, so daß jeweils alle noch möglichen Varianten durchgespielt werden müssen.
Wegen der von vornherein vorgegebenen Zyklizität ist es aber egal, wo wir anfangen...

gefundene Kette:
Reihe 3 -> 8256
Reihe 4 -> 5625
Reihe 7 -> 2512
Reihe 8 -> 1281
Reihe 6 -> 8128
Reihe 5 -> 2882

62 Kubikzahlenspielereien

Aufgabe im Euler-Projekt
Hmmm... Die EIGENTLICHE Aufgabe heißt wohl eher:
Innerhalb einer Gruppe von Kubikzahlen mit gleicher Stellenzahl im Dezimalsystem ein paar Vertreter finden, die den gleichen Satz von Dezimalziffern verwenden.

Also: Kubikzahlengruppen bilden, die gleiche Stellenzahl haben.
Dabei mit den kleinsten beginnen und nach oben offen fortsetzen.
Dann innerhalb der Gruppen eine Dezimalziffernbeschreibung bilden.
Dann diese auf Gleichheiten vergleichen...

gefundene Gruppe: (913237656408,936302451687,536178930624,140283769536,613258407936,)
gefundene Gruppe: (569310543872,352045367981,127035954683,373559126408,589323567104,)

Ach ja... Und den kleinsten Vertreter einer solchen (letzteren) Gruppe suchen wir...

Das ist: 5027 ^ 3 = 127035954683

63 Potenzspielereien

Aufgabe im Euler-Projekt
Hmmm... Also: Eine "10" hoch "irgendwas" ergibt im Dezimalsystem immer genau eine Stelle mehr als das "irgendwas". -> Wir können also nur glücklich werden mit Basen kleiner als die Zahlensystembasis. Ergo mit den Ziffern.
Und mit einer dann maximalen "9" als Basis werden wir irgendwann zuwenig Ziffern kriegen, nämlich bei: 9 ^ 22 = 984770902183611232881
Jetzt brauchen wir also nur pro Exponent (genau 22 Varianten: von 0 bis 21) jeweils alle Ziffern durchprobieren, was trivial ist...
Ergebnis: 50

Allerdings meint ProjectEuler, daß das falsch wäre...

Aha: Eine "0" ist bei ProjectEuler kein "positiver Integer".
Wieder was dazugelernt (eine erste Andeutung, daß bei den folgenden Aufgaben der Scherzanteil wichtiger wird als der ernsthafte Kern der Sache)...

64 Reihenzerlegungen

Aufgabe im Euler-Projekt
Hmmm... Die erste Hürde hierbei: Was soll der SINN hinter den Zerlegungen sein? Welcher GOTT schreibt vor, daß man z.B. bei einer Wurzel aus 23 zuerst die Zahl 4 abspaltet?

Erst zwei Tage "ausliegen" der Gedanken über diese ominösen Aktivitäten und zwischendurch Reinschauen in das folgende Problem 65 führte mich hier zu der Erkenntnis dessen, was die Aufgabensteller offenbar für ein zu hütendes Geheimnis halten... (wieder mal faktisch ein Problem des "social engineering"...)

Es geht offenbar darum, Terme darzustellen in der Form: x = x0 + Rest, wobei der "Rest" vom Betrag her immer kleiner als "1" und das "x0" immer positiv gehalten wird. Wobei das Verfahren dann mit dem Reziproken des Rests fortgesetzt wird. Also:
x = a0 + r0; r0 = 1 / (a1 + r1); r1 = 1 / (a2 + r2); ...
...wobei es nur darauf ankommt, die ganzzahligen a's zu bestimmen, bis der Rest hinreichend klein geworden ist, und das Ganze schlußendlich wieder von hinten aufzurollen um von einem vernachlässigbaren Rest (der Null gesetzt wird) ausgehend das x zu ermitteln...
r[hinreichend groß] = 0; ... r[i-1] = 1 / (a[i] + r[i]); ... r[0] = 1 / (a[1] + r[1]); x = a[0] + r[0];

Wobei mir als nicht ausgebildetem Hobby-Mathematiker durchaus mehr Fragen entstehen als Antworten kommen: Warum soll x0 immer nur positiv bleiben? Wäre es nicht gerade bei der beispielhaft gegebenen Wurzel aus 23 effektiver, ein x0 von 5 abzuspalten?...
Unabhängig davon ist aber die Aufgabenstellung in dieser Hinsicht eindeutig.

Offenbar ist die 64 eine momentane magische Grenze in den Aufgaben des Euler-Projekts, ab der die Aufgabenstellungen nur noch von Insidern, die sich die Lösung eh aus dem Handgelenk schütteln können, überhaupt auf Anhieb erfaßt und um die zwingend notwendig wärenden Hinweise aus der Erinnerung an bereits Gelerntes ergänzt werden können. Ich hoffe, daß sich die Qualität dahingehend noch verbessert...

Die nächste Frage, die mir als Nicht-Mathematiker kommt: Kann ich effektiv die Koeffizienten ermitteln, ohne zuvor eine (momentan mir nicht vorliegende) "echte Bruchrechnung" zu etablieren?

a[0]: 4, Rest: 1.25654736047 a[1]: 1, Rest: 3.89791576166 a[2]: 3, Rest: 1.11369021762 a[3]: 1, Rest: 8.79583152331 a[4]: 8, Rest: 1.25654736047 a[5]: 1, Rest: 3.89791576164 a[6]: 3, Rest: 1.11369021764 a[7]: 1, Rest: 8.79583152142 a[8]: 8, Rest: 1.25654736346 a[9]: 1, Rest: 3.89791571621
Hmmmm... Naja: Der Rest "wandert" ganz schön gewaltig...
Einfach mal versuchen wäre es aber wert...
Immerhin brauche ich NUR eine Periode in den Koeffizienten feststellen, wobei ich vom Aufgabensteller ja immerhin wenigstens schon die analytische Arbeit erledigt bekommen habe, daß ich mich darauf VERLASSEN können sollte, daß eine Periode auftritt...
Ich schaue also nach einem Rest, der zusammen mit einem gleichen Koeffizienten hinreichend dicht an einem vorher schon mal erreichten Rest liegt...

Hmmm... Interessante Einblicke und Erkenntnisse...
Also: Ganz so einfach können wir es uns nicht machen, weil die Rundungsfehler zu schnell überhand nehmen...
Oder aber: Eventuell sollte ich die Toleranzschwelle ändern?
-> Das bringt's schon mal bis zur Wurzel(94)...
Dann allerdings werden die Rundungsfehler zu groß.
OK, das deckt sich mit der in der Aufgabenstellung vermittelten Erkenntnis, daß diese Art der Approximation eine im allgemeinen sehr effektive solche sein soll.

Ich benötige also eine andere Darstellung. Am besten eine, die das Wurzelziehen in diesem speziellen Fall umgeht. Mindestens aber eine Erhöhung der Genauigkeit.

Hmmm.. Wenn ich die Funktion an sich so lassen will, wie sie ist (so daß ich x-beliebige Zahlen darstellen lassen kann), sollte ich nur die Genauigkeit erhöhen. DAS sollte trivial sein...

Nächste Erkenntnis: Die Folge bricht bei den Quadratzahlen IMMER mit einem Glied ab, das doppelt so groß ist wie das zuerst abgetrennte, während keiner der vorher auftretenden Koeffizienten größer als jenes Abbruchglied ist (warum auch immer das so ist).
Für die Quadratzahlen könnte ich also gezielt nach diesem Glied suchen lassen. Womit ich allerdings die Allgemeinheit der Funktion verliere.
Andererseits zeigt sich, daß die Erhöhung der Stellenzahl innerhalb der Funktion allein keine Verbesserung bringt. Offenbar ist schon der Fehler, der durch die Erzeugung des Arguments mittels 8-Byte-Gleitkomma verursacht wird, Schuld an den Fehlern...

Der Toleranzbereich für den internen Rechenfehler innerhalb der Koeffizientenermittlung kann dagegen irrsinnig hoch angesetzt werden: erst bei 0.1 (sprich: rund 10%) kommt es zu ersten fehlerhaften Erkennungen des Abbruchs.

Hübsch... Alle Koeffizienten unterwegs bis zum "Wrapper" sind höchstens so groß wie das erste abgetrennte Glied. Allerdings immerhin bis maximal so groß. Da der Fehler des Restwertes sich proportional dem Quadrat des Restwertes vergrößert, steigt er logischerweise an solchen Stellen sprunghaft an. Außerdem sind die Koeffizientenfolgen grundsätzlich spiegelsymmetrisch zwischen dem Anfang an dem Wrapper-Element.
Gut, die Sachen kann man alle zur Fehlereingrenzung benutzen...

Mit 50 Stellen geht es immerhin bis zur Wurzel( 631)...
Mit 100 Stellen geht es immerhin bis zur Wurzel(2311)...
Mit 150 Stellen geht es immerhin bis zur Wurzel(3259)...
Mit 220 Stellen schaffen wir es schließlich bis zum Ziel...

Es ist aber abzusehen, daß der Aufwand für rein numerische Brute Force in den Tausender Wurzeln rabiat ansteigt... Die Erkenntnis, daß es prinzipiell ginge (mit sehr viel Wartezeit) stecke ich mal weg...

Das Problem hier ist nicht, eine Reihenentwicklung zu präsentieren, die für PRAKTISCHE Belange in Bezug auf Genausigkeit hinreicht, sondern eine, die die vorgefundenen langen Perioden ihrer selbst zu fassen gestattet. Also doch eher eine Spezialfunktion...
Allerdings tue ich mich bei der allgemeinen Herleitung der Spezialität schwer. Inzwischen ist der Algorithmus schon mit Brute Force bis zur 10000 gekommen. Die Lösung wird aber wieder mal nicht akzeptiert. Es werden also irgendwo wieder fehlerhafte Elemente versteckt sein...

Ja, das kam durch einen inzwischen für die Menge der Koeffizienten zu groß wirkenden Toleranzbereich. Den auf 1e-4 verringert liefert das korekte Ergebnis...

Lösung: 1322 (Die bisher schwierigste Aufgabe)

65 Reihenzerlegung für die Euler-Konstante

Aufgabe im Euler-Projekt
Aha... Da kommt, was ich in Aufgabe 64 noch nicht geschafft habe, als Voraussetzung: Die Brüche als ganzzahlige Dinge bestehen lassen...

66 Ganzzahlige Lösungen quadratischer Gleichungen

Aufgabe im Euler-Projekt
Hmmm, allzuviele Möglichkeiten gibt es doch nicht zu testen... Wenn ich ein x vorgebe und das "passendste" y ermittle, bleibt außerhalb der korrekten Lösung ein Rest. Wenn ich die Werte durchspaziere, sollte dieser Rest sich allmählich ändern...

Erstmal anhand d = 13 probiert: Hmmm, so richtig weiterhelfen tut das aber auch nicht: Ich müßte die Reste genauso verarbeiten, wie ich den eigentlichen Funktionswert auch verarbeiten müte, um einen Schnittpunkt mit einer Ganzzahl vorherzusagen. Letztlich müßte ich doch alle Möglichkeiten durchprobieren...

Gut, die Betrachtung der Reste hilft nicht weiter, aber ein Blick auf die Lösungen zeigt interessantes Verhalten: Lösung für d= 2 : 3
Lösung für d= 3 : 2
Lösung für d= 5 : 9
Lösung für d= 6 : 5
Lösung für d= 7 : 8
Lösung für d= 8 : 3
Lösung für d= 10 : 19
Lösung für d= 11 : 10
Lösung für d= 12 : 7
Lösung für d= 13 : 649
Lösung für d= 14 : 15
Lösung für d= 15 : 4
Lösung für d= 17 : 33
Lösung für d= 18 : 17
Lösung für d= 19 : 170
Lösung für d= 20 : 9
Lösung für d= 21 : 55
Lösung für d= 22 : 197
Lösung für d= 23 : 24
Lösung für d= 24 : 5
Lösung für d= 26 : 51
Lösung für d= 27 : 26
Lösung für d= 28 : 127
Lösung für d= 29 : 9801
Lösung für d= 30 : 11
Lösung für d= 31 : 1520
Lösung für d= 32 : 17
Lösung für d= 33 : 23
Lösung für d= 34 : 35
Lösung für d= 35 : 6
Lösung für d= 37 : 73
Lösung für d= 38 : 37
Lösung für d= 39 : 25
Lösung für d= 40 : 19
Lösung für d= 41 : 2049
Lösung für d= 42 : 13
Lösung für d= 43 : 3482
Lösung für d= 44 : 199
Lösung für d= 45 : 161
Lösung für d= 46 : 24335
Lösung für d= 47 : 48
Lösung für d= 48 : 7
Lösung für d= 50 : 99
Lösung für d= 51 : 50
Lösung für d= 52 : 649
Lösung für d= 53 : 66249
Lösung für d= 54 : 485
Lösung für d= 55 : 89
Lösung für d= 56 : 15
Lösung für d= 57 : 151
Lösung für d= 58 : 19603
Lösung für d= 59 : 530
Lösung für d= 60 : 31
keine Lösung gefunden: 61
Lösung für d= 62 : 63
Lösung für d= 63 : 8
Soweit gefundenes Maximum von x: 66249 bei d: 53

67 Routenfindung

Aufgabe im Euler-Projekt
ENDLICH wieder mal ein Problem mit sinnvollem praktischem Hintergrund!
Erster Gedanke: Lokale Optimierung, indem alle Elemente rausgeschmissen werden, die eine lokal absehbare bessere Alternative haben.
Es könnten Knoten und Stege unterschieden werden.
Es könnte aber auch reichen, nur die Stege oder die Knoten wegzunehmen...

Eventuell mache ich es GANZ anders: Was interessiert mich der innere Aufbau, wenn ich die Pyramide Zeile für Zeile abbaue?
In jeder Zeile kann ich die jeweils auf jedem Element maximal erreichbare Summe notieren, und die nächste Zeile ist davon exakt 2 * Anzahl der Zeilenelemente entfernt.
Ich ERSETZE also einfach in jeder Zeile die Elemente durch die soweit maximal erreichbaren Summen. Damit wird das ganze trivial...
Allerdings paßt dann auch die Überschrift nicht mehr so richtig.
Obwohl: Es ist halt eine triviale Routenfindung...

Maximum: 7273

68

Aufgabe im Euler-Projekt
Wir haben es bei purer Brute Force mit 10! = 3'628'800 Anordnungen zu tun. Das reicht...

121 Wahrscheinlichkeitsrechnung

Aufgabe im Euler-Projekt
Trivial, oder?
Hmmm... Nein: Die Aufgabenstellung ist definitiv falsch:
Wenn ein Spieler gewinnt, falls er MEHR blaue als rote Dinger nimmt, ist die Wahrscheinlichkeit nach 4 Zügen bei 5/120.
Bei 11/120 ist sie genau DANN, wenn der Spieler gewinnt, falls er MINDESTENS GENAUSO VIELE blaue wie rote Dinger nimmt.
Aus dem Beispieldaten geht also etwas anderes als aus der Aufgabenbeschreibung hervor.

Dies ist schon die zweite Aufgabenstellung, in der das Problem möglicherweise weniger in dem Verständnis des Wesens der Beschreibung liegt als im Entdecken irgendwelcher Hintergedanken des Aufgabenstellers. Also im "social Engineering" statt im mathematischen Problemlösen...

Allerdings ist diese Unterscheidung für die Anzahl von 15 Zügen irrelevant.

Anzahl der Versuche: 15
Anzahl der Varianten insgesamt: 20922789888000
Anzahl der Varianten mit mehr blauen als roten Punkten: 16384
Reziproke Gewinnwahrscheinlichkeit (maximaler Gewinn): 1277025750.0
Laut ProjectEuler allerdings falsch...
Auch ein Einsatz weniger wird nicht als Lösung akzeptiert...

124 Faktorisierung

Aufgabe im Euler-Projekt
An und für sich trivial (nichts neues gegenüber dem Stand ganz am Anfang...)

E(4): 8
E(6): 32
E(10000): 21417

155 Kombinatorik

Aufgabe im Euler-Projekt
Das Problem ist nur etwas anders verpackt, ansonsten aber reine Kombinatorik:
Immer wenn ein Kondensator dazukommt, kann er
  1. zu allen schon vorher möglichen Varianten parallel geschaltet werden, wodurch er die Kapazität aller Varianten um ein C erhöht, womit alle Werte auf größer C geschoben werden.
  2. allein auftreten, und damit wieder den Wert C einsetzen.
  3. zu allen schon schon vorher möglich gewesenen Varianten in Serie geschaltet werden, wodurch lauter Werte unter C hergestellt werden.
Die Menge der Varianten ist also trivial: D(n) = 2 * D(n-1) + 1 = 2 ^ n - 1
D(18) = 262143

Allerdings sagt ProjectEuler, daß das falsch sei.

Tja: Ganz so einfach ist es leider nicht. Der neue Kondensator kann auch irgendwo in die bereits bestehenden Blöcke hineingesetzt werden, was Varianten entstehen läßt, die nicht mit der einfachen Betrachtungsweise erfaßt werden...

165 Geometrie

Aufgabe im Euler-Projekt
Nun ja: Streckenschnitte. Eher trivial.
Die Herausforderung soll wohl darin liegen, daß es 5000 Strecken sind.
Das ist allerdings auch keine Hürde für plane Brute Force.
Verhübschen könnte man das durch Vorselektionsmethoden, wo allerdings die Mehrdimensionalität ein Problem darstellt.

Menge der "echten" UND "unterschiedlichen" Schnittepunte: 2868868

Hmmm...
Mal ein paar Überlegungen zu eventuellen Rechenfehlern: Weiter:
-> Unklar. Genau wie bei Problem 155...

Vergleich mit einem anderen (erfolgreichen) Rätselrater ergibt: Hmmm... Vielleicht DOCH irgendwas mit Toleranz?
tol n(1000)
0 113853
1e-6 113853
1e-5 113851
2e-5 113850
2.2e-5 113849
2.5e-5 113848
3e-5 113845
Also, ganz pragmatisch gesehen: mit der Toleranz 2.2e-5 sollte ich auf jeden Fall NÄHER am korrekten Ergebnis liegen...

tol n(5000)
2e-5 2868955
2.2e-5 2868949
2.5e-5 2868926
Hmmm... Wo liegt nun entweder der Fehler oder die Lösung?
Test aller möglichen Werte um den bei tol = 2.2e-5 herum (286854...286845) ergibt: Keiner wird akzeptiert.

Erst ein Hinweis aus dem Hackerboard bringt die Erkenntnis, daß es im letzten Satz der Aufgabenstellung einen winzigen, aber entscheidenden Zusatz "distinct" gibt...

Die Herausforderung in dieser Aufgabe bestand also darin, versteckte Hinweise im Aufgabentext zu erraten. Das halte ich eher für die Kategorie "Scherzaufgabe". Es kündet von der Fähigkeit des Aufgabenstellers, sich mißverständlich ausdrücken zu können, nicht jedoch von der Fähigkeit, mathematische Aufgaben zu stellen...