Autor Beitrag
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1600
Erhaltene Danke: 232


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 11.04.13 06: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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 11.04.13 07:55 
Hallo,

@user profile iconMathematiker:
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.
ausblenden 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:
ausblenden 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// ist gleich i+2
      //Startsumme suchen
      repeat
        inc(j);
        inc(differenz,j); 
      until differenz >= von;
      //Hier muesste man eigentlich die letzte Differenz und j 
      //fuer den naechsten Durchgang  i->i+1 speichern, um die repeat Schleife abzukuerzen

      //Jetzt ist differenz >= von, nun nur noch differenz < bis testen
      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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Do 11.04.13 14:54 
Hallo Horst_H,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Do 11.04.13 16: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
ausblenden Quelltext
1:
  z = n(n+1)/2 - m(m+1)/2					

gesucht, für natürliche n und m. Auflösung ergibt
ausblenden 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
ausblenden Quelltext
1:
  4n² + 4n + 1 - 8z - u²  =  0					

u muss ungerade sein. Erneutes Lösen liefert
ausblenden 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
ausblenden Quelltext
1:
  8z = v² - u² = (v-u)(v+u)					

Da u ungerade ist, muss es auch v sein. Damit kann man umschreiben zu
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 11.04.13 17: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 18:34, insgesamt 1-mal bearbeitet
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 11.04.13 17: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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Do 11.04.13 18: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,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
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



BeitragVerfasst: Sa 13.04.13 09: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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Sa 13.04.13 11:50 
user profile iconkaufmax hat folgendes geschrieben Zum zitierten Posting springen:
Mathe hab ich schon in der woche genug.

:nixweiss:

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1600
Erhaltene Danke: 232


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Sa 13.04.13 12:13 
user profile iconkaufmax hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 13.04.13 12: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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Sa 13.04.13 12: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 :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 13.04.13 14: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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Sa 13.04.13 15: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^^

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 13.04.13 15: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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Sa 13.04.13 16: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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mo 15.04.13 07: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.
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 15.04.13 08:42 
Hallo Horst_H,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1653
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Di 16.04.13 22: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