Unit 26 Euklidischer Algorithmus, Kettenbruchentwicklung, Euklid-Kode

Der bekannteste Algorithmus im Bereich der Zahlentheorie ist der Euklidische Algorithmus [1,2,3,4,5] zur Berechnung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen. Er ist zugleich auch Bestandteil vieler anderer zahlentheoretischer Algorithmen, z.B. von probabilistischen Primzahltests [6,7,8,9] und des Berlekamp-Algorithmus [1,2,10,11,12,13].

  • Seien \(a\) und \(b\) zwei natürliche Zahlen mit den kanonischen Primfaktorzerlegungen
      \( a=\prod_{i=1}\,p_i^{\alpha_i}\;\mbox{ und }\;b=\prod_{i=1}\,p_i^{\beta_i} \) (1)
    Dann ist der größte gemeinsame Teiler von \(a\) und \(b\) (größte natürliche Zahl, die sowohl Teiler von \(a\) als auch von \(b\) ist)
      \( \begin{equation} \mbox{ggT}\,(a,b)=\prod_{i=1}\,p_i^{\min (\alpha_i,\beta_i)} \end{equation} \) (2)

  • Die praktische Berechnung des \(\mbox{ggT}\,(a,b)\) mittels der Definitionsgleichung (2) setzt die Berechnung der kanonischen Primfaktorzerlegungen von \(a\) und \(b\) voraus. Dieser Weg wäre schon allein wegen der nachfolgenden Informationsreduktion durch die Minimumbildung in Gl. (2) prinzipiell ineffizient, er erweist sich auch für große a und bals praktisch ungangbar, da dann der Rechenzeitaufwand für die Faktorisierung Gl. (1) extrem groß ist (vgl. [14]).
  • Eine viel elegantere und unvergleichlich effizientere Methode zur Berechnung des ggT(a, b) besteht in der ausschöpfend wiederholten Anwendung der numerisch anspruchslosen Reduktionsgleichung
      \( \mbox{ggT}\,(x,y)=\mbox{ggT}\,(y,\mbox{rest}\,(x,y))\;\mbox{ für }\;x>y\,. \) (3)
    Sie ist das Kernstück (Schleifenkörper) des Euklidischen Algorithmus (A1), der das Tupel (a, b) schrittweise in das Tupel (ggT(a, b), 0) reduziert.
    Regel Bedingung Aktion Verbundaktion
    1   \( (x,y):=(a,b) \)  
    2 \(y=0\) \(\mbox{ggT}(a,b):=x\) \(\mbox{stop}\)
    3   \((x,y):=(y,\mbox{rest}\,(x,y))\) \(\mbox{goto}\,r^2\)
    Algorithmus (A1): Euklidischer Algorithmus
Aufgabe 26.1
Leiten Sie (A1) aus Gl. (1) her.
Beachten Sie dabei:
\(\bullet \mbox{ ggT}(x,y) = \mbox{ggT}(y,x)\) (4)
\(\bullet\mbox{ Aus } x>y \mbox{ folgt } y > \mbox{rest}(x,y)\) (5)
\(\bullet\mbox{ ggT}(x,0)=x\) (6)
Aufgabe 26.2
Die zweistellige algebraische Operation \((\mathbb{O},\mathbb{N})\) sei durch
\( \displaystyle a\mathbb{O} b=\prod_{i=1}\,p_i^{|\alpha_i-\beta_i|} \) (7)
definiert.
  • Welche Eigenschaften besitzt diese Operation?
  • Geben Sie einen (A1)-analogen Algorithmus zur effizienten Berechnung von \((a\mathbb{O}b) \)an.
    • Die natürlichen Zahlen \(a\) und \(b\) lassen sich aus dem mittels (A1) berechneten \(\mbox{ggT}(a,b)\) nicht wiedergewinnen. Das ist jedoch dann der Fall, wenn man alle im Verlaufe der in \(n\) Schritten erfolgenden ggT-Berechnung anfallenden Reste \(rest(x, y)\) bzw. auch die zugehörigen \(div(x, y)\) als \(n\)-komponentige Vektoren \(\vec{r} \mbox{ bzw. }\vec{d}\) speichert, also (A1) zu (A2) erweitert.
    Regel Bedingung Aktion Verbundaktion
    1   \((x,y):=(a,b)\,;\;i:=0\)  
    2 \(y=0\) \(\mbox{ggT}(a,b):=x\)
    \(n:=i\)
    \(\vec{r}:=(r_0,r_1,r_2,\ldots ,r_{n-1})\)
    \(\vec{d}:=(d_0,d_1,d_2,\ldots ,d_{n-1})\)     		\(\mbox{stop}\)
    3   \(r_i:=\mbox{rest}\,(x,y);\)
    \(d_i:=\mbox{div}\,(x,y);\)     		 
    4   \((x,y):=(y,\mbox{rest}\,(x,y))\)  
    5   \(i: = i + 1\) \(\mbox{goto}\,r^2\)
    Algorithmus (A2):Erweiterter Euklidischer Algorithmus
    Berechnung von \(\vec{r} \mbox{ und }\vec{d} \) .
    Aufgabe 26.3
    Beweisen Sie:

    • \((a, b)\) läßt sich allein aus \(ggT(a, b)\) und \(\vec{d}\) ,,rekonstruieren'': (A3).


      • Regel Bedingung Aktion Verbundaktion
      1   \((x,y):=(\mbox{ggT}\,(a,b),0); i:=n-1 \)  
      2 i = -1 \((a,b):=(x,y)\) stop
      3   \((x,y):=(x\cdot d_i+y,x)\)  
      4   \(i:=i-1\) \(\mbox{goto}\,r^2\)

      Algorithmus (A3): ,,Rekonstruktion'' von \((a, b)\) aus \(ggT(a, b)\) und \(\vec{d}\)

    • \((a, b)\) läßt sich allein aus \(ggT(a, b)\) und \(\vec{r}\) nicht rekonstruieren, hierzu sind noch zusätzlich mindestens \(d_0\) und \(d_1\) erforderlich.
      • Aufgabe 26.4
      Zeigen Sie, daß mittels (A2) zugleich die Entwicklung von \(\frac{a}{b}\) in einen regelmäßigen Kettenbruch (vgl. Modul 16) realisiert wird:
      \( \displaystyle\frac{a}{b}=d_0+\displaystyle\frac{1}{d_1+ \displaystyle\frac{1}{d_2+\ddots + \displaystyle\frac{1}{d_{n-1}}}} =[d_0;d_1,d_2,\ldots ,d_{n-1}]\,. \) (8)

      Dem Vektor

      \( \vec{d}=(d_0,d_1,d_2,\ldots ,d_{n-1}) \) (9)

      läßt sich mittels
      \( \mbox{EKW}\,(a,b)\) = \(1^{d_0}0^{d_1}1^{d_2}\ldots\, (1\mbox{ bzw. }0)^{d_{n-1}}\)  
          \(1^{d_0}=\underbrace{1\,1\ldots 1}_{d_0 \;\mbox{Einsen}}\,;\;0^{d_1}=\underbrace{0\,0\ldots 0}_{d_1 \;\mbox{Nullen}}\,;\;1^0=\varepsilon\) (10)

      eineindeutig ein Binärwort, das Euklidische Kodewort \(EKW(a, b)\) zuordnen; \((a, b)\) ist dann auch allein aus \(ggT(a,b)\) und \(EKW(a, b)\) rekonstruierbar.

      Aufgabe 26.5
      Die geordneten Paare natürlicher Zahlen \((a,b)\) und \((c,d)\) seien jeweils teilerfremd:

      \(\mbox{ggT}\,(a,b)=1\,;\;\mbox{ggT}\,(c,d)=1\,.\) (11)

      Untersuchen Sie, wie sich Operationen mit den Operanden \(EKW(a,b)\) und \(EKW(c,d)\) auf Operationen mit den Operanden \((a,b)\) und \((c,d)\) abbilden.

      Beispiel 1:
      Aus

      \(\mbox{EKW}\,(c,d):=\overline{\mbox{EKW}\,(a,b)}\quad \mbox{ (bitweise Negation)}\) (12)
      folgt
      \(\displaystyle \frac{c}{d}=\frac{b}{a}\,.\) (13)

      Beispiel 2:
      Aus

      \(\mbox{EKW}\,(a,b)\oplus \mbox{EKW}\,(c,d)\quad \mbox{ (bitweise Addition modulo 2)}\) (14)
      folgt ?

      Beispiel 3:
      Aus

      \(\mbox{EKW}\,(c,d):=\mbox{g}\,(\mbox{EKW}\,(a,b))\quad \mbox{ (Gray-Kode)}\) (15)
      folgt ?

      Die zweidimensionale Notation des

      \(\mbox{EKW}\,(a,b)=z(0)\,z(1)\,z(2)\,\ldots\in\{0,1\}^*\,,\) (16)
      z.B. in Form einer Ulam-Spirale [15,16] als Schwarz-Weiß-Muster gemäß Bild 1

      \epsfbox{modul24_14.ps}
      Bild 1: Ulam-Spirale


      eröffnet gegenüber der eindimensionalen Zeichenkettennotation qualitativ neue Möglichkeiten zur Analyse der ,,inneren Struktur`` von \((a,b)\) mit \(ggT(a,b)\). So hat man z.B. für
      \((37889062373143906, 23416728348467685)\) (17)
      das Schwarz-Weiß-Muster Bild 2.

      \epsfbox{modul26_1.ps}
      Bild 2: Ulam-Spirale des EKW(37889062373143906,23416728348467685)

      Aufgabe 26.6
      Diskutieren Sie die erhaltenen Ergebnisse.
      Aufgabe 26.7
      Jedem diskontinuierlichen Schwarz-Weiß-Muster
      \(m:\mathbb{N}\times\mathbb{N}\rightarrow\{0,1\}\) (18)
      läßt sich via Ulam-Abtastung gemäß Bild 1 und Euklid-Dekodierung mittels (A3) eineindeutig ein teilerfremdes Zahlenpaar
      \((a,b)\in\mathbb{N}\times\mathbb{N}\) (19)
      als kompakte Speicherform von m zuordnen (vgl. Beispiel Bild 3).

      \epsfbox{modul26_2.ps}
      Bild 3: Beispiel für Bildkodierung m $ \leftrightarrow$ (37205, 14216)

      Die Komponenten a und b können dabei getrennt gespeichert, transportiert, ... werden; die sichere Rekonstruktion von m via Euklid-Kodierung \(\rightarrow\) Ulam-Musteraufbau kann nur bei Vorliegen beider Komponenten a und b erfolgen.
      Ist durch getrennte Übertragung bzw. Speicherung von a und b auf diese Weise eine kryptographisch gesicherte Bildübertragung bzw. -speicherung realisierbar?
      Diskutieren Sie Praktibilität und Sicherheit eines solchen Verfahrens!

      Über (A2) und Gl. (10) wird jedem voll gekürzten Bruch = rationale Zahl

      \(\frac{a}{b}=q\in\mathbb{Q} _+\,;\;a,b\in\mathbb{N}\,;\;\mbox{ggT}\,(a,b)=1\) (20)
      eineindeutig ein binäres Kodewort
      \(\mbox{EKW}\left(\frac{a}{b}\right)\in\{0,1\}^*\) (21)

      zugeordnet (Euklid-Kodierung).
      Es liegt nun natürlich nahe, die Euklid-Kodierung auch auf positive reelle Zahlen \(r\in \mathbb{R}_+\) auszudehnen und dabei das schon für Zahlenpaare \((a,b)\) bzw. rationale Zahlen \(q=\frac{a}{b}\) formulierte Ziel konsequent weiter zu verfolgen, unter Einbeziehung zweidimensionaler Notierungsmodelle (z.B. Ulam-Spirale \(\rightarrow\) Schwarz-Weiß-Muster) qualitativ neue Möglichkeiten zur Darstellung (Visualisierung) und Analyse der ,,inneren Struktur`` von irrationalen und transzendenten Zahlen zu gewinnen (neue methodische, heuristische und experimentelle Zugänge, z.B. auch durch Einbeziehen des Methodeninventars der digitalen Bildverarbeitung [17,18,19]).
      Man erhält dann die nachstehenden Algorithmen (A4) und (A5) zur Euklid-Kodierung bzw. -Dekodierung.

      Regel Bedingung Aktion Verbundaktion
      1   \(x:=r\,;\;y:=1^{\scriptsize{\mbox{ int}}\normalsize(r)}\)  
      2   \(x:=\displaystyle\frac{1}{\mbox{frac}\,(x)}\,;\,y:=y\circ 0^{\scriptsize{\mbox{ int}}\normalsize(x)}\)  
      3 \({\mbox{frac(x)=0}\, \underline{oder}\atop \mbox{length(y)} \ge \mbox{n}}\) \({\mbox{$w:=$ bzw. $:\approx y$} \atop \mbox{$l:=$ length$(y)$}}\) stop
      4   \( x:=\displaystyle\frac{1}{\mbox{frac}\,(x)}\,;\,y=y\circ 1^{\scriptsize{\mbox{ int}}\normalsize(x)}\)  
      5 \({\mbox{frac(x)=0}\, \underline{oder}\atop \mbox{length(y)} \ge \mbox{n}}\) \({\mbox{$w:=$ bzw. $:\approx y$} \atop \mbox{$l:=$ length$(y)$}}\) stop
      6     goto r2
      Algorithmus (A4): Euklid-Kodierung
      Approximation des \(\infty\)-stelligen Euklidischen Kodewortes \(EKW (r\in \mathbb{R}_+,r\notin \mathbb{N})\) durch das l-stellige Binärwort \(EKW (r, l )=left (EKW(r),l)\)
      \(int(x)=\lfloor x\rfloor, frac(x) = x - int(x) \)
      \(a \circ b\) - Wortverkettung; \(w\circ 1^0=w\circ\varepsilon =w\)


      Regel Bedingung Aktion Verbundaktion
      1   \((x,w):=(1\,,\,\mbox{EKW}(r,l))\)  
      2 \(w=\varepsilon\) \(r(l):=x\) stop
      3 \(\mbox{right}(w,j)=1^i\)
      \(w\) endet (rechtsbündig) mit einem 1-Block der Länge \(i\in \mathbb{N}\)i       		\((x,w):=(x+i\,,\,w\ominus 1^i)\) goto r2
      4 \(\mbox{right}(w,j)=0^j\) \((x,w):=\left({\displaystyle\frac{x}{1+j\,x}\,,\,w\ominus 0^j}\right)\) goto r2
      Algorithmus (A5): Euklid-Dekodierung
      \(EKW (r,l) = left (EKW(r),l) \longrightarrow r(l) \in \mathbb{Q} \) approximiert \( r \in \mathbb{R} \)
      \( a \ominus b \) - Wortentkettung


      Aufgabe 26.8

      • Leiten Sie (A4) und (A5) her.
      • Die Euklid-Dekodierung kann auch mit nachstehendem Algorithmus (A6) realisiert werden.

        • Regel Bedingung Aktion VA
        1   \((x,y,w):=(1\,,\,0\,,\,\mbox{EKW}(r,l))\)  
        2 \(w=\varepsilon \;\&\&\;\mbox{EKW}(r,1)=1\) \(r(l):=\displaystyle\frac{x}{y}\) stop
        3 \(w=\varepsilon \;\&\&\;\mbox{EKW}(r,1)=0\) \(r(l):=\displaystyle\frac{y}{x}\) stop
        4 \(\mbox{right}(w,i)=0^i \underline{oder} 1^i\) \((x,y,w):=\\ \left(i\,x+y\,,\,x\,,\,w\ominus (0^i \;\underline{\mbox{oder}}\; 1^i)\right)\) goto r2
        Algorithmus (A6): Euklid-Dekodierung
        \(\mbox{EKW}(r,1)=\mbox{EKW}(r,z(0))\) - erstes Binärzeichen des Euklidischen Kodewortes \(\mbox{EKW}(r,l))\)

        Vergleichen Sie die Leistungsfähigkeit von (A5) und (A6).

      • Diskutieren Sie (A4) mit den Vertauschungen
        • \( \mbox{frac}(x)\rightarrow \mbox{int}(x)\,;\;\mbox{int}(x)\rightarrow\mbox{frac}(x)\,. \) (22)

      Mit (A4) werden die nachstehenden Ulam-Spiralen Bild 4 - 19 generiert.

      \epsfbox{modul26_3.ps}
      Bild 4: Ulam-Spirale für e, US(e)       		\epsfbox{modul26_4.ps}
      Bild 5: US ($ {\frac{1}{e}}$)= $ \overline{\mbox{US}(e)}$

      \epsfbox{modul26_5.ps}
      Bild 6: US ($ \tau$) ;  $ \tau$ = $ {\frac{1}{2}}$($ \sqrt{5}$ - 1)

      \epsfbox{modul26_6.ps}
      Bild 7: US ($ \sigma$) = $ \overline{\mbox{US}(\tau )}$ ;  $ \sigma$ = $ {\frac{1}{\tau}}$ = $ {\frac{1}{2}}$($ \sqrt{5}$ + 1)

      \epsfbox{modul26_7.ps}
      Bild 8: US(tanh(1)) ;  tanh(1) = $ {\frac{e-e^{-1}}{e+e^{-1}}}$

      		\epsfbox{modul26_8.ps}
      Bild 9: US $ \left(\vphantom{\frac{1}{2}(\sqrt{21}-3)}\right.$$ {\frac{1}{2}}$($ \sqrt{21}$ - 3)$ \left.\vphantom{\frac{1}{2}(\sqrt{21}-3)}\right)$

      \epsfbox{modul26_9.ps}
      Bild 10: US $ \left(\vphantom{\frac{1}{2}(\sqrt{77}-7)}\right.$$ {\frac{1}{2}}$($ \sqrt{77}$ - 7)$ \left.\vphantom{\frac{1}{2}(\sqrt{77}-7)}\right)$

      		\epsfbox{modul26_10.ps}
      Bild 11: US $ \left(\vphantom{\frac{1}{2}\sqrt{3}}\right.$$ {\frac{1}{2}}$$ \sqrt{3}$ $ \left.\vphantom{\frac{1}{2}\sqrt{3}}\right)$

      \epsfbox{modul26_11.ps}
      Bild 12: US $ \left(\vphantom{\sqrt{5}}\right.$$ \sqrt{5}$ $ \left.\vphantom{\sqrt{5}}\right)$       		\epsfbox{modul26_12.ps}
      Bild 13: US $ \left(\vphantom{\frac{1}{4}(\sqrt{3}-1)}\right.$$ {\frac{1}{4}}$($ \sqrt{3}$ - 1)$ \left.\vphantom{\frac{1}{4}(\sqrt{3}-1)}\right)$

      \epsfbox{modul26_13.ps}
      Bild 14: US $ \left(\vphantom{\sqrt{11}}\right.$$ \sqrt{11}$ $ \left.\vphantom{\sqrt{11}}\right)$       		\epsfbox{modul26_14.ps}
      Bild 15: US $ \left(\vphantom{\frac{1}{4}(\sqrt{3})}\right.$$ {\frac{1}{4}}$($ \sqrt{3}$)$ \left.\vphantom{\frac{1}{4}(\sqrt{3})}\right)$

      \epsfbox{modul26_15.ps}
      Bild 16: US $ \left(\vphantom{\frac{1}{2}(\sqrt{11}-1)}\right.$$ {\frac{1}{2}}$($ \sqrt{11}$ - 1)$ \left.\vphantom{\frac{1}{2}(\sqrt{11}-1)}\right)$       		\epsfbox{modul26_16.ps}
      Bild 17: US (3$ \sqrt{2}$)

      \epsfbox{modul26_17.ps}
      Bild 18: US $ \left(\vphantom{\frac{1}{2}(\sqrt{13}-1)}\right.$$ {\frac{1}{2}}$($ \sqrt{13}$ - 1)$ \left.\vphantom{\frac{1}{2}(\sqrt{13}-1)}\right)$, ein klassisches Escher-Muster [20,21,22]      		 \epsfbox{modul26_18.ps}
      Bild 19: US $ \left(\vphantom{\frac{1}{2}(\sqrt{29}-3)}\right.$$ {\frac{1}{2}}$($ \sqrt{29}$ - 3)$ \left.\vphantom{\frac{1}{2}(\sqrt{29}-3)}\right)$
      Es ist bemerkenswert, daß sich die Bilder 9 - 19 ,,nach dem visuellen Eindruck``  zwanglos in Klassen einteilen lassen:
      $ \bullet$ Bilder 9 - 13
      $ \bullet$ Bilder 14 - 16
      $ \bullet$ Bilder 17 - 19,
      wobei den zugehörigen Argumenten r auf dem ersten Blick eine solche Verwandschaft nicht anzusehen ist.
      Aufgabe 26.9
      Untersuchen Sie diesen Sachverhalt experimentell mit einer genügend großen Anzahl quadratischer Irrationalitäten r [23]:

      • Welche ,,Grundmuster`` treten dabei auf?

      • Versuchen Sie einen Zusammenhang zwischen den Grundmustern und den zugehörigen Argumenten r aufzufinden.

      • Die Schwarz-Weiß-Muster Bild 9 bis 13 bilden eine Art ,, Zyklus``.

        • Generieren Sie aus geeigneten quadratischen Irrationalitäten r plausible Zwischenmuster, so daß eine lückenlose ,, Animationsfolge`` entsteht.

        • Versuchen Sie für die zugehörige Argumentfolge (ev. iterativ) ein einfaches Bildungsgesetz (,, Feldgleichungen``, vgl. [24,25,26,27]) zu finden, das die Animationsdynamik adäquat abbildet.

        • Generieren Sie damit andere interessante Animationsfolgen.

        • Diskutieren Sie die erhaltenen Ergebnisse.

      Für

      z(i) = $\displaystyle \left\{\vphantom{ \begin{array}[l]{l} 1\,,\,\mbox{ wenn $i+1$\space Primzahl}\\ 0\;\;\;\mbox{ sonst} \end{array}}\right.$$\displaystyle \begin{array}[l]{l} 1\,,\,\mbox{ wenn $i+1$\space Primzahl}\\ 0\;\;\;\mbox{ sonst} \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}[l]{l} 1\,,\,\mbox{ wenn $i+1$\space Primzahl}\\ 0\;\;\;\mbox{ sonst} \end{array}}\right.$ (23)

      erhält man mit Bild 1 die Ulam-Spirale Bild 20 (vgl. [15,16], Diagonalstruktur der Primzahlverteilung!).

      \epsfbox{modul26_19.ps}
      Bild 20: Ulam-Spirale Primzahlverteilung


      Die Ulam-Abtastung gemäß Bild 3 und anschließende Euklid-Dekodierung mittels (A5) ergibt das zugehörige

      r (Ulam-Spirale Primzahlverteilung) = 0.72294 80986 94838 ... . (24)

      Aufgabe 26.10

      • Berechnen Sie r (US Primzahlverteilung) mit höherer Genauigkeit.

      • Könnte man r (US Primzahlverteilung) auf irgend einem anderen Wege mit beliebiger Genauigkeit berechnen, wäre daraus via (A4) die Primzahlfolge in der Folge der natürlichen Zahlen konstruierbar!

      • Suchen Sie nach einer solchen Möglichkeit, sowie nach Zusammenhängen von r (US Primzahlverteilung) mit $ \pi$, e, $ \delta$, ...?
      Aufgabe 26.11
      Die Euklid-Kodierung von

      $\displaystyle \sum_{i=1}^{\infty}$ 2-2i = 0.31642 15090 21893 ...    [28] (25)

      mittels (A4) liefert das teilperiodisch aufgebaute binäre Kodewort

      EKW$\displaystyle \left(\vphantom{\sum_{i=1}^{\infty}\,2^{-2^i}}\right.$$\displaystyle \sum_{i=1}^{\infty}$ 2-2i$\displaystyle \left.\vphantom{\sum_{i=1}^{\infty}\,2^{-2^i}}\right)$ = 03w11a10b1w21a20b2w11a30b3w21a40b4w11a50b5w2... (26)

      mit

      w1 = 160414021406 ;  w2 = 160412041406 (27)

      ai = $\displaystyle \left\{\vphantom{ \begin{array}[l]{l} 2\;\;\;\mbox{ f''ur rest}... ...est}(i,8)=2\\ a_{\frac{i}{4}}\;\mbox{ f''ur rest}(i,4)=0 \end{array}}\right.$$\displaystyle \begin{array}[l]{l} 2\;\;\;\mbox{ f''ur rest}(i,4)=3\;\;\underli... ...;\mbox{rest}(i,8)=2\\ a_{\frac{i}{4}}\;\mbox{ f''ur rest}(i,4)=0 \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}[l]{l} 2\;\;\;\mbox{ f''ur rest}(... ...est}(i,8)=2\\ a_{\frac{i}{4}}\;\mbox{ f''ur rest}(i,4)=0 \end{array}}\right.$ (28)


      < ai > = \epsfbox{modul26_20.ps} (29)

      bi = $\displaystyle \left\{\vphantom{ \begin{array}[l]{lll} 2&&a_i=4\\ &\mbox{f''ur}&\\ 4&&a_i=2 \end{array}}\right.$$\displaystyle \begin{array}[l]{lll} 2&&a_i=4\\ &\mbox{f''ur}&\\ 4&&a_i=2 \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}[l]{lll} 2&&a_i=4\\ &\mbox{f''ur}&\\ 4&&a_i=2 \end{array}}\right.$. (30)

      Konstruieren und diskutieren Sie die zugehörige Ulam-Spirale.

      Im Zusammenhang mit der Lösung von Aufgabe 26.11 gelangt man zu dem teilperiodischen und selbstähnlichen Binärwort

      w = \epsfbox{modul26_21.ps} (31)
        = z(0)z(1)z(2)z(3)z(4)z(5)z(6)z(7)z(8)... (32)

      mit

      z(i) = $\displaystyle \left\{\vphantom{ \begin{array}[l]{l} z(0)=1\\ z(1)=1\\ z(2)=0\\... ...div}(i,4))\\ z(4)=1\\ z(5)=0\\ z(6)=0\\ z(\mbox{div}(i,4)) \end{array}}\right.$$\displaystyle \begin{array}[l]{l} z(0)=1\\ z(1)=1\\ z(2)=0\\ z(\mbox{div}(i,4))\\ z(4)=1\\ z(5)=0\\ z(6)=0\\ z(\mbox{div}(i,4)) \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}[l]{l} z(0)=1\\ z(1)=1\\ z(2)=0\\ ... ...div}(i,4))\\ z(4)=1\\ z(5)=0\\ z(6)=0\\ z(\mbox{div}(i,4)) \end{array}}\right.$ für  rest(i, 8) = $\displaystyle \left\{\vphantom{ \begin{array}[l]{l} 0\\ 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ \end{array}}\right.$$\displaystyle \begin{array}[l]{l} 0\\ 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}[l]{l} 0\\ 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ \end{array}}\right.$ (33)

      (vgl. [29,30]).
      Bild 21 zeigt die zugehörige Ulam-Spirale, Bild 22 die Ulam-Spirale der Gray-Kodierten

      g(w) = 011010100101101001101001010110... . (34)

      \epsfbox{modul26_22.ps}
      Bild 21: US(w)

      \epsfbox{modul26_23.ps}
      Bild 22: US (g(w))

      Aufgabe 26.12

      • Extrahieren Sie alle in den Diagonalzeilen von Bild 21 auftretenden bandförmigen Ornamente, z.B.

        Lesen Sie hierzu [31,32,33,34,35].

      • Untersuchen Sie experimentell (ev. Fortsetzung von Bild 21):
        Ist US(w) vollständig regelmäßig aufgebaut oder gibt es irgendwo unregelmäßig aufgebaute ,,Diagonalzeilen``, die sich als ,,binäre messages`` interpretieren lassen (vgl. Modul 24, Aufgabe 24.8, Bild 23).

      • Mit (A5) erhält man aus den Gln. (31) - (34)

        r(w) = 2.70891 47683 98757 ... (35)

        r(g(w)) = 0.72318 91133 09895 ... . (36)

        Suchen Sie nach einem Zusammenhang zwischen r(w) und r(g(w)).

      • Vergleichen Sie US(w) Bild 21 und US(g(w)) Bild 22.

      Bild 23: Ulam-Spirale für g(tms)
      tms = 01101001100101101001011001101001... - Thue-Morse-Folge [36,37], rekursiv generiert (vgl. [39]) mittels
      w (0) = 0
      w(t + 1) = ;   t = 0,1,2,...
      tms (0) = w(t).

      Der Quotient q = $ {\frac{\scriptstyle \mbox{Anzahl der 1--Felder}}{\mbox{Anzahl der 0--Felder}}}$ dieser Ulam-Spirale konvergiert mit wachsender Spirallänge l gegen 2.
      • Dekodieren Sie die binären ,,messages`` in den Diagonalzeilen unterhalb der Hauptdiagonalen (x $ \widehat{=}$0; xx $ \widehat{=}$1), z.B. $ \nwarrow$ in Bild 23:
        010011000100100001001000110010...
    Aufgabe 26.13
    Die Fibonacci-Folge

    < fib(i) > = 1, 1, 2, 3, 5, 8, 13,... (37)

    wird durch das rekursive Bildungsgesetz

    fib(i + 2) = fib(i + 1) + fib(i) (38)

    mit den Startwerten

    fib(0) = fib(1) = 1 (39)

    erzeugt.
    Das binäre Analogon, die Fibonacci-Wort-Folge (rabbit sequence) [36,37,38]

    < fibw(i) > = 1, 10, 101, 10110, 10110101,... (40)

    entsteht aus dem rekursiven Bildungsgesetz

    fibw(i + 2) = fibw(i + 1)ofibw(i) (41)

    mit den Startwerten

    fibw(0) = 1 ;  fibw(1) = 10 . (42)

    Untersuchen Sie experimentell die Ulam-Spirale des Fibonacci-Wortes

    und seiner Gray-Kodierten

    g(fibw) , (44)

    insbesondere mit den Fragestellungen von Aufgabe 26.12 und von [36].