Höchste Primzahl ermitteln

Question

Ich habe 6 natürliche Zahlen, sagen wir 913,407,395,86,203,296
Anhand welcher Formel finde ich heraus, welche Kombination (Addition) die höchstmögliche Primzahl ergibt?

Comments

Jetzt bin ich selbst auf die Lösung gekommen :-). Hat sich erledigt!

---

Wie lautet die Formel?

---

Hast du die Lösung anders als durch einfaches Probieren gefunden ?

---

Ich habe es durch Probieren und mit Hilfe eines Primzahlrechners versucht

913+407+401+395+296+203+86 = 2701 = 37*73
913+407+401+395+296+203 = 2615 = 5*523

913+407+401+395+296+86 = 2498 = 2 · 1249

913+407+401+395+296 = 2319 = 3*773

913+407+401+395+203 = 2319 = 3 · 773

913+407+401+395+86 = 2202 = 2 · 3 · 367

913+407+401+395 = 2023 = 7*17*17
913+407+401+296 = 2017 = Primzahl. (Sie ist nur durch 1 und sich selbst teilbar)

---

Es soll 127 Kombinationen der 6 Zahlen geben. Aber dafür muß es doch eine Formel geben, oder?

---

Es soll 127 Additionsmöglichkeiten der 6 Zahlen. Hat jemand eine Lösung?

---

oben stehen 6 Zahlen, unten sieben. Was denn nun?

---

Man kann doch sicher gleich die Möglichkeiten ausschließen, die als Summe eine gerade Zahl ergeben.

203, 395, 407, 913
86, 296

((4 über 1) + (4 über 3))·2^2 = 32

Damit kann man die Möglichkeiten schon auf 32 reduzieren. Das lässt sich dann auch schneller durchprobieren.

---

127 Kombinationsmöglichkeiten wäre für sieben Summanden, nämlich \( \sum\limits_{k=1}^{7} \begin{pmatrix} 7\\k \end{pmatrix} \) wobei jeder Summand höchstens einmal vorkommt. Bei sechs Summanden sind es 63 Möglichkeiten. Diese reduzieren sich aber weiter, weil man um eine Primzahl zu bekommen eine ungerade Summe haben muss.

Answer 1

Eine n-elementige Menge hat  2ⁿ Teilmengen.

Dazu zählt aber auch die leere Menge (Menge mit 0 Elementen). Da die Summen aus wenigstens einem Element bestehen müssen, muss man diese Möglichkeit wegnehmen und damit gibt es 2ⁿ -1 zu testende Summen.