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
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein