JavaScripts › Mathematik

Collatz Problem

Veranschaulicht die berühmte 3n+1-Folge: Gerade Zahlen werden halbiert, ungerade verdreifacht plus eins — endet das wirklich immer bei 1?

Inspiriert durch einen Beitrag von Vollautomatisch in unserem Forum hat uns david97 dieses Script geschickt, das das sogenannte Collatz-Problem veranschaulicht.

Dahinter steckt eine verblüffend einfache Rechenvorschrift, auch als 3n+1-Folge bekannt: Man startet mit einer beliebigen natürlichen Zahl. Ist sie gerade, wird sie halbiert; ist sie ungerade, wird sie verdreifacht und um eins erhöht. Mit dem Ergebnis geht es nach derselben Regel weiter — so lange, bis die Folge bei 1 ankommt. Aus der vorbelegten 34 wird so 17, dann 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2 und schließlich 1.

Das eigentliche mathematische Problem dabei, benannt nach Lothar Collatz, der es 1937 formulierte: Es gibt bis heute weder einen Beweis noch einen Gegenbeweis dafür, dass diese Folge für jede natürliche Zahl irgendwann bei 1 endet. Per Computer wurde die Vermutung zwar für gewaltige Zahlenbereiche bestätigt, ein allgemeiner Beweis fehlt aber — sie zählt zu den bekanntesten ungelösten Problemen der Mathematik.

Zur Bedienung: Tragt eine natürliche Zahl in das Feld ein und klickt auf „Berechnen" — darunter erscheint die komplette Folge bis zur 1. Oder findet ihr eine Zahl, bei der die Folge nicht bei 1 endet? Probiert es aus! Wer Gefallen an solchen Zahlenfolgen und Vermutungen hat: Im Archiv gibt es auch Scripts zur Fibonacci-Reihe und zur Goldbachzahl — die Goldbachsche Vermutung ist ebenfalls bis heute unbewiesen.

Mathematik Baujahr 2007 läuft in deinem Browser
Eingesandt von david97

So funktioniert das Script

Das Script ist angenehm kurz: Es liest die Startzahl aus dem Eingabefeld, wendet in einer Schleife die Collatz-Regel an und sammelt dabei alle Zwischenwerte in einem Text, der am Ende in die Ausgabefläche geschrieben wird.

let i = parseInt(document.getElementById("col-zahl").value, 10);

if (isNaN(i) || i < 1) {
  ausgabe.textContent = "Bitte eine natürliche Zahl ab 1 eingeben.";
  return;
}

parseInt(…, 10) macht aus dem Feldinhalt eine ganze Zahl (die 10 steht für das Dezimalsystem). Die anschließende Prüfung ist hier besonders wichtig: isNaN() („is Not a Number") fängt ungültige Eingaben ab, und i < 1 verhindert Starts mit 0 oder negativen Zahlen — für die würde die Folge nämlich nie bei 1 ankommen und die Schleife liefe endlos. Im Fehlerfall erscheint eine Meldung und return beendet die Funktion.

while (i !== 1) {
  if (i % 2 === 0) {
    i = i / 2;
  } else {
    i = i * 3 + 1;
  }
  output += i + "<br>";
}

Das ist die komplette Collatz-Regel in Codeform. Die while-Schleife läuft, solange i nicht 1 ist. Der Modulo-Operator % liefert den Rest einer Division — i % 2 === 0 bedeutet also „i ist gerade". Gerade Zahlen werden halbiert, ungerade mit i * 3 + 1 weiterverarbeitet. Nach jedem Schritt wird der neue Wert samt Zeilenumbruch <br> an die Variable output angehängt. Dass niemand beweisen kann, dass diese Schleife für jede Startzahl endet, ist genau der Witz des Collatz-Problems.

ausgabe.innerHTML = output;

Erst nach der Schleife wird der gesammelte Text auf einen Schlag per innerHTML ausgegeben — das ist deutlich schneller, als das Dokument bei jedem Schritt einzeln zu verändern, und ersetzt das document.write() des Originals, das auf modernen Seiten Probleme macht. Die letzte Zeile verbindet die Funktion mit dem Knopf: addEventListener("click", doCollatz) sorgt dafür, dass die Berechnung bei jedem Klick läuft; das Script steht dafür unter dem Formular, damit Feld und Knopf schon existieren.

Zum Anpassen: Wenn ihr statt untereinander lieber alles in einer Zeile sehen wollt, ersetzt das "<br>" durch " → ". Und mit einer Zählvariablen, die in der Schleife per schritte++ hochgezählt wird, könnt ihr zusätzlich ausgeben, wie viele Schritte die Folge bis zur 1 braucht — bei manchen Startzahlen (probiert mal 27) sind es überraschend viele.

Script für die eigene Homepage

Kopiert euch den kompletten Code und fügt ihn an der Stelle eurer Seite ein, an der das Script erscheinen soll. Er läuft ohne weitere Dateien und ohne fremde Server.

Mehr aus der Kategorie Mathematik