3m+1

Diese Aufgabe ist der Anfang unserer ganzen Programmierreihe. Jens hatte sie bei ACM International Collegiate Programming Contest gefunden und davon beim Stammtisch am 29. Januar 2004 erzählt. Daraufhin haben wir einen Laptop ergriffen und angefangen zu programmieren. Da ich (Jörg) schon am Stammtisch das ganze geleitet habe, habe ich auch die Dokumentation zu dieser Aufgabe geschrieben.

Aufgabenstellung

Die Folge <x_k> (k nat. Zahl) ist wie folgt definiert: Für gerade x_k ergibt sich x_k+1 als x_k/2 und für ungerade x_k ergibt sich x_k+1 als 3x_k+1.
Nach endlich vielen Schritten (Folgeglieder) ergibt sich x_k = 1. Welches ist die größte Anzahl an Schritten -- das größte k--, die/das sich für eine Zahl im Intervall [1,n] ergibt?

Lösung

Dieses Problem zu lösen ist ansich sehr einfach -- Brute Force. Jedoch ging es uns bei der Programmierung mehr um den Punkt, diese Aufgabe möglichst schnell und ordentlich zu bewältigen.
3m1.ps [180k], 3m1.pdf [150k], Quellen 3m1.tar.gz[22k]