Mittlere Anzahl der Alternativfragen und Primzahlen

Neue Frage »

Zeno-2 Auf diesen Beitrag antworten »
Mittlere Anzahl der Alternativfragen und Primzahlen
Das Nachfolgende interessiert mich rein aus Neugier.

Angenommen man soll eine ganze Zahl kleiner erraten, wobei nur Ja/Nein-Fragen erlaubt sind. Der beste Weg ist es, den Wertebereich in jedem Schritt zu halbieren.

Beispiel: und man fragt:

1) Ist die Zahl kleiner 50? --> Nein
2) Ist die Zahl kleiner 75? --> Ja
3) Ist die Zahl kleiner 62,5? --> Nein
4) Ist die Zahl kleiner 68,75? --> Ja
5) Ist die Zahl kleiner 65,625 ? --> Nein
6) Ist die Zahl kleiner 67,0625? --> Nein -> die Zahl ist 68.

Im Schnitt benötigt man so Ja/Nein -Fragen.

Okay. Angenommen man darf die Zahl nur über die Frage nach ihren Primzahlteilern bestimmen, also eigentlich eine Primfaktorzerlegung. Für das Beispiel:

1) Ist die Zahl durch 2 teilbar? --> Ja.
2) Ist die Zahl noch einmal durch 2 teilbar? --> Ja.
3) ist die Zahl noch einmal durch 2 teilbar? -> Nein.
4) Ist die Zahl durch 3 teilbar? --> Nein
5) Ist die Zahl durch 5 teilbar? --> Nein.
6) Ist die Zahl durch 7 teilbar? --> Nein.
7) Ist die Zahl durch 11 teilbar? --> Nein.
8) Ist die Zahl durch 13 teilbar? --> Nein.
9) Ist die Zahl durch 17 teilbar? --> Ja. --> Die Zahl ist 2×2×17 =68, denn jeder weitere Primfaktor würde zu einer zahl > N führen.

Man braucht offenbar deutlich mehr Alternativfragen. Wieviele sind es im Mittel?

Wenn ich es richtig verstanden habe benötigt man zur Bestimmung von alternativen Ereignissen wenn diese mit der Wahrscheinlichkeit auftreten



Alternativfragen. Eine beliebige ganze Zahl lässt sich durch eine Primzahl mit der Wahrscheinlichkeit teilen. Man müsste also in die Entropieformel alle Wahrscheinlichkeiten p_i der Primzahlen 2, 3, 5, 7... <= N eingeben und ausrechnen...aber das ist die Obergrenze. .

Oder...?

(Und nun muss ich aufhören, da der Saft auf dem Tablet alle ist)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »