Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Primzahlsummen, Moser-Problem
Mathematiker - Di 09.04.13 22:17
Titel: Primzahlsummen, Moser-Problem
Hallo,
ich quäle mich wieder einmal mit einem Zahlenproblem herum, dem Moser-Problem.
Ist n eine natürliche Zahl, so existiert evtl. eine Darstellung als Summe aufeinander folgender Primzahlen, z.B.
36 = 5+7+11+13 = 17+19.
Dabei sei f(n) = k die Anzahl der verschiedenen Darstellungsmöglichkeiten für n. Auf Leo Moser geht die Frage zurück, ob für jedes f(n) = k ein n existiert.
Mein Programm sucht nun nach den jeweils kleinsten Zahlen n, für die k verschiedene Primzahlsummen existieren. Dabei betrachte ich zwei Arten. Zum einen, diejenigen die k echte Summen mit mindestens 2 Primsummanden haben, zum anderen, diejenigen mit k-1 solchen Summen, die jedoch selbst Primzahl sind.
In der Ergebnisliste ist die zweite Art mit einem * gekennzeichnet.
Das Problem ist nun, dass ich über k = 9 nicht hinauskomme. Das Programm ist einfach zu langsam.
Im Moment verwende ich folgenden Algorithmus:
Ein dynamisches Feld erhält eine Größe g. Nun werden alle Primzahlsummen von einer unteren Primzahl bis zu einer oberen Primzahl bestimmt, die noch in den Bereich g hineinpassen. Das Feldelement der gefundenen Summe wird erhöht. Danach wird die untere Primzahl erhöht usw.
Ist der Bereich 0...g abgesucht, wird der Bereich auf g...2g erweitert, danach auf 2g...3g usw. usf.
Dieses Aufteilen habe ich gewählt, da zum Beispiel ein dynamisches Feld mit theoretisch 1 Milliarde oder mehr Elementen von meinem Rechner nicht mehr (vernünftig) verarbeitet wird.
Die Suche kann nur mit dem Schalter Stopp abgebrochen werden.
Wahrscheinlich klingen meine Erklärungen etwas verworren. Aber vielleicht sieht jemand von Euch eine Möglichkeit die Suche zu beschleunigen. k = 12 wollte ich eigentlich erreichen.
Vielen Dank für Eure Hilfe und beste Grüße
Mathematiker
Rev 1/2: Überlauf beseitigt.
Rev 3: Dank
Horst_H's Hinweise ist das Feld auf die reinen Primzahlen reduziert. Damit wird weniger Speicher benötigt und die Berechnung läuft schneller.
Rev 4: Es werden nicht mehr die Primzahlen, sondern nur deren Abstand im Feld gespeichert. Das reduziert die Feldgröße erneut deutlich.
F34r0fTh3D4rk - Di 09.04.13 22:31
Wie groß werden denn die Primzahlen und dein n bei k > 8 ?
Mathematiker - Di 09.04.13 23:02
Hallo,
F34r0fTh3D4rk hat folgendes geschrieben : |
Wie groß werden denn die Primzahlen und dein n bei k > 8 ? |
Für k = 9* habe ich n = 48205429 mit
48205429 = 48205429, 46507 » 56611, 124291 » 128749, 176303 » 179461, 331537 » 333397, 433577 » 434939, 541061 » 542149, 2536943 » 2537323, 16068461 » 160668499
gefunden, wobei a » b Primzahlsumme von a bis b bedeutet. Für ein reines k = 9 kenne ich noch kein n.
Beste Grüße
Mathematiker
Nachtrag: Ich habe nun alle n bis einschließlich 300 Millionen getestet (1 h Computer quälen) und habe für k = 9 noch n = 274452156 gefunden.
F34r0fTh3D4rk - Di 09.04.13 23:23
Müssen es mindestens k Summen sein oder genau k?
Mathematiker - Di 09.04.13 23:25
F34r0fTh3D4rk hat folgendes geschrieben : |
Müssen es mindestens k Summen sein oder genau k? |
Mindestens k Summen.
Beste Grüße
Mathematiker
F34r0fTh3D4rk - Di 09.04.13 23:35
Ich hab grad erst einmal einen naiven Algorithmus in Java implementiert, um das Problem zu verstehen (Der Teufel liegt oft im Detail). Der ist vermutlich auch noch eine ganze Ecke langsamer, als das Verfahren, welches du aktuell verwendest:
C#-Quelltext
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:
| import java.math.BigInteger; import java.util.ArrayList;
public class Moser { public static boolean isPrime(long m) { int[] p17 = {2, 3, 5, 7, 11, 13, 17}; for (int i=0; i<p17.length; i++) { int a = p17[i]; if (m == a) { return true; } BigInteger A = new BigInteger(""+a); long b = A.modPow(new BigInteger(""+(m-1)), new BigInteger(""+m)).longValue(); if (b != 1) { return false; } } return true; } public static void main(String[] args) { int targetK = 4; ArrayList<Long> primes = new ArrayList<Long>(); boolean found = false; long example = -1; for (long n = 2; n < Long.MAX_VALUE; n++) { if (isPrime(n)) { primes.add(n); } int k = 0; int skip = 0; for (int s = 1; s < n; s++) { for (int p = primes.size()-(skip + 1); p >= s-1; p--) { long sum = 0; for (int i = 0; i < s; i++) { sum += primes.get(p-i); } if (sum < n) { break; } if (sum == n) { k++; skip = s; break; } } if (k == targetK) { example = n; found = true; break; } } if (found) { break; } } System.out.println("Found example for f^-1(k=" + targetK + ") = " + example); } } |
Ich schau mal, was mir da so für Tricks einfallen, um das zu beschleunigen :).
EDIT: Wenn Summen der Länge 1 mitgezählt werden sollen, muss s natürlich bei 1 anfangen.
EDIT2: Hast du
das hier [
http://www.primepuzzles.net/puzzles/puzz_046.htm] mal gelesen?
IhopeonlyReader - Mi 10.04.13 10:27
wenn es mindestens k summen sein müssen, dann ist bei 36 k auch mindestens 4
du hast geschrieben:
Mathematiker hat folgendes geschrieben : |
36 = 5+7+11+13 = 17+19 |
UND
29+7
23+13
29+5+2
und wenn die mehrfachnutzung einer Primzahl Möglich ist:
7+7+7+5+5+5
ebenfalls zeigt er mir für 311 4* 4 und 5* an... reicht nicht 5*
oder verstehe ich das Moser-Problem falsch?
Horst_H - Mi 10.04.13 11:51
Hallo,
Was für merkwürdige Rätsel.
für k= 12 soll es also minimal 166400805323 sein. 1.6*10¹¹ ist natürlich schon weit über longint hinaus.
F34r0fTh3D4rk hat Ja in seinem EDIT2 eine passende Seite gefunden, der bis 82 Milliarden die Primzahlen gespeichert hat.Ich bräuchte dafür mindestens 0.198 (1*2*4*6*10*12*16/(2*3*5*7*11*13*17)) *82e9 Bit = 2,035e9 Byte
Aber mir fällt etwas auf ;-)
Wenn man die zu untersuchende Zahl erhöht, bleiben die Zahlen, die man z.B. bei 12 Summanden untersuchen muss, natürlicherweise fast identisch.
218918+1=218919 zu untersuchen findet auf den selben Zahlen statt.Aber viel wichtiger bei sehr großen Zahlen = wenig Summanden.
Ich brauche in Bereich "großer" Zahlen ja nur ein Primzahlsieb der Region mitzuführen und ab und an aktualisieren wenn man die Region verlässt, oder ich suche eine Funktion NextPrim die eben in gewissen Regionen Miller-Rabin anwendet ( von
Gammatester
Die 50,8 Mio Primzahlen bis 1e9 lassen sich ja unkompliziert speichern.
Für die kleineren Zahlen, viele Summanden, merkt man sich nur den Startwert des Bereiches( Nummer der Primzahl in der Liste) , den Endwert und die Summe von Start bis Endwert.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| tSummand= record StartIndex, EndIndex, Summe : Int64Longint; Pufferindex : integer; RingpufferDiffenzen : array Of integer; end; Summanden = array of TSummand; |
Wie groß ist die Summe aller Primnzahlen bis 1e9?
Wenn jede 20.te Zahl prim wäre ( 50.8e6/1e9) 1/20 Summe 1..1e9 aber da die Diche der Primzahlen im wichtigen Bereich eher 1/40 ist, somit eher 1/40 * 1e9²/2 = 1.25e16 müsste also für k = 12 reichen.
Delphi-Quelltext
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:
| Ablauf: Felder der Summandenzahl 1..1000 initialisieren. maxSumZahl = 1000; Startzahl S = 2+3 wiederhole k = 0 sumAnz = 2; wiederhole with Summanden[SumAnz] do Ist S >= Summe dann Falls S = Summe dann erhoehe k wiederhole np = Nextprim(Endwert) summe = summe - Startwert+np dec(Startwert,RingpufferDiffenzen[Pufferindex]); RingpufferDiffenzen[Pufferindex] := np-Endwert; inc(Pufferindex); IF Pufferindex >= SumAnz then Pufferindex := 0; bis Summe >S; inc(sumAnz); bis sumAnz >= maxSumZahl; S = NextPrim(S); bis SNT |
Dann fehlen noch Bedingen für mehr Summenden etc. pp.
Gruß Horst
@
IhopeonlyReader
Es bezieht sich aufeinanderfolgende Primzahlen, deshalb kann mein hier skizzierter Ansatz überhaupt funktionieren.
Gammatester - Mi 10.04.13 11:52
IhopeonlyReader hat folgendes geschrieben : |
wenn es mindestens k summen sein müssen, dann ist bei 36 k auch mindestens 4
du hast geschrieben:
Mathematiker hat folgendes geschrieben : | 36 = 5+7+11+13 = 17+19 |
UND
29+7
23+13
...
oder verstehe ich das Moser-Problem falsch? |
Ja. Es wird doch gefordert "eine Darstellung als Summe
aufeinander folgender Primzahlen"
Horst_H - Mi 10.04.13 13:16
Hallo,
mir fällt gerade noch ein, dass man vielleicht ein Feld mit Zeigern auf eine einfache verkettete Liste machen könnte.
In diesen Listen steht die Anzahl der Summanden mit gleicher Summe.
Als S+4 -> 3->6->9->14->17->NIL ( uups k= 5, jetzt wird es zu einfach... )
S+5 -> NIL
..
Listeneintrag 0 -> in der Liste stehen alle Summanden deren Summe gerade S ist.
Listeneintrag 1 -> in der Liste stehen alle Summanden deren Summe gerade S+1 ist.
..
Listeneintrag 999 -> in der Liste stehen alle Summanden deren Summe gerade S+999 ist.
Listeneintrag 1000 alle restlichen, enventuell in 100er/1000er Schritten.
Dann kann ich erst alle Einträge bis 1000 verarbeiten und aktualisieren und dann einmal komplett auf den neuesten Stand bringen.Dann muss man nicht immer wieder tausende anschauen, obwohl sich nichts getan hat, denn k= 12 kommt das erste Mal bei 1.6e11 oder bezog sich dies auf S= prim?
Gruß Horst
Mathematiker - Mi 10.04.13 14:06
Hallo,
und Danke an alle mit Ihren guten Vorschlägen. Ich werde sehen, was ich davon verwenden kann.
Heute Nacht (3.24 Uhr) wurde ich munter und hatte eine Idee zur Beschleunigung des Verfahrens. Es ist wirklich so, dass das Gehirn weiterarbeitet, auch wenn man schläft.
In der verbesserten Version (siehe 1.Beitrag) berechne ich einmal(!) alle Primzahlsummen 2+3+...+p der ersten m Primzahlen und speichere diese in einem großen Feld. Praktisch ist das die Idee von Horst_H. :D
Für die möglichen Primzahlsummen muss ich dann nur die möglichen und interessanten Differenzen der Summen auswerten.
Das beschleunigt ungemein, allerdings auf Kosten des Speichers.
Jetzt werde ich meinen Computer rechnen lassen. Mal sehen, was möglich ist.
Beste Grüße
Mathematiker
Nachtrag: Mit 50 Millionen Primzahlen, d.h. der Suche bis 1,95 Milliarden ergibt sich neu für k = 10* als keinstes n = 1798467197.
Jetzt müssen es 250 Millionen Primzahlen werden. Bei meinem Computer wird das dauuuuuuuuuuuuuuuuuuuuuuuern.
Nachtrag 2: Sch... Computer. Über 125 Millionen Primzahlsummen im Feld bekomme ich ein nettes "Out of memory". :evil:
Nachtrag 3: Was ist denn jetzt los? Kann das sein, dass das Feld auf die Festplatte ausgelagert wird?
jfheins - Mi 10.04.13 16:10
Mathematiker hat folgendes geschrieben : |
Nachtrag: Mit 50 Millionen Primzahlen, d.h. der Suche bis 1,95 Milliarden ergibt sich neu für k = 10* als keinstes n = 1798467197.
Jetzt müssen es 250 Millionen Primzahlen werden. Bei meinem Computer wird das dauuuuuuuuuuuuuuuuuuuuuuuern.
Nachtrag 2: Sch... Computer. Über 125 Millionen Primzahlsummen im Feld bekomme ich ein nettes "Out of memory". :evil:
Nachtrag 3: Was ist denn jetzt los? Kann das sein, dass das Feld auf die Festplatte ausgelagert wird? |
Hi,
ich kann das ja mal im Hintergrund laufen lassen. bei mit geht's immerhin bis 223 Mio. Primzahlen. (Braucht dann 1,795 GB RAM)
Aber das Teil hängt bei läppischen 25% CPU Auslastung rum! Kann man da nicht was parallelisieren?
Und was den RAM angeht: Natürlich lagert Windows nicht benutzte Teile auf die Festplatte aus. Wenn du also 2GB Speicher anforderst und erst mal nur die ersten paar MB benutzt kann es schnell passieren dass der Rest ausgelagert wird.
Da ich anderweitig zu tun habe, werde ich wohl nicht dazu kommen eine C# Version zu programmieren ;-)
Mathematiker - Mi 10.04.13 16:35
jfheins hat folgendes geschrieben : |
ich kann das ja mal im Hintergrund laufen lassen. bei mit geht's immerhin bis 223 Mio. Primzahlen. (Braucht dann 1,795 GB RAM) |
Breche mal lieber die Berechnung ab. Ich hatte noch einen numerischen Überlauf im Programm. Ist in Rev 1 beseitigt.
Beste Grüße
Mathematiker
jfheins - Mi 10.04.13 16:42
Ach deshalb isses eingefroren ^^
Okay, also auf ein neues ;-)
Mathematiker - Mi 10.04.13 16:44
Hallo jfheins,
jfheins hat folgendes geschrieben : |
Okay, also auf ein neues ;-) |
Warte mal noch einen Moment. Ich teste gerade auf einem 2.Computer und da stimmt irgendetwas nicht.
Da tritt schon wieder ein Überlauf ein. Tut mir leid.
Beste Grüße
Mathematiker
Nachtrag: Mit Rev 2 gab's keinen Überlauf mehr. Nochmals Entschuldigung bitte.
jfheins - Mi 10.04.13 18:20
Ja, jetzt läuft's einigermaßen :-)
Immer noch nicht multithreaded, aber ich habe schon paar Ergebnisse:
Zitat: |
Berechnung bis 9326037144
2* 5
2 36
3* 41
3 240
4 311
4* 311
5* 311
5 16277
6* 34421
6 130638
7 218918
7* 442019
8* 3634531
8 9186778
9* 48205429
9 274452156
10* 1798467197
10 4611108324
Ende
gesucht bis 9300000000 |
Edit: Ist fertig.
F34r0fTh3D4rk - Mi 10.04.13 20:56
Wenn man das plottet (angenommen, man nimmt immer das kleinste n), hat die Kurve eine starke Ähnlichkeit zu einer Exponentialfunktion. Ich postuliere weiterhin, dass f(n) normalverteilt ist :?!?: :).
Mathematiker - Mi 10.04.13 21:40
Hallo,
jfheins hat folgendes geschrieben : |
aber ich habe schon paar Ergebnisse: Zitat: | Berechnung bis 9326037144 ...
10* 1798467197
10 4611108324 |
|
F34r0fTh3D4rk hat folgendes geschrieben : |
Wenn man das plottet (angenommen, man nimmt immer das kleinste n), hat die Kurve eine starke Ähnlichkeit zu einer Exponentialfunktion. |
Wenn man die Ergebnisse sich ansieht und dazu noch den von
F34r0fTh3D4rk angegebenen Link
http://www.primepuzzles.net/puzzles/puzz_046.htm, so wird klar, dass mit meiner Lösung nichts Neues gefunden werden kann.
Um den bisher von Wilfred Whiteside getesteten Bereich bis 260 Milliarden zu übertreffen, würde ich deutlich über 5 Milliarden Primzahlsummen benötigen. Das hält wohl kein Speicher aus; nicht zu reden von der extrem steigenden Berechnungs- und Auswertungszeit.
Fazit: Entweder wir finden eine neue Superidee für das Problem, oder das war's. Leider. :nixweiss:
Danke an alle für Eure Bemühungen.
Beste Grüße
Mathematiker
Horst_H - Mi 10.04.13 22:35
Hallo,
da habe ich etwas nicht verstanden, wie das sein kann:
Zitat: |
4 311
4* 311
5* 311 |
Es kann doch nicht gleichzeitig einer 4er und eine 5er Zerlegung von 311 geben.
Ach, ich habe es falsch verstanden.Vorher gab es maximal eine dreifache Zerlegung in eine Summe von aufeinander folgender Primzahlen und nun auf einmal direkt eine 5-fache mit 311 prim.
Lazarus verweigert unter meiner experimentellen Linux-Version irgendetwas auszugeben. Mit Freepascal, als Konsolenprogramm ging es. Jau, gotoXY funktioniert, nachdem ich die Konstante grenze global gemacht habe, die lies sich innerhalb der procedure nicht ändern, das zu finden hat gedauert.
Wie ist denn eigentlich das Laufzeitverhalten, das müßte doch quadratisch sein.
Wenn es für 2^32= 4,3e9 2 Stunden waren, sind es für 1,6e11 schätzungsweise:
(1.6e11/4.3e9)^2 *2h = 2775.5 h = 16,6 Wochen.
Mathematiker hat es ja schon erkannt, dass dauert.
Da ist doch mein Vorschlag nicht übel, mit bis zu 1000 Summanden seperat zu speichern, denn 1000 * Zahlen im Bereich 4e9 sind eben 4e12== 400 Milliarden.
Die maximale Anzahl an Summanden kann man ja auch bestimmen, das ist die Summe aller Primzahlen ab 2 ..? die dann 4e12 ergeben und dass sind deutlich unter 50 Mio. ich rate 25 Mio.
Für diese Zahlen mit kleinen Summanden, die man noch im Speicher halten kann reichte ein record von
Delphi-Quelltext
1: 2: 3: 4: 5:
| tkleinerSummand= record StartIndex, EndIndex: Dword; Summe : Int64; end; |
Für kleine Summanden also ein Feld [1.. 25e6] of tKLeinerSummand ~ 400 Mb
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| tGroßerSummand= record StartWert, EndWert, Summe : Int64; PufferStartPos: ^byte; PufferIndex :^byte; end; Ringpuffer = array [0..1000*1001 div 2] of byte; Bei 2 Summanden zeigt PufferStartPos auf Ringpuffer[0] PufferIndex geht von 0..0( Summandenzahl-2 ) Bei 3 Summanden zeigt PufferStartPos auf Ringpuffer[1] PufferIndex geht von 0..1 Bei 4 Summanden zeigt PufferStartPos auf Ringpuffer[3] PufferIndex geht von 0..2 Bei 5 Summanden zeigt PufferStartPos auf Ringpuffer[6] PufferIndex geht von 0..3 |
..
Natürlich gingen auch dynamische Felder. Aber brauchen noch mehr Platz, aber bei 1000 Feldern in der Länge von 1,2,3,4..999 ist das kein großer Aufwand.
Natürlich fehlen noch die Primzahlen 50.8 Mio als DWORD. = 200 Mb
Also 600 Mb könnten fast reichen :-)
Wer wird denn da verzagen, dass ist doch nur ein Ansporn.
Wenn man sich auf istPrime verlassen kann, der ja recht schnell zu sein scheint, brauchen nur die obersten Summanden diesen Primtest, wie in dem Link zum prime puzzle46.
Vielleicht könnte hier sogar ein 64-Bit Betriebssystem von Vorteil sein, bei den ganzen Int64 hier.
Gruß Horst
Mathematiker - Mi 10.04.13 23:48
Hallo,
trotz der motivierenden Worte von
Horst_H habe ich erst einmal das Moser-Problem kurz abgebrochen und eine Verallgemeinerung betrachtet.
Sucht man allgemein die Darstellung einer natürlichen Zahl n als Summe aufeinanderfolgender natürlicher Zahlen (nicht notwendig Primzahlen), so ergeben sich auch für kleine n eine Vielzahl von Möglichkeiten.
Meine Annahme, dass man schnell viele Zahlen n findet, für die genau k solche Summen existieren, war aber ein Trugschluss.
Obwohl ich meinen Computer mit 100 Millionen Zahlsummen gequält habe (die Festplatte leistete eine Mammutaufgabe) habe ich keine Zahl gefunden, für die es genau 18 solche Summen gibt.
Die ersten Ergebnisse sind
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| k kleinste Zahl 6 729 7 105 8 225 9 405 10 59049 11 315 12 531441 13 3645 14 2025 15 945 16 43046721 17 1575 18 --- 19 2835 20 18225 21 295245 22 --- 23 3465 24 50625 25 2657205 |
Schön ist, dass man keine Primzahlberechnung mehr braucht. Nicht so schön ist, dass man zum Testen aller Zahlen bis 1 Milliarde nun 500 Millionen Summen benötigt, bei dem Original-Moser-Problem sind es nur etwas über 50 Millionen.
Aber vielleicht kann man bei diesem "einfacheren" Problem noch schneller einen effektiven Algorithmus finden.
Ich gehe jetzt erst einmal in's Bett und werde wohl wieder von Zahlen träumen.
Beste Grüße
Mathematiker
Nachtrag: In einem späteren Beitrag habe ich eine sehr schnelle Lösung des Problems. Deshalb ist der Anhang hier nicht mehr vorhanden.
Delphi-Laie - Do 11.04.13 07:23
Ist das Problem überhaupt anders als mit Probeberechnungen zu lösen?
Falls nein, so wirkt es auf mich NP-vollständig (habe da aber nun wirklich keine vertiefte Kenntnisse).
Horst_H - Do 11.04.13 08:55
Hallo,
@
Mathematiker:
es ist nicht gut morgens um 3:24 Uhr eine gute Idee zu haben und abends um 23:00 Uhr das nochmals zu verlangen.
In Deiner Variante AllMoser mit aufeinanderfolgenden natürlichen Zahlen kannst Du statt der Summe diese auch mit der allseits beliebten Gaußsummenformel berechnen.
k>=a
Summe( i = a..k )= Summe(i= 1..k )-Summe i= (1..a)
=( k*(k+1)-a*(a+1)) /2
aber das ist ja nicht einmal nötig , das a ist doch innerhalb der Schleife konstant und Summe k kann man fortlaufend in der Schleife bilden.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:
| Statt: for i:=0 to grenze-2 do begin j:=i+2; repeat differenz:=summe[j]-summe[i]; if (differenz>von) and (differenz<bis) then inc(feld[differenz-von]); inc(j); until (j>grenze) or (differenz>bis); Nun ohne das gigantische Summenfeld SummeA := 0; for i:=1 to grenze do begin inc(SummeA,i); SummeK :=SummeA+ i+1; j:=i+2; repeat inc(SummeK,j); differenz:=SummeK-SummeA; if (differenz>von) and (differenz<bis) then inc(feld[differenz-von]); inc(j); until (j>grenze) or (differenz>bis); |
Ich teste es mal.
Gruß Horst
Edit:
Es geht noch kompakter, ohne SummeA,SummeK, indem man nunmehr ausschließlich die Differenz betrachtet:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| for i:=1 to grenze-2 do begin differenz := i+1; j:=i+1; repeat inc(j); inc(differenz,j); until differenz >= von; repeat if differenz<bis then inc(feld[differenz-von]); inc(j); inc(differenz,j); until (j>grenze) or (differenz>=bis); |
Das macht die Sache sogar schneller.
Was mir nicht einleuchtet sind die Zahlen hinter den Vielfachen.Diesee zeigen an, welches die letzte Startzahl(i+von) einer Summe war die zum k.ten Mal die DifferenzSumme erzeugte.Ach, was macht man damit?
Mathematiker - Do 11.04.13 15:54
Hallo Horst_H,
Horst_H hat folgendes geschrieben : |
Es geht noch kompakter, ohne SummeA,SummeK, indem man nunmehr ausschließlich die Differenz betrachtet: |
Dein Vorschlag beschleunigt die Suche extrem. Besonders toll ist, dass das Summenfeld nicht mehr auftritt. Vielen Dank.
Im Moment lasse ich gerade meinen Rechner arbeiten und bin schon bei 600 Millionen. Eine Zahl mit genau 18 Zerlegungen habe ich auch schon: n = 387420489.
Beste Grüße
Mathematiker
Mathematiker - Do 11.04.13 17:51
Hallo,
das allgemeine Moser-Problem ist mathematisch "gelöst".
z sei eine natürliche Zahl und f(z) die Anzahl der verschiedenen Möglichkeiten, z als Summe aufeinanderfolgender natürlicher Zahlen darzustellen. Die Summe der natürlichen Zahlen von 1 bis n ist n(n+1)/2, d.h. es wird die Anzahl aller möglichen Gleichungen der Form
Quelltext
1:
| z = n(n+1)/2 - m(m+1)/2 |
gesucht, für natürliche n und m. Auflösung ergibt
Quelltext
1:
| m = 1/2 (-1 + Wurzel(1 - 4(2z - n(n+1))) |
wobei der Radikand eine Quadratzahl sein muss. Damit gibt es eine ganze Zahl u mit
Quelltext
1:
| 4n² + 4n + 1 - 8z - u² = 0 |
u muss ungerade sein. Erneutes Lösen liefert
Quelltext
1:
| n = 1/2 (-1 + Wurzel(8z + u²)) |
Da der Radikand wieder Quadratzahl sein muss, gibt es eine ganze Zahl v, so dass gilt
Quelltext
1:
| 8z = v² - u² = (v-u)(v+u) |
Da u ungerade ist, muss es auch v sein. Damit kann man umschreiben zu
Quelltext
1:
| 2z = [(v-u)/2] [(v+u)/2] |
Die Aufgabe besteht folglich darin, 2z in zwei Faktoren A = (v-u)/2 und B = (v+u)/2 zu zerlegen.
A und B müssen entgegengesetzte Parität besitzen, eine ist ungerade, eine gerade. Ist d ein beliebiger Teiler von z, kann man A = d und B = 2z/d setzen bzw. umgekehrt.
Insgesamt bedeutet dies: Die Anzahl der verschiedenen Möglichkeiten, z als Summe aufeinanderfolgender natürlicher Zahlen darzustellen, ist gleich der Anzahl ungerader Teiler von z (ohne die 1!).
Damit kann die Aufgabe so verändert werden, dass die kleinste Zahl gesucht wird, die eben eine bestimmte Anzahl ungerader Teiler hat.
Im Moment weiß ich noch nicht, wie das gehen soll und ob das schneller möglich ist.
Beste Grüße
Mathematiker
Horst_H - Do 11.04.13 18:27
Hallo,
uff!
Ich dachte schon, Du willst Deinem Namen nicht gerecht werden, indem Du einfach ein Programm "probieren" lässt. tse tse tse ;-)
Und kommt bei n = 387420489 = 3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 =3^18 auch 18 heraus?
Minimale 18 ungerade Faktoren in Reinkultur :-)
Ich habe das Programm geändert.
Es zählt jetzt wie häufig eine bestimmte Anzahl an Zerlegungen auftritt. Bis 1e9 keine mit 36, kann dass stimmen oder habe ich etwas wegoptimiert...3^36 ist aber auch 1.5e17...
Gruß Horst
EDIT:
Scheinbar gibt es da etwas früheres
Zitat: |
von 4250000000 bis 4300000000
...
Vielfache 35 Haeufigkeit 12617016
Vielfache 36 Haeufigkeit 1
|
Horst_H - Do 11.04.13 18:50
Hallo,
noch was zum Ausgangsproblem. Wir hatten doch mal was mit der k.ten Primzahl dort habe ich meine Version eines Siebes mal eingestellt:
http://www.entwickler-ecke.de/viewtopic.php?p=668003#668003
Wenn man für jedes Element mit großen Primzahlen nur die Überträge der Siebprimzahlen ( bis 1e6 = 78498 x4Byte) und die gesiebten Primzahlen speichert ( alle 20 bei 1e9 ? ~ 3000 x4Byte) sind das etwa 91 kb zusätzlich.
Das 1000 fach sind 91 Mb. Dann sind 1 Gbyte noch nicht erreicht.
Der Vorteil ist, das man wahnsinnig schnell sieben kann.geschätzte ~1ms für einmal und man hat die Primzahlen für die nächsten 60060.
Dann müßte ich mal testen ob istPrime dies bei 1e12 das auch in 1 ms schafft.( Sonntag vielleicht )
Gruß Horst
Mathematiker - Do 11.04.13 19:57
Hallo,
so, ich bin etwas stolz.
Das allgemeine Moser-Problem ist gelöst. Das hier angehängte Programm berechnet sofort die kleinste natürliche Zahl n, für die es genau k Summen aufeinanderfolgender natürlicher Zahlen gibt.
Der Grundgedanke des Algorithmus ist die Tatsache, dass für k Zerlegungen bei der Berechnung der Teilerzahl die Zahl k+1 zu betrachten ist, da die 1 als Teiler nicht mitzählt. Anschließend wird k+1 wird faktorisiert.
Danach werden alle monoton wachsenden Partitionen der Primteiler betrachtet und aus diesen die Zahl n berechnet. Das Minimum ist das gesuchte Ergebnis.
Jetzt dröhnt mir der Kopf und ich kann mich wieder dem Ausgangsproblem zuwenden.
Hallo Horst_H,
Horst_H hat folgendes geschrieben : |
Und kommt bei n = 387420489 = 3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 =3^18 auch 18 heraus? Minimale 18 ungerade Faktoren in Reinkultur :-) ...
Scheinbar gibt es da etwas früheres
Zitat: | von 4250000000 bis 4300000000
...
Vielfache 35 Haeufigkeit 12617016
Vielfache 36 Haeufigkeit 1 |
|
Die 18 ist korrekt. Das kleinste n für 36 ist jedoch 150094635296999121. Da 37 Primzahl ist, muss es bei n = 3^36 sein.
Beste Grüße
Mathematiker
kaufmax - Sa 13.04.13 10:29
Das ist ja ganz nett, aber interessiert das einen Delphianer? Gehts nicht um Programmierung? Mathe hab ich schon in der woche genug.
kaufmax
Mathematiker - Sa 13.04.13 12:50
kaufmax hat folgendes geschrieben : |
Mathe hab ich schon in der woche genug. |
:nixweiss:
Delphi-Laie - Sa 13.04.13 13:13
kaufmax hat folgendes geschrieben : |
Das ist ja ganz nett, aber interessiert das einen Delphianer? Gehts nicht um Programmierung? Mathe hab ich schon in der woche genug. |
So einige (nicht zuletzt auch mich). Es gibt eben mehr Dinge im Himmel und auf Erden, als Eure Schulweisheit sich träumen läßt.
Sehr konstruktiver Beitrag. Schade, daß es dafür nicht den Undankschalter gibt.
Diese Wissenschaft heißt übrigens "Mathematik". Die "Mathe" liegt hingegen gewöhnlicherweise vor der Haus-/Wohnungstüre.
Horst_H - Sa 13.04.13 13:44
Hallo,
ein Undank-Schalter ist wohl etwas übertrieben.
Die Sparte heißt aber auch Algorithmen und dort fügt es sich ja ganz gut ein
Gruß Horst
IhopeonlyReader - Sa 13.04.13 13:53
Dein Problem scheint gelöst zu sein.. da ich gelesen hatte, dass du am anfang eine Liste aller Primzahlen brauchst, habe ich mal getestet wie schnell ich möglichst viele Primzahlen zusammenkriege...
ich erreiche ca. 75 Millionen Primzahlen (also bis 1,5 Milliarden ca) in unter 25 sek...
1. brauchst du überhaupt noch die "Primzahlenliste"
2. ich denke du kriegst das warscheinlich noch irgendwie schneller hin oder?
Horst_H - Sa 13.04.13 15:31
Hallo,
die Primzahlliste ist nicht das Problem.
http://www.entwickler-ecke.de/viewtopic.php?t=33013 oder
http://www.planet3dnow.de/vbulletin/showthread.php?s=a16c206584bf6343d5d37eacccad8291&t=119641&page=16
Mein Beitrag knapp hier drüber hat auch eine einfaches Sieb, dass ich für dieses Problem hier leicht anpassen könnte, weil ich es selbst erstellt habe und es benutzt nur einen sehr kleinen Speicherbereich, wo ich nur immer wieder über 4*30030 entsprechend verschoben siebe und dann bis theoretisch bis MaxInt64 sieben könnte.
Eine Tabelle für Primzahlen bis .. könnte mal ja auch einmal auf die Festplatte bannen und gut ist.Vielleicht auch per MMF nutzen, mal schauen. Ich hoffe, Dir fällt noch etwas anderes ein, damit man möglichst viele Ideen auch kombinieren kann. Einer allein, kommt immer nur auf die selben dummen Gedanken ;-)
Gruß Horst
IhopeonlyReader - Sa 13.04.13 16:10
naja Horst, was du gepostest hast berechnet zwar Primzahlen/überprüft welche, aber nicht sehr "schnell".. eventuell könnte man ja mal Tests machen wer die schnellste proc. schreibt :D
Und: du müsstest eigentlich wenn du bei K nach Zahl x suchst meiner Meinung nach alle zahlen x durchgehen, bis zum ersten gesuchten K...
dafür musst du bis zur Hälfte von X (am ende K) die Primzahlen bilden und dann
solange Primzahlenfolge<X Primzahlenfolge+nächstPrimzahl
und wenn PrimzahlenFolge>X dann Primzahlenfolge-ErstePrimzahlderFolge
mehr fällt mir auch nicht ein^^
Mathematiker - Sa 13.04.13 17:22
Hallo Horst_H,
dank Deines guten Vorschlags beim Lösen des allgemeinen Problems, habe ich das Feld auf die reinen Primzahlen reduziert. Die Summen müssen nicht mehr berechnet werden.
Damit wird weniger Speicher benötigt, solange die höchste Primzahl nicht größer als das maximale Cardinal wird, und die Berechnung läuft schneller.
Die Änderung habe ich als Rev 3 gespeichert.
Jetzt werde ich mal testen, wie weit ich damit komme.
Beste Grüße
Mathematiker
Nachtrag: Ohne, dass meine Festplatte wieder verrückt gespielt hat, funktioniert es mit 100 Millionen Primzahlen perfekt. Damit ist der Bereich bis 4 Milliarden vollständig testbar. Die Lösung für 10* wird gefunden.
Horst_H - Mo 15.04.13 08:11
Hallo,
ich habe mein altes Programm von 2001 mal umgemodelt, damit es bis 86 Milliarden sieben kann und dabei das Sieb/Suchfeld vollständig im Speicher behält, was nicht sehr effektiv ist und es verzählt beim letztem DWORD, aber darum geht es ja nicht.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| 92160 Zahlen :2042040 Byte DiffFeld :92160 Byte MulFeld :200 Byte SuchFeld :1940647592 Byte 293261 86002014121 Zeit in Sekunden 1664.240000 Bis 86000000000 Sind es 3563706205 Primzahlen
real 28m54.620s user 27m41.000s sys 0m1.157s |
Es braucht knapp überlinear mehr Zeit ( 12 sekunden bis 1e9, 160 Sekunden bis 10x1e9 )
Vielleicht läuft es mit Intel Prozessoren schneller, weil sie schneller auf den Hauptspeicher zugreifen.Man kann es sicher beschleunigen, indem man abschnittweise siebt und die Zahlen dann dort einträgt, aber es geht darum die 3,5 Milliarden Zahlen in 2 Milliarden Byte unter zu bringen, also fast zwei pro Byte.Aber dann kann man nicht einfach direkt darauf zu greifen, sondern muss von der letzten Stelle aus suchen, aber nicht sehr weit.
Vielleicht sollte man auch nur ein Feld mit Differenzen shr 1 speichern. Sind zwar nur halb soviel Primzahlen, aber wesentlich schneller.
Gruß Horst
Mathematiker - Mo 15.04.13 09:42
Hallo Horst_H,
Horst_H hat folgendes geschrieben : |
Vielleicht sollte man auch nur ein Feld mit Differenzen shr 1 speichern. Sind zwar nur halb soviel Primzahlen, aber wesentlich schneller. |
Deine Idee habe ich aufgegriffen und speichere im Feld nun den Abstand benachbarter Primzahlen (Rev 4). Das reduziert die Feldgröße erneut deutlich, da ich nun nur noch 2 Byte (smallint), an Stelle der ursprünglichen 8 (int64), für eine Primzahl benötige.
Zwischen 436273009 und 436273291 wird der Abstand mit 282 erstmals größer als 255, d.h. Byte genügt nicht.
Die Speicherung der halben Differenz in einem Byte funktioniert zwar bis Primzahl 304599508537, da deren Abstand zur nächsten Primzahl 304599509051 schon 514 ist, dann müsste 2 aber gesondert behandelt werden.
Dein Beispielprogramm zur schnellen Primzahlbestimung werde ich mir heute noch ansehen.
Beste Grüße
Mathematiker
Horst_H - Di 16.04.13 23:06
Hallo,
ich habe das segmentierte Sieb von mir verändert um in höhere Regionen zu kommen.
Ohne speichern der Zahlen sind es also für 1e11 Zahlen ~260 Sekunden.
Zitat: |
ERATOSTHENES SIEB bis: 100000000000
Zahlen im Sieb : 360360
Maximale Suchprim 316241
Maximale SuchprimIndex 27293
Es sind 4118054813 Primzahlen von 1 bis 100000000000
Es wurden 277501 Siebe gesiebt.
Es dauerte 04.16.566
|
Bei den Laufzeiten kann man in etwa 12-fache Laufzeit für 10-fache Anzahl abschätzen, ca 1,8 Sekunden für 1e9
Ich frage mich, wozu mit smallint die Abstände zu speichern, wenn man sowieso nicht bis 304.599.509.051 kommen wird, weil es schon um die ca. 12 x1e9 Primzahlen sein werden.Ich habe nur 4 GB Hauptspeicher, wovon 3294 Mb nutzbar sind.
Was ich aber aufzeigen wollte, dass diese Version etwa 5-mal langsamer als die von Kim Walisch ( single threaded 0.4 Sekunden bis 1e9 )ist, aber immer noch 8mal schneller als prime3a.
Es fehlen noch Korrekturen für das erstellen der Siebprimzahlen, da habe ich noch einen hartnäckigen Fehler, aber es ist ja auch schon dunkel ;-)
Gruß Horst
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!