Mathematiker - Fr 12.09.14 15:59
Titel: Scherk-Zerlegungen
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:
http://de.wikipedia.org/wiki/Satz_von_Scherk_(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
Horst_H - So 14.09.14 14:01
Hallo,
Mal für n = 1000*1000
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
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 |
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);
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;
nr:=strtoint(edit1.text);
if nr<=1 then
nr:=2;
setlength(primzahl,nr+deltaPrim+3);
fehler:=0;
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;
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;
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;
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;
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
http://www.entwickler-ecke.de/viewtopic.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