Scherk-Zerlegungen

Mathematiker · Verfasst: Fr 12.09.14 16:59

Hallo,
"verflixtes" Wikipedia! Kaum erscheint wieder ein neuer Beitrag zur Zahlentheorie, juckt es mir sofort in den Fingern.
Dieses Mal ist es der Satz von Scherk: de.wikipedia.org/wik...herk_(Zahlentheorie)
Im Artikel wird zwar erklärt, worum es geht, aber leider nicht, wie man algorithmisch eine Lösung findet.

Konkret geht es darum, eine Primzahl als Summe aller vorhergehenden Primzahlen inklusive der 1 darzustellen.
Je nach Parität des Primzahlindex ergeben sich Darstellungen der Form
P6: 13 = 1+2-3-5+7+11
P7: 17 = 1+2-3-5+7-11+2*13 ...
Meine erste Überlegung war, dass man für die z.B. 10000.Primzahl kaum eine Zerlegung findet. Immerhin sind rund 10000 Primzahlen entweder mit Vorzeichen +1 oder -1 zu addieren. Bei 2^10000 theoretischen Möglichkeiten würde mein Rechner etwa 10^3000 Jahre zu tun haben.

Aber es geht schneller. Beginnend ab 1 erhalten alle Primzahlen alternierende Vorzeichen. Die entstehende Summe wird im Allgemeinen nicht die Gesuchte sein, sie ist zu groß!
Dann gibt es zwei Korrekturmöglichkeiten. Erstens werden zwei Vorzeichen - und + so getauscht, dass der Überschuss ausgeglichen wird, wobei das Minus bei der kleineren Primzahl steht.
Gibt es da keine Lösung, so werden jeweils drei Primzahlen, außer der 2, betrachtet. Ist deren vorzeichenbehaftete Summe die Hälfte des Überschusses zur Zielsumme, wird getauscht.

Bis jetzt funktionierte es bei allen Testzahlen. Allerdings habe ich keinen Beweis, dass das immer klappt.
Übrigens dauert es mit 10000 als Startindex immer noch etwas länger, aber keine 10^3000 Jahre.

Wenn es jemanden interessiert, kann er es sich ja einmal ansehen.
Wählt man "nur abweichende Vorzeichen anzeigen", werden nur die Primzahlen ausgegeben, deren Vorzeichen von der ursprünglichen alternierenden Folge abweichen.

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

Horst_H · Verfasst: So 14.09.14 15:01

Hallo,

Mal für n = 1000*1000

markieren

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:

15485863 = ... +3873179 ... +15485857
15485867 = ... +7 -167 +3873367 ... +2*15485863
15485917 = ... +13 -97 +3873299 ... +15485867
15485927 = ... -5 +3873257 ... +2*15485917
15485933 = ... -2 +3873257 ... +15485927
15485941 = ... +3873209 ... +2*15485933
15485959 = ... -5 +3873257 ... +15485941
15485989 = ... -2 +3873257 ... +2*15485959
15485993 = ... +7 -103 +3873343 ... +15485989
15486013 = ... +13 -109 +3873343 ... +2*15485993
15486041 = ... -47 +3873299 ... +15486013
15486047 = ... -23 +3873299 ... +2*15486041
15486059 = ... +7 -67 +3873323 ... +15486047
15486071 = ... +13 -241 +3873491 ... +2*15486059
15486101 = ... +3 -31 +3873299 ... +15486071
15486139 = ... -17 +3873299 ... +2*15486101
15486157 = ... +13 -73 +3873343 ... +15486139
15486173 = ... +7 -83 +3873367 ... +2*15486157
15486181 = ... +7 -59 +3873343 ... +15486173
15486193 = ... +7 -431 +3873713 ... +2*15486181
15486209 = ... +7 -59 +3873343 ... +15486193
15486221 = ... +13 -439 +3873731 ... +2*15486209
15486227 = ... -23 +3873323 ... +15486221
15486241 = ... -23 +3873323 ... +2*15486227
15486257 = ... +7 -31 +3873323 ... +15486241
15486259 = ... +3 -137 +3873437 ... +2*15486257
15486277 = ... -17 +3873323 ... +15486259
15486281 = ... -2 +3873323 ... +2*15486277
15486283 = ... +3873299 ... +15486281
15486287 = ... +3873299 ... +2*15486283
15486347 = ... +3 -31 +3873323 ... +15486287
15486421 = ... -5 +3873323 ... +2*15486347
15486433 = ... -67 +3873427 ... +15486421
15486437 = ... +3 -11 +3873367 ... +2*15486433
15486451 = ... +7 -97 +3873437 ... +15486437
15486469 = ... +3 -11 +3873367 ... +2*15486451
15486481 = ... -5 +3873367 ... +15486469
15486487 = ... +3 -23 +3873379 ... +2*15486481
15486491 = ... +7 -31 +3873391 ... +15486487
15486511 = ... -2 +3873367 ... +2*15486491

