Anzahl der Proth'schen Zahlen

25.09.2023, 17:42

Malcang

Anzahl der Proth'schen Zahlen

Hallo zusammen, da bin ich nochmal Augenzwinkern

ich schaue mir ja aktuell die Proth'schen Zahlen an. Dies sind Zahlen $\begin{eqnarray*} n \end{eqnarray*}$ der Bauform $\begin{eqnarray*} n= h\cdot 2^k + 1 \end{eqnarray*}$ , wobei $\begin{eqnarray*} h<2^k \end{eqnarray*}$ ungerade ist.
Nun möchte ich wissen, wieviele solcher Zahlen es bis zu einer gegebenen Grenze $\begin{eqnarray*} l \end{eqnarray*}$ gibt.
Dazu habe ich auch etwas erarbeitet und wollte euch fragen, ob ich das etwas vereinfachter hinbekomme.

Notwendigerweise ist $\begin{eqnarray*} h\leq \operatorname{ld}(l) \end{eqnarray*}$ , wobei $\begin{eqnarray*} \operatorname{ld} \end{eqnarray*}$ hier der duale Logarithmus ist,
Sei nun $\begin{eqnarray*} k \end{eqnarray*}$ fest. Dann muss $\begin{eqnarray*} h\leq \frac{l-1}{2^k} \end{eqnarray*}$ gelten. Da der Ausdruck rechts in der Regel nicht ganzzahlig ist, müssen wir abrunden. Also $\begin{eqnarray*} h\leq \big\lfloor\frac{l-1}{2^k}\big\rfloor \end{eqnarray*}$ .
Nun suchen wir ja nur die ungeraden $\begin{eqnarray*} h \end{eqnarray*}$ , also bilden wir $\begin{eqnarray*} \frac{1}{2}\cdot\big\lfloor\frac{l-1}{2^k}\big\rfloor \end{eqnarray*}$ und runden auf. Denn wenn $\begin{eqnarray*} \big\lfloor\frac{l-1}{2^k}\big\rfloor \end{eqnarray*}$ ungerade ist, muss ich ja diese Zahl selbst und die $\begin{eqnarray*} 1 \end{eqnarray*}$ mitzählen.

Nun muss aber ja noch $\begin{eqnarray*} h<2^k \end{eqnarray*}$ bedacht werden. Die Anzahl der ungeraden Zahlen zwischen $\begin{eqnarray*} 1 \end{eqnarray*}$ und $\begin{eqnarray*} 2^k \end{eqnarray*}$ beträgt $\begin{eqnarray*} 2^{k-1} \end{eqnarray*}$ .

Für meine Fragestellung heißt das:
Die Anzahl der möglichen $\begin{eqnarray*} h \end{eqnarray*}$ bei fixem $\begin{eqnarray*} k \end{eqnarray*}$ beträgt $\begin{eqnarray*} \min\{\big\lceil \frac{1}{2}\cdot \big\lfloor\frac{l-1}{2^k}\big\rfloor\big\rceil, 2^{k-1}\} \end{eqnarray*}$ .

Wenn ich nun die Anzahl der Proth'schen Zahlen bis $\begin{eqnarray*} l \end{eqnarray*}$ berechnen möchte, muss ich also die für alle möglichen $\begin{eqnarray*} k \end{eqnarray*}$ finden und summieren.
Dabei sind sogar alle natürlichen Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ möglich, da für $\begin{eqnarray*} k>\operatorname{ld}(l-1) \end{eqnarray*}$ ohnehin Null rauskommt.

Die Anzahl bei Grenze $\begin{eqnarray*} l \end{eqnarray*}$ beträgt also $\begin{eqnarray*} \sum\limits_{k=1}^{\infty}\min\{\big\lceil \frac{1}{2}\cdot \big\lfloor\frac{l-1}{2^k}\big\rfloor\big\rceil, 2^{k-1}\} \end{eqnarray*}$ .

Dies scheint auch zu stimmen, jedenfalls habe ich das mit python mal überprüft, indem ich die Proth'schen Zahlen einfach erstellt und gezählt habe. Die Ergebnisse stimmen überein.

Jetzt hab ich mich gefragt, ob man diese Formel vielleicht etwas handhabbarer hinbekommt? Sehr elegegant sieht sie ja leider nicht aus.

26.09.2023, 07:27

IfindU

Anzahl der Proth'schen Zahlen

Verwandte Themen