| Autor |
Beitrag |
Delphi-Laie
 
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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?
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker 
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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 _________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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 _________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
|
Zuletzt bearbeitet von Horst_H am Do 11.04.13 19:34, insgesamt 1-mal bearbeitet
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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:
www.entwickler-ecke.....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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
kaufmax
Hält's aus hier
Beiträge: 4
|
Verfasst: 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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 13.04.13 12:50
| kaufmax hat folgendes geschrieben : | | Mathe hab ich schon in der woche genug. |
 _________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Beiträge: 600
Erhaltene Danke: 23
Delphi 7 PE
|
Verfasst: 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?
_________________ Sucht "neueres" Delphi 
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 13.04.13 15:31
Hallo,
die Primzahlliste ist nicht das Problem.
www.entwickler-ecke....iewtopic.php?t=33013 oder
www.planet3dnow.de/v...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
Beiträge: 600
Erhaltene Danke: 23
Delphi 7 PE
|
Verfasst: 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
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^^ _________________ Sucht "neueres" Delphi
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 13.04.13 16:29
Hallo,
lies Dir www.entwickler-ecke....iewtopic.php?t=33013 mal durch, dann erkennst Du, dass man zum Sieben nur die Primzahlen bis Wurzel(MaxZahl) braucht.
Von negaH und alzaimar die Programme sind mindestens viermal so schnell wie meins, welches bei mir knapp 4 Sekunden bis 2^32-1 braucht.
Kim Walisch ist immer noch rasant code.google.com/p/primesieve/ wie Du an der Tabelle siehst.
Andere Varianten: code.google.com/p/primesieve/wiki/Links
Schneller können andere besser, aber erst mal muss es theoretisch dort auch hinkommen.
Gruß Horst
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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.
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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 _________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
|
|
|
