Explizite Folgenvorschrift finden (Proth'sche Zahlen)

06.02.2024, 12:54

Malcang

Explizite Folgenvorschrift finden (Proth'sche Zahlen)

Hallo zusammen smile

Es geht, nach wie vor, um die Proth'schen Zahlen.
Kurz nochmal zusammengefasst: Eine Zahl $\begin{eqnarray*} n = h\cdot 2^k +1 \end{eqnarray*}$ mit $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ und $\begin{eqnarray*} h<2^k \end{eqnarray*}$ ungerade heißt Proth'sche Zahl.

Betrachte ich das ganze nun in der Art, dass ich die Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ durchlaufe und pro Exponent alle möglichen $\begin{eqnarray*} h \end{eqnarray*}$ nehme, erhalte ich die Folge
$\begin{eqnarray*} a(1) = 1\cdot 2^1+1 = 3, a(2) = 1\cdot 2^2+1 = 5, a(3) = 3\cdot 2^2+1 = 13... \end{eqnarray*}$ und so weiter.

Nun ist mir aufgefallen, dass ich dies sogar explizit berechnen kann:
$\begin{eqnarray*} a(2^b+c) = (2c+1)\cdot 2^{b+1}+1 \end{eqnarray*}$ für $\begin{eqnarray*} 0\leq c<2^b \end{eqnarray*}$ .

Nun möchte ich gerne beweisen, dass das auch stimmt. Ich dachte an eine Induktion, welche für
$\begin{eqnarray*} a(1) = a(2^0 + 0) = (2\cdot 0+1)\cdot 2^1+1 = 3 \end{eqnarray*}$ ja auch einen funktionierenden Anfang liefert.

Aber wie kann ich hier den Induktionsschritt umsetzen? Oder gibt es eine einfachere Methode?

Vielen Dank an alle Helfer smile

06.02.2024, 13:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Nun ist mir aufgefallen, dass ich dies sogar explizit berechnen kann:
$\begin{eqnarray*} a(2^b+c) = (2c+1)\cdot 2^{b+1}+1 \end{eqnarray*}$ für $\begin{eqnarray*} {\color{red}0\leq b <2^k} \end{eqnarray*}$ .

06.02.2024, 13:27

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Hab's korrigiert. Danke HAL smile

06.02.2024, 13:31

HAL 9000

Auf diesen Beitrag antworten »

Ja, kann man so machen. Ist dann natürlich so, dass diese Folge aller Proth-Zahlen nicht monoton wachsend ist, sondern es bei allen Index-Übergängen $\begin{eqnarray*} 2^b-1 \to 2^b \end{eqnarray*}$ mit $\begin{eqnarray*} b\geq 2 \end{eqnarray*}$ mal kurz und steil nach unten geht.

Die monotone Auflistung ist etwas komplizierter, aber dazu hatten wir damals ja schon ausgiebige Gefechte, wenn ich mich richtig erinnere...

06.02.2024, 14:02

Malcang

Auf diesen Beitrag antworten »

Das ist korrekt, und das damalige Gefecht hat mir auch sehr geholfen smile

Aber für diese folge hier würde ich das gerne auch beweisen. Aber ich sehe noch nicht den zielführenden Ansatz.
Klar, ich kann jede Zahl eindeutig durch $\begin{eqnarray*} 2^b + c \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq c < 2^b \end{eqnarray*}$ darstellen.

Hmmm.... Aber wie weiter?

06.02.2024, 14:08

HAL 9000

Auf diesen Beitrag antworten »

Zu festem $\begin{eqnarray*} k \end{eqnarray*}$ gibt es genau $\begin{eqnarray*} 2^{k-1} \end{eqnarray*}$ ungerade positive $\begin{eqnarray*} h<2^k \end{eqnarray*}$ .

D.h., hintereinander angeordnet gibt es dann genau $\begin{eqnarray*} 2^0+2^1+\ldots+2^b=2^{b+1}-1 \end{eqnarray*}$ Proth'sche Zahlen mit einem $\begin{eqnarray*} k\leq b+1 \end{eqnarray*}$ , wobei der Fall $\begin{eqnarray*} k=b+1 \end{eqnarray*}$ dann die Indizes $\begin{eqnarray*} 2^b \end{eqnarray*}$ bis $\begin{eqnarray*} 2^{b+1}-1 \end{eqnarray*}$ umfasst, also eben jene $\begin{eqnarray*} i=2^b+c \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq c<2^b \end{eqnarray*}$ sowie mittels $\begin{eqnarray*} h=2c+1 \end{eqnarray*}$ zugehöriger Proth'scher Zahl $\begin{eqnarray*} (2c+1)\cdot 2^{b+1}+1 \end{eqnarray*}$ .

Mir würde das als formloser Beweis genügen. Kannst du natürlich noch in irgendeine Art Induktion packen, wenn dir dabei wohler ist.

06.02.2024, 17:03

Malcang

Auf diesen Beitrag antworten »

Erstmal: Vielen Dank HAL, das hat mir für mein Verständnis schonmal sehr weitergeholfen! Freude

Nun geht es für mich noch darum, dass ganze in einen Beweis zu packen, den ich in meiner Masterarbeit anführen kann. Daher dachte ich an eine Induktion, weil sie sich ja sehr sauber aufschreiben lässt. Ich bin wie ihr wisst sehr penibel Big Laugh

Ich hatte mir überlegt, dass man die Proth'schen Zahlen ja in einer Tabelle betrachten kann. Die Zeilen entsprechen dem Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ , die Spalten dem Koeffizienten $\begin{eqnarray*} h \end{eqnarray*}$ .

[attach]57528[/attach]

In Zeile $\begin{eqnarray*} k \end{eqnarray*}$ gibt es demnach genau $\begin{eqnarray*} 2^{k-1} \end{eqnarray*}$ Einträge.
Damit gibt es in den ersten $\begin{eqnarray*} m \end{eqnarray*}$ Zeilen ingesamt genau $\begin{eqnarray*} 2^{m}-1 \end{eqnarray*}$ Einträge.
Daher finden sich die Einträge $\begin{eqnarray*} a(2^b) = 2^b+1 \end{eqnarray*}$ genau in der ersten Spalte der $\begin{eqnarray*} b- \end{eqnarray*}$ ten Zeile.
Sei nun $\begin{eqnarray*} l \end{eqnarray*}$ ein beliebiger Index. Dann existieren eindeutige $\begin{eqnarray*} b, c \end{eqnarray*}$ mit $\begin{eqnarray*} l = 2^b+c, 0\leq c<2^b. \end{eqnarray*}$
Dann findet sich $\begin{eqnarray*} a(l) \end{eqnarray*}$ in der $\begin{eqnarray*} b- \end{eqnarray*}$ ten Zeile und der $\begin{eqnarray*} (c+1)- \end{eqnarray*}$ ten Spalte.
Demnach ist der Koeffizient dort die $\begin{eqnarray*} (c+1)- \end{eqnarray*}$ te ungerade Zahl, also $\begin{eqnarray*} h = 2c+1 \end{eqnarray*}$ .

Ist das so für eine Masterarbeit ok? Oder lässt das zuviel "Spielraum"? Ich müsste ja auch die Tabelle mit Pünktchen fortführen....

10.02.2024, 13:41

Malcang

Auf diesen Beitrag antworten »

Hallo nochmal HAL, und natürlich Hallo an Alle smile

ich habe mich nochmal obigem Beweis beschäftigt und würde ihn euch gerne zeigen.
Mir ist an sich völlig klar, wie der Beweis funktioniert. Mein Problem ist hierbei, es formal sauber aufzuschreiben. So, dass sogar Edmund Landau sagen würde, er genügt den Anforderungen Big Laugh

(wenn das überhaupt möglich ist).
Hier ist mein Beweis smile

[attach]57544[/attach]

20.02.2024, 09:13

HAL 9000

Auf diesen Beitrag antworten »

Hatte das aus den Augen verloren... zwei Anmerkungen:

1) In der Lemma-Formulierung sollte $\begin{eqnarray*} 0\leq c\leq 2^k-1 \end{eqnarray*}$ stehen statt $\begin{eqnarray*} 0\leq c\leq 2^{k+1}-1 \end{eqnarray*}$ . Du bist mit dem Exponent vermutlich durcheinandergekommen wegen $\begin{eqnarray*} 0 < h\leq 2^{k+1}-1 \end{eqnarray*}$ für die zugeordnete ungerade Zahl $\begin{eqnarray*} h=2c+1 \end{eqnarray*}$ .

2) Im Beweis sollte dazu passend die $\begin{eqnarray*} k \end{eqnarray*}$ -Spalte bei 0 statt bei 1 beginnen:

k=0 zugehörig Index i=1
k=1 zugehörig Indizes i=2,3
k=2 zugehörig Indizes i=4,5,6,7 usw.

Zu festem $\begin{eqnarray*} k \end{eqnarray*}$ gibt es dann genau $\begin{eqnarray*} 2^k \end{eqnarray*}$ Indizes $\begin{eqnarray*} i \end{eqnarray*}$ .

Neue Frage »

Antworten »

Explizite Folgenvorschrift finden (Proth'sche Zahlen)

Verwandte Themen