Ich habe nicht darauf gewartet, sondern die Suche geändert ;-)

Bei einem Vorzeichenwechsel wird die Summe ja um 2*-Vz*p geändert.
Also muss p >= Abweichung/2.
Bei Änderung zweier Vorzeichen, die Unterschiedlich sind, ändert es sich um 2*Vz2*(p2-p1) | p2>p1)
Da ist noch ein Fehler drin, bei kleinen Zahlen, aber der stört mich jetzt nicht. ;-)

Es wird zu weit gesucht

markieren

Quelltext

1:
2:
3:
4:
5:
6:

Startzeit 00:00:00.655 // von Primzahl nr 4 bis Primzahl Nr 1000004 
31 = ...-7 +17 -29 ... +2*29 AlterSum =-15 delta0 = 6 sum = -26
37 = ...-7 +31 -37 ... +31 AlterSum =14 delta0 = 4 sum = -18
73 = ...-3 +47 -71 ... +2*71 AlterSum =-37 delta0 = 16 sum = -22
431 = ...-13 +331 -421 ... +2*421 AlterSum =-235 delta0 = 88 sum = -30
Laufzeit   00:00:00.584

markieren

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:
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:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:

procedure TForm1.Button1Click(Sender: TObject);
//Anzahl der zu zerlegenden Primzahlen
const
  deltaPrim = 10000;
var summe,AlterSumme,VZ,
    delta0,
    delta1,
    delta2,
    nr,m,
    i,j_alt,j,k,l,
    fehler:integer;
    s:string;
    korrekt:boolean;
    primzahl:array of integer;
    sl : TStringList;
    T1,T0 : TDateTime;

begin
    if not abbruch then
    begin
       abbruch:=true;
       exit;
    end;
    label1.caption := '';
    T0 := Time;
    abbruch:=false;
    button1.caption:='Abbruch';
    memo1.clear;
    sl := TStringList.create;
    //Startnummer der Primzahlen mindestens 2
    nr:=strtoint(edit1.text);
    if nr<=1 then
      nr:=2;
    setlength(primzahl,nr+deltaPrim+3);
    fehler:=0;

    //Primzahlfeld erzeugen
    primzahl[0]:=1;
    primzahl[1]:=2;
    primzahl[2]:=3;
    j:=5;
    k := nr+deltaPrim+2;
    i:=3;
    repeat
      if istprime(j) then begin
        primzahl[i]:=j;
        inc(i);
      end;
      inc(j,2);
    until i> k;

    AlterSumme := 0;
    Vz := +1;
    For i:= 0 to nr-2 do
    begin
      AlterSumme := AlterSumme+Vz*PrimZahl[i];
      Vz := -Vz;
    end;
    T1 := Time;

    sl.Add('Startzeit '+Formatdatetime('HH:NN:SS.ZZZ',T1-T0));
    T0:= time;
    //Schleife für deltaprim Scherk-Zerlegungen
    m:=nr+deltaPrim;
    j_alt := 2;
    repeat
      if odd(nr) then summe:=2*primzahl[nr-1]
                 else summe:=primzahl[nr-1];
      Summe := summe+AlterSumme;
      summe:=summe-primzahl[nr];
      Delta0 := Summe div 2;
      j := -1;
      k := -1;
      l := -1;
      //keine korrekte Darstellung
      if summe<>0 then
      begin
        j:= j_alt;
        korrekt:=false;
        repeat
          IF primzahl[j]>= Delta0 then
          begin
            IF j >= 2 then
              j_alt:= j-2;
            BREAK;
          end;
          inc(j,2);
        until J> nr-2;

        while (Not korrekt) AND (j<= (nr-2)) do
        Begin
          k := -1;
          l := -1;
          delta1 := primzahl[j]-Delta0;
          IF Delta1 = 0 then
          begin
            korrekt:=true;
            break;
          end
          else
          begin
            k := 1;
            l := -1;
            repeat
              IF primzahl[k]>= Delta1 then
                BREAK;
              inc(k,2);
            until k> j;
            delta2 := primzahl[k]-delta1;

            if delta2 = 0 then
            Begin
              korrekt:=true;
              BREAK;
            end
            else
            begin
              l := 2;
              repeat
                IF primzahl[l]>= Delta2 then
                  BREAK;
                inc(l,2);
              until l>k;

              if primzahl[l]= Delta2 then
              begin
                korrekt:=true;
                Break;
              end;
            end;
          end;
          IF NOT Korrekt then
            inc(j,2);
        end;
      end
      else
        korrekt:=true;


      //Ausgabe
      s:=inttostr(primzahl[nr])+' = ...';
      IF l>= 0 then
      begin
       s:=s+'-'+inttostr(primzahl[l])+' ';
       summe := summe-2*primzahl[l];
      end;
      IF k>= 0 then
      begin
       s:=s+'+'+inttostr(primzahl[k])+' ';
       summe := summe+2*primzahl[k];
      end;
      IF j>= 0 then
      begin
       s:=s+'-'+inttostr(primzahl[j])+' ';
       summe := summe-2*primzahl[j];
      end;
//    Zu Testzwecken fuer die Ausgabe der Fehler bis Primzahl 1000004:
{
31 = ...-7 +17 -29 ... +2*29 AlterSum =-15 delta0 = 6 sum = -26
37 = ...-7 +31 -37 ... +31 AlterSum =14 delta0 = 4 sum = -18
73 = ...-3 +47 -71 ... +2*71 AlterSum =-37 delta0 = 16 sum = -22
431 = ...-13 +331 -421 ... +2*421 AlterSum =-235 delta0 = 88 sum = -30
}
//      IF Summe <> 0 then
      begin
        s:=s+'... ';
        if odd(nr) then s:=s+'+2*'+inttostr(primzahl[nr-1])
                   else s:=s+'+'+inttostr(primzahl[nr-1]);

        s := s+' AlterSum ='+IntToStr(AlterSumme);
        s := s+' delta0 = '+IntToStr(delta0)+' sum = '+IntToStr(summe);
        sl.Add(s);
      end;
      AlterSumme := AlterSumme+Vz*PrimZahl[nr-1];
      Vz := -Vz;
      inc(nr);

    until (nr>m) or abbruch;
    T1 := time;
    sl.Add('Laufzeit   '+Formatdatetime('HH:NN:SS.ZZZ',T1-T0));

    application.processmessages;
    if fehler>0 then
      label1.caption:=inttostr(fehler)+' Fehler';
    abbruch:=true;
    button1.caption:='Berechnung';
    setlength(primzahl,0);

    memo1.lines:=sl;
    sl.free;
end;

Man kann noch viel anders machen:
Nun bräuchte man das Feld Vorzeichen nicht mehr.
EDIT: Umgesetzt und ein wenig beschleunigt.
Die Ausgabe in ein Memo könnte man ja noch ändern. ala www.entwickler-ecke....ewtopic.php?t=112237
EDIT2:
Ich habe jetzt die Memoausgabe geändert.
Es wird eine scrollbar benutzt um nur die passenden Zeilen in der Memo anzuzeigen.
Dann sind auch 1 Mio Zeilen kein Problem.

Gruß Horst

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme