Generatorfunktion für Folge

Neue Frage »

28.04.2018, 11:55	Hosenschlange	Auf diesen Beitrag antworten »
Generatorfunktion für Folge Gegeben ist: $\begin{eqnarray} a_{1} = 3 \end{eqnarray}$ $\begin{eqnarray} a_{n+1} = 7a_{n}^{3} + 9a_{n} + 2 \end{eqnarray}$ Die ersten Werte sind 1 -> 3 2 -> 218 3 -> 72523588 4 -> 2670151395126345402146598 5 -> 133261807180216122475451470147325279314162931058284183854771966989826113728 Gesucht sind die letzten 10 Stellen von $\begin{eqnarray} a_{q} \end{eqnarray}$ , wobei $\begin{eqnarray} q=3^{41} \end{eqnarray}$ . Bei Betrachtung von q weiß ich, dass es keinen Sinn macht alles der Reihe nach auszurechnen. Ich dachte also eher daran, eine Art Generatorfunktion(änhlich wie bei Dreieckszahlen) zu basteln. Bin damit aber auch nicht weitergekommen. Ist das übehaupt der richtige Ansatz? Oder gäbe es einen besseren? Danke für die Hilfe
28.04.2018, 13:58	HAL 9000	Auf diesen Beitrag antworten »
$\begin{eqnarray} 9\,004\,963\,588 \end{eqnarray}$
28.04.2018, 14:11	Hosenschlange	Auf diesen Beitrag antworten »
@HAL9000 Ich weiß es leider nicht. Ich hab auch noch keine Idee, um $\begin{eqnarray} a_{n} \end{eqnarray}$ direkt zu berechnen. Könntest du sagen, wie du auf diesen Wert gekommen bist?
28.04.2018, 14:17	HAL 9000	Auf diesen Beitrag antworten »
Eine Bruteforcelösung mit ein paar wenigen, groben Vereinfachungen zur Reduzierung des Rechenaufwands: Offenkundig reicht es $\begin{eqnarray} b_n = a_n\bmod 10^{10} \end{eqnarray}$ zu betrachten. Dann ist auch $\begin{eqnarray} b_{n+1} = (7b_n^3+9b_n+2)\bmod 10^{10} \end{eqnarray}$ . Nun stellt sich heraus, dass Folge $\begin{eqnarray} (b_n) \end{eqnarray}$ ab Index 2 periodisch ist, genauer: Es ist $\begin{eqnarray} b_{n+T}=b_n \end{eqnarray}$ für alle $\begin{eqnarray} n\geq 2 \end{eqnarray}$ mit $\begin{eqnarray} T=2\cdot 10^8 \end{eqnarray}$ . Dieses Ergebnis ist per Bruteforce ermittelt, es scheint sogar allgemeiner $\begin{eqnarray} a_{n+2\cdot 10^{m-2}}\equiv a_n\bmod 10^m \end{eqnarray}$ für alle $\begin{eqnarray} n\geq 2 \end{eqnarray}$ und $\begin{eqnarray} m\geq 3\qquad () \end{eqnarray}$ zu gelten, das konnte ich aber nicht beweisen. Nun, jedenfalls ist damit $\begin{eqnarray} b_q = b_{q\bmod T} = b_{170\,786\,403} = 9\,004\,963\,588 \end{eqnarray*}$ , letzteres auch wieder nur mit roher Rechengewalt ermittelt. Ich freue mich schon auf den eleganten Weg, jedenfalls liegt erstmal ein (hoffentlich richtiger) Vergleichswert dafür vor.
29.04.2018, 03:05	Hosenschlange	Auf diesen Beitrag antworten »
Um also langsam einzusteigen kann man als erstes festhalten, dass man versuchen kann die Periodizität zu ermitteln? Auch wenn das -wie du es gemacht hast- ein "Kraftakt" ist...
29.04.2018, 08:13	HAL 9000	Auf diesen Beitrag antworten »
Jede rekursive Folge $\begin{eqnarray} b_{n+1} = g(b_n) \end{eqnarray}$ mit $\begin{eqnarray} g:\;E\to E \end{eqnarray}$ mit endlichem $\begin{eqnarray} E \end{eqnarray}$ ist zwangsläufig periodisch mit einer Periode $\begin{eqnarray} T\leq \|E\| \end{eqnarray}$ , allerdings nicht notwendig gleich von Beginn an. D.h., es existiert ein $\begin{eqnarray} n_0 \end{eqnarray}$ mit $\begin{eqnarray} b_{n+T}=b_n \end{eqnarray}$ für alle $\begin{eqnarray} n\geq n_0 \end{eqnarray}$ . Im vorliegenden Fall mit $\begin{eqnarray} E=\left\{0,1,\ldots,10^{10}-1\right\} \end{eqnarray}$ und $\begin{eqnarray} g(x) = (7x^3+9x+2)\bmod 10^{10} \end{eqnarray}$ klappt es bereits mit $\begin{eqnarray} n_0=2 \end{eqnarray}$ . Für $\begin{eqnarray} n=1 \end{eqnarray}$ offenkundig noch nicht, denn es ist $\begin{eqnarray} b_1=3 \end{eqnarray}$ während alle weiteren $\begin{eqnarray} b_n \end{eqnarray}$ auf Ziffer 8 enden.
Anzeige

30.04.2018, 16:35	Hosenschlange	Auf diesen Beitrag antworten »
Danke, HAL Ich werde mal versuchen, dass auch auf andere Folgen anzuwenden
02.05.2018, 09:32	HAL 9000	Auf diesen Beitrag antworten »
Eine Frage noch, und damit hätte ich vielleicht beginnen sollen: Das ist nicht zufällig eines dieser Projekt-Euler-Probleme? In dem Fall würde es mich nicht wundern, wenn neben ein paar vorbereitenden Überlegungen auch ein wenige Rechenpower zur Problembewältigung nötig sind.
03.05.2018, 17:33	Hosenschlange	Auf diesen Beitrag antworten »
Ein Analogon. Ich glaube es taucht unter Nr. 492 auf. Dort sind die Werte um einiges kleiner. Die spielen aber weniger eine Rolle, wenn man das Prinzip verstehen will

Neue Frage »

Antworten »

Generatorfunktion für Folge

Verwandte Themen