Informatik

Quartalsaufgabe 1 - 2021

Fun!
Das Collatz-Problem, auch als (3n+1)-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde. Es hat Verbindungen zur Zahlentheorie, zur Theorie dynamischer Systeme und Ergodentheorie und zur Theorie der Berechenbarkeit in der Informatik. Quelle: Wikipedia Collatz-Problem
Problembeschreibung:

Beginne mit einer beliebigen Zahl \( a_0 \in \mathbb{N} \). Die Collatz-Folge ist definiert : \[ a_{n+1} = \left \{ \begin{array}{l:l} \frac{a_n}{2} & \mbox{ falls } a_n \mbox{ gerade}\\ 3 \cdot a_n +1 & \mbox{ falls } a_n \mbox{ ungerade} \end{array} \right . \] Collatzsche Vermutung:

Wenn wir die Regeln oben benutzen und mit \( a_0=13 \) beginnen, erhalten wir die folgende Folge:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Es ist zu sehen, dass diese Folge (beginnend bei 13 und endend bei 1) 10 Glieder enthält. Obwohl es bisher nicht bewiesen wurde (Collatz-Problem), wird vermutet, dass alle Anfangszahlen bei 1 enden und sich dann periodisch mit der Teilfolge 4,2,1 fortsetzen.

Aufgabenstellung:
  1. Schreiben Sie ein Programm, welches zu vorgegebenen \( a_0 \) die Länge \( L \)der Folge ausgibt. Dabei definieren wir die Länge \(L=L(a_0)\) als Anzahl der Folgenglieder bis zum Auftreten der ersten Eins.

  2. Welche Anfangszahl unter 1 Million erzeugt die längste Folge?

    HINWEIS: Sobald die Folge begonnen hat, dürfen die Folgenglieder den Wert 1 Million überschreiten.

Die Lösung kann im Lehrerzimmer oder auch Online im Schulportal MaIf - AG abgegeben werden.