Beweis für "simple" Formel gesucht

30.06.2024, 18:14

Telefonmann1

Beweis für "simple" Formel gesucht

Hallo zusammen, ich bin beim "Rumrechnen" neulich zu der folgenden Aufgabe, bzw. Fragestellung gelangt:

Sind die Zahlen der folgenden Reihe alle durch 27 teilbar?

$\begin{eqnarray*} z_m = 2^m + 1 \end{eqnarray*}$
mit
$\begin{eqnarray*} m = 3^k \end{eqnarray*}$
und k>=2 also k=2,3,4,5,6,7, ....

Man kann die Behauptung für k=2,3,4 numerisch noch relativ leicht überprüfen und mit Hilfe der geometrischen Reihe auch zeigen, dass z_m für jedes ungerade m durch 3 teilbar ist, aber damit bin ich dann auch schon fertig.

Hat jemand weitereführende Ideen?

30.06.2024, 18:49

Elvis

Auf diesen Beitrag antworten »

Induktionsanfang stimmt für $\begin{eqnarray*} k=2 \end{eqnarray*}$

Für den Induktionsschritt von k auf k+1 genügt $\begin{eqnarray*} 2^{3^{k+1}}+1 =(2^{3^k}+1)\cdot (2^{2\cdot 3^k}-2^{3^k}+1) \end{eqnarray*}$ , denn nach Induktionsvoraussetzung ist der erste Faktor durch 27 teilbar, und der zweite Faktor in $\begin{eqnarray*} \mathbb N \end{eqnarray*}$

(Ich habe geschummelt und mir helfen lassen : https://www.wolframalpha.com/input?i=2%5...3%5Ek%29%2B1%29 )

30.06.2024, 19:16

Telefonmann1

Auf diesen Beitrag antworten »

Cool. THX

30.06.2024, 21:12

HAL 9000

Auf diesen Beitrag antworten »

Man kann hier per Vollständiger Induktion sogar noch deutlich mehr nachweisen:

$\begin{eqnarray*} 2^{3^k}+1 \end{eqnarray*}$ ist durch $\begin{eqnarray*} 3^{k+1} \end{eqnarray*}$ , aber nicht durch $\begin{eqnarray*} 3^{k+2} \end{eqnarray*}$ teilbar - gültig für alle $\begin{eqnarray*} k\in \mathbb{N}_0 \end{eqnarray*}$ .

30.06.2024, 22:44

Telefonmann1

Auf diesen Beitrag antworten »

Die Formel entstammt dem Collatz-Problem:

Zahlen der Folge 8n+7 werden nach drei T-Iterationen auf die Zahlen der Folge 27n+26 abgebildet und da kann man sich dann fragen, für welches n das eine Zweierpotenz ist. Das erste n auf welches das zutrifft ist die 18, usw.

01.07.2024, 08:32

HAL 9000

Auf diesen Beitrag antworten »

Ach je, der Collatz. Denk an die Warnung "Don’t try to solve these problems!" des Mathematikers Richard Guy. Augenzwinkern

Zitat:

Original von Telefonmann1
Zahlen der Folge 8n+7 werden nach drei T-Iterationen auf die Zahlen der Folge 27n+26 abgebildet und da kann man sich dann fragen, für welches n das eine Zweierpotenz ist.

Oder gleich allgemeiner mit der von mir oben genannten Aussage:

Zahlen der Form $\begin{eqnarray*} 2^m\cdot n-1 \end{eqnarray*}$ werden nach $\begin{eqnarray*} m \end{eqnarray*}$ T-Iterationen zu $\begin{eqnarray*} 3^m\cdot n-1 \end{eqnarray*}$ , was bei Wahl von $\begin{eqnarray*} n = \frac{2^{3^{m-1}}+1}{3^m} \end{eqnarray*}$ eine Zweierprotenz darstellt.

Beispielsweise für $\begin{eqnarray*} m=4 \end{eqnarray*}$ ist $\begin{eqnarray*} n=1\,657\,009 \end{eqnarray*}$ und die Ausgangszahl vor den 4 T-Iterationen ist dann $\begin{eqnarray*} 2^m\cdot n-1 = 26\,512\,143 \end{eqnarray*}$ .

01.07.2024, 09:32

Telefonmann1

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ach je, der Collatz. Denk an die Warnung ... "Don’t try to solve these problems!" des Mathematikers Richard Guy. Augenzwinkern

Ja. Herrlich "sinnlos" Big Laugh

Zitat:

.... Beispielsweise für $\begin{eqnarray*} m=4 \end{eqnarray*}$ ist $\begin{eqnarray*} n=1\,657\,009 \end{eqnarray*}$ und die Ausgangszahl vor den 4 T-Iterationen ist dann $\begin{eqnarray*} 2^m\cdot n-1 = 26\,512\,143 \end{eqnarray*}$ .

Sehr interessant und durchaus "würdig" für den zugehörigen Wikipedia-Artikel zum Collatz-Problem. Ich denke, ich würde das ganz gerne bei Gelegenheit einbauen, da die Formel für m=2 eh von mir stammt und das eine geeignete Verallgemeinerung ist. Soll ich da einen Link auf dieses Thema einbauen? Leicht "flüchtige" Forenthemen machen sich als Referenz dort zumeist nicht so gut.

01.07.2024, 10:07

Telefonmann1

Auf diesen Beitrag antworten »

Zitat:

Original von Telefonmann1
Ich denke, ich würde das ganz gerne bei Gelegenheit einbauen, da die Formel für m=2 eh von mir stammt und das eine geeignete Verallgemeinerung ist.

Ich sehe gerade, dass die vorgeschlagene Formel im Beitrag #6 nur ein n für jedes m liefert. Die bereits vorhandene Formel im Wikipediaartikel liefert für m=2 aber unendlich viele n (, die dann auf eine Zweierpotenz führen). Die ersten drei Beiträge im Thema hier zeigen, dass es auch für m=3 unendlich viele n gibt, die auf eine Zweierpotenz führen.

Mal sehen ...

01.07.2024, 10:32

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Telefonmann1
Ich sehe gerade, dass die vorgeschlagene Formel im Beitrag #6 nur ein n für jedes m liefert. Die bereits vorhandene Formel im Wikipediaartikel liefert für m=2 aber unendlich viele n (, die dann auf eine Zweierpotenz führen).

Das ist richtig, es liefert genau einen Startwert für $\begin{eqnarray*} m \end{eqnarray*}$ T-Iterationen bis zu einer Zweierpotenzen. Aber das ist keine wirkliche Einschränkung in dem von dir gerade genannten Sinne:

Wenn du unendlich viele Startwerte suchst mit genau $\begin{eqnarray*} m \end{eqnarray*}$ T-Iterationen bis zu einer Zweierpotenz suchst, dann kannst du ja einfach alle $\begin{eqnarray*} m'\geq m \end{eqnarray*}$ nehmen, die obigen von mir genannten Startwerte nehmen und dann jeweils $\begin{eqnarray*} (m'-m) \end{eqnarray*}$ T-Iterationen durchführen, dann hast du jeweils genau wieder solche passenden Werte.

Beispielsweise hat oben Startwert $\begin{eqnarray*} \frac{3\cdot 26\,512\,143 + 1}{2} = 39\,768\,215 \end{eqnarray*}$ (d.h. nach $\begin{eqnarray*} 4-3=1 \end{eqnarray*}$ Iteration) auch die Eigenschaft, nach genau 3 T-Iterationen auf eine Zweierpotenz zu führen, genau wie Startwert 303.

01.07.2024, 13:33

Telefonmann1

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Beispielsweise hat oben Startwert $\begin{eqnarray*} \frac{3\cdot 26\,512\,143 + 1}{2} = 39\,768\,215 \end{eqnarray*}$ (d.h. nach $\begin{eqnarray*} 4-3=1 \end{eqnarray*}$ Iteration) auch die Eigenschaft, nach genau 3 T-Iterationen auf eine Zweierpotenz zu führen, genau wie Startwert 303.

Ja, Danke. Gutes Beispiel mit weiteren Möglichkeiten, weil die Zahl $\begin{eqnarray*} 39\,768\,215 \end{eqnarray*}$ zusätzlich auch nach 4, 5, 6, bis ? T-Iterationen auf eine Zweierpotenz führt.

09.07.2024, 10:25

Telefonmann1

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Man kann hier per Vollständiger Induktion sogar noch deutlich mehr nachweisen:

$\begin{eqnarray*} 2^{3^k}+1 \end{eqnarray*}$ ist durch $\begin{eqnarray*} 3^{k+1} \end{eqnarray*}$ , aber nicht durch $\begin{eqnarray*} 3^{k+2} \end{eqnarray*}$ teilbar - gültig für alle $\begin{eqnarray*} k\in \mathbb{N}_0 \end{eqnarray*}$ .

Ich habe per Taschenrechner und Rumprobieren noch etwas allgemeinere Eigenschaften gefunden:

$\begin{eqnarray*} 3^{k+1} \end{eqnarray*}$ teilt $\begin{eqnarray*} 2^{2m3^k}-1 \end{eqnarray*}$
$\begin{eqnarray*} 3^{k+1} \end{eqnarray*}$ teilt $\begin{eqnarray*} 2^{(2m+1)3^k}+1 \end{eqnarray*}$
für alle $\begin{eqnarray*} k,m\in \mathbb{N}_0 \end{eqnarray*}$

Der von Elvis benutzte Beweis oben lässt sich allerdings nicht trivial auf diese Formeln ausweiten. Hat jemand Ideen dazu?

09.07.2024, 12:50

HAL 9000

Auf diesen Beitrag antworten »

Das ist eine einfache Folgerung, denn es gilt ja gemäß Geometrischer Partialsummenformel

$\begin{eqnarray*} a^{2m} - 1 = (a+1)(a-1)\sum_{k=0}^{m-1} a^{2k} \end{eqnarray*}$ und $\begin{eqnarray*} a^{2m+1} + 1 = (a+1)\sum_{k=0}^{2m} (-a)^k \end{eqnarray*}$ ,

speziell auch für $\begin{eqnarray*} a = 2^{3^k} \end{eqnarray*}$ .

09.07.2024, 14:13

Telefonmann1

Auf diesen Beitrag antworten »

THX

Neue Frage »

Antworten »

Beweis für "simple" Formel gesucht

Verwandte Themen