[RUBY] Ob das Gesamtprodukt der ersten n Primzahlen plus 1 eine Primzahl ist

Im antiken Griechenland war bereits bekannt, dass es unendlich viele Primzahlen gibt. Der folgende Beweis ist in " Principles Stoikeia </ ruby>" geschrieben, das in BC zusammengestellt wurde.

Angenommen, Sie haben nur drei Primzahlen. Dies sei $ p $, $ q $, $ r $. Wenn $ pqr + 1 $ durch $ p $, $ q $ oder $ r $ geteilt wird, bleibt $ 1 $ übrig. Dies verstößt gegen die Annahme, dass die Primzahlen nur $ p $, $ q $, $ r $ sind. (Diese Argumentation ist dieselbe, unabhängig davon, ob es 4 oder 5 Primzahlen gibt. Das heißt, die Annahme einer endlichen Anzahl von Primzahlen führt immer zu einem Widerspruch.)

Es verwendet die Absurditätsmethode (eine Argumentation, die einen Widerspruch aus der Annahme A ableitet und die Ablehnung von A beweist). Als ich diesen Beweis in der Junior High School traf, war ich ein wenig bewegt. Die Absurditätsmethode war cool, und ich fand es wunderbar, den Widerspruch aus der einfachen Formel "Gesamtprodukt aller Primzahlen plus 1" zu ziehen.

Etwa zur gleichen Zeit erfuhr ich, dass es ein Thema gab: "Suche nach großen Primzahlen". Mit dem Fortschritt der elektronischen Computer sah ich, dass riesige Primzahlen, die durch manuelle Berechnung niemals gefunden werden konnten, nacheinander gefunden wurden, und es wurde eine Liste erstellt, z. B. wer welche Primzahl in welchem Jahr gefunden hat. ..

Ein Amateur wie ich erinnert sich an den Beweis der "ursprünglichen Theorie" und kommt auf so etwas Falsches.

Sie können leicht eine große Primzahl erhalten, indem Sie alle gefundenen Primzahlen multiplizieren und 1 addieren!

Natürlich nicht. Die Annahme, dass die Zahl endlich ist, hat nur dazu geführt, dass das Gesamtprodukt plus 1 durch keines teilbar ist. In Wirklichkeit gibt es unendlich viele Primzahlen, und nur weil eine endliche Anzahl von Primzahlen herausgenommen, multipliziert und zu 1 addiert wird, heißt das nicht, dass es sich um Primzahlen handelt.

Aber ist es? Die Summe von $ n $ Primzahlen plus eins ist nicht durch mindestens diese Primzahlen teilbar. In gewissem Sinne kann daher gesagt werden, dass es sich um eine „schwer zu teilende Zahl“ handelt. Gibt es nicht einige Primzahlen?

In Anbetracht des Siebs Siebs </ ruby> von Eratostenes scheint es effizient zu sein, Vielfache kleiner Primzahlen zu eliminieren, um synthetische Zahlen zu eliminieren.

Daher scheint es besser, die Primzahlen in aufsteigender Reihenfolge zu sortieren, die ersten $ n $ Stücke zu nehmen und 1 zu ihrem Gesamtprodukt hinzuzufügen.

Nehmen wir zuerst die erste Primzahl $ 2 $. $ 3 $, die Summe aus diesem und $ 1 $, ist eine Primzahl.

Nächster. $ 2 \ cdot3 + 1 = 7 $ ist eine Primzahl. Wie schön.

$ 2 \ cdot3 \ cdot5 + 1 = 31 $ ist ebenfalls eine Primzahl. Nun, es ist in gutem Zustand.

Wie wäre es mit $ 2 \ cdot3 \ cdot5 \ cdot7 + 1 = 211 $? Es ist leicht zu erkennen, dass weder $ 11 $ noch $ 13 $ teilbar sind. $ 17 ^ 2 $ überschreitet $ 211 $, sodass Sie es nicht versuchen müssen. Es stellte sich heraus, dass es sich um eine Primzahl handelte. Hmmm, ist die Geschichte nicht zu gut? Bisher habe ich mein Bestes von Hand berechnet.

Wie wäre es mit $ 2 \ cdot3 \ cdot5 \ cdot7 \ cdot11 + 1 = 2311 $? Ich habe die manuelle Berechnung aufgegeben. Es ist nicht so schwierig, aber ich bin nicht sicher, dass ich bei der Berechnung keinen Fehler machen werde.

Hier zum Terminal

irb -r prime

Schlagen. Dadurch wird die interaktive Ruby-Umgebung gestartet und die Primzahlbibliothek "prime" geladen.

Und

irb(main):001:0> 2311.prime?
=> true

Oh, ist das auch eine Primzahl! (Sie können überprüfen, ob eine Ganzzahl eine Primzahl bei [Integer # prime?] Ist (Https://docs.ruby-lang.org/ja/2.7.0/method/Integer/i/prime=3f.html))

Ich hätte nie gedacht, dass nur Primzahlen so gut herauskommen würden.

Lassen Sie es uns systematisch im Programm untersuchen. Schreiben Sie wie folgt in Ruby.

require "prime"

1.step do |n|
  m = Prime.take(n).inject(:*) + 1
  puts "%3d %s %d" % [n, (m.prime? ? "o" : "x"), m]
end

Dieses Programm ist nicht zum Stoppen geschrieben. Formal sucht es unbegrenzt weiter.

Prime.take (n) gibt das erste n Array von Primzahlen an.

Sie können das Gesamtprodukt mit injizieren (: *) erhalten.

Und

Wert von n
Ob es sich um eine Primzahl handelt (o wenn es sich um eine Primzahl handelt, x wenn nicht)
Wert von "Gesamtprodukt plus 1"

Einfach anzeigen und nebeneinander.

Die Ergebnisse waren wie folgt.

  1 o 3
  2 o 7
  3 o 31
  4 o 211
  5 o 2311
  6 x 30031
  7 x 510511
  8 x 9699691
  9 x 223092871
 10 x 6469693231
 11 o 200560490131
 12 x 7420738134811
 13 x 304250263527211
 14 x 13082761331670031
 15 x 614889782588491411
 16 x 32589158477190044731
 17 x 1922760350154212639071
 18 x 117288381359406970983271

Es geht bis zu $ n = 18 $ am Stück, aber es geht nicht für immer weiter.

Bis zu $ n = 5 $ war es eine Primzahl, danach folgt eine zusammengesetzte Zahl. Hmmm sorry.

Wenn ich denke, dass die Primzahl endlich bei $ n = 11 $ erscheint, wird die zusammengesetzte Zahl wieder fortgesetzt.

War es eine Illusion, dass ich dachte: "Ich denke, dass Primzahlen in einem angemessenen Verhältnis enthalten sind?"