Mit Hilfe eines Zufallsgenerators soll eine Primzahl mit etwa 500 Stellen im Binärsystem gefunden werden. Dabei wird folgendermaßen vorgegangen: Das letzte Bit wird auf 1 gesetzt, damit nur ungerade Zahlen entstehen. Die anderen 499 Bits werden mit einem Zufallsgenerator erzeugt, der Nullen und Einsen zufällig und mit gleicher Wahrscheinlichkeit produziert. (Führende Nullen sind erlaubt.)

Wir setzen (entsprechend dem Primzahlsatz) voraus, dass die Anzahl ´pi(n)´ der Primzahlen ´<= n´ ungefähr gleich ´n/ln(n)´ ist. (Die Primzahl 2 können wir dabei vernachlässigen.)

  1. Wie hoch ist dann (ungefähr) die Wahrscheinlichkeit p, dass die so erzeugte Zahl eine Primzahl ist?
  2. Wie viele solche Zahlen müssen erzeugt werden, damit mit einer Wahrscheinlichkeit von ´>= 0.99´ mindestens eine Primzahl dabei ist?
Approach

Teil 1

´(2^500/ln(2^500))/2^499 = (2^500/(500 ln(2)))/2^499 = 2^500/(2^499 * 500 ln(2)) =´ ´1/(250 ln(2)) ~ 0.005771 ~ 0.5771%´

Teil 2

´(1 - 0.005771)^n < 0.01´ ´0.99423^n < 0.01 | ln´ ´ln(0.99423^n) < ln(0.01)´ ´n ln(0.99423) < ln(0.01)´ ´| :ln(0.99423)´ ´n > ln(0.01)/ln(0.99423)´ ´n > 795.7104´ ´n = 796´

Answer: At least 796 such numbers have to be generated.


Solution
    1. ´~~ 0.5771%´
    2. ´n = 796´
  • URL:
  • Language:
  • Subjects: math stochastics
  • Type: Calculate
  • Duration: 25min
  • Credits: 3
  • Difficulty: 0.4
  • Tags: hpi probability
  • Note:
    HPI, 2014-04-14, Mathe 2, Aufgabe 5
  • Created By: adius
  • Created At:
    2014-07-25 20:41:50 UTC
  • Last Modified:
    2014-07-25 20:41:50 UTC