Collatz-Folge

collatz.cs

/*
Die Collatz-Vermutung oder 3n+1-Vermutung. Sie wurde 1937 vom deutschen Mathematiker Lothar Collatz formuliert und gehört zu den bekanntesten offenen Problemen der Mathematik. Die Vermutung lautet:

Starte mit einer beliebigen positiven ganzen Zahl n.

Wenn n gerade ist, setze n := n / 2.
Wenn n ungerade ist, setze n := 3n + 1.

Wiederhole diesen Vorgang.
Die Vermutung behauptet, dass unabhängig von der Startzahl die Folge immer irgendwann die Zahl 1 erreicht.

Aktueller Stand der Wissenschaft (Mai 2025)
Nicht bewiesen.

Trotz intensiver Bemühungen gibt es bis heute keinen allgemeinen Beweis für die Collatz-Vermutung.

Die Vermutung wurde numerisch für extrem große Zahlen getestet (z. B. bis ca. 2⁶⁰ ≈ 10¹⁸) und für alle getesteten Fälle bestätigt.

Der bekannte Mathematiker Terence Tao veröffentlichte 2019 einen partiellen Fortschritt, der zeigt, dass „fast alle“ Zahlen sich im statistischen Sinne wie vorhergesagt verhalten – aber kein vollständiger Beweis.

Das Problem ist so elementar, aber gleichzeitig tiefgründig, dass viele glauben: Ein Beweis (oder Gegenbeweis) würde neue Methoden in der Zahlentheorie erfordern.

Wie könnte ein Beweis grundsätzlich aussehen?
Ein wissenschaftlicher Beweis müsste zeigen, dass für jede beliebige natürliche Zahl n die Folge
nach endlich vielen Schritten den Wert 1 erreicht.

Zwei mögliche Ansätze:
1. Induktiver Beweis
Versuch, über vollständige Induktion zu zeigen, dass jede Zahl irgendwann auf eine kleinere Zahl trifft, die bereits zur „1“ führt.

Problem: Wegen der Verzweigungen (ungerade/gerade) entsteht eine Art unendlicher Baum, der sich nicht direkt induktiv erfassen lässt.

2. Widerspruchsbeweis
Annahme: Es existiert eine Zahl, die nie zur 1 führt.

Zwei Möglichkeiten:

- Die Folge wächst unendlich – man müsste zeigen, dass das nicht möglich ist.
- Die Folge tritt in einen Zyklus ≠ 1 ein – man müsste zeigen, dass alle Zyklen mit 1 enden.

Bisher wurde kein anderer Zyklus außer der trivialen Schleife (4 → 2 → 1 → 4) gefunden.


*/

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Numerics;
using System.Text.RegularExpressions;

class Program
{
    static void Main()
    {
        while (true)
        {
            Console.Write("Startzahl eingeben (z.B. 27, 9², 34^33 | q zum Beenden): ");
            string input = Console.ReadLine()?.Trim().ToLower();

            if (input == "q") break;
            if (string.IsNullOrWhiteSpace(input)) continue;

            try
            {
                input = input.Replace("²", "^2");
                BigInteger start = EvaluateExpression(input);

                if (start <= 0)
                {
                    Console.WriteLine("Nur positive ganze Zahlen erlaubt.\n");
                    continue;
                }

                BigInteger n = start;
                BigInteger max = n;
                int schritte = 0;
                List<BigInteger> folge = new();

                while (n != 1)
                {
                    folge.Add(n);
                    n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
                    if (n > max) max = n;
                    schritte++;
                    
					if (++schritte > 1_000_000)
					{
						Console.WriteLine("Abbruch: Maximale Schrittlänge erreicht. Vermutlich keine Konvergenz.");
						break;
					}
                }

                folge.Add(1);
                
				int maxAnzeigen = 200;
				Console.WriteLine("Collatz-Folge:");

				if (folge.Count > maxAnzeigen)
					Console.WriteLine(string.Join(" → ", folge.GetRange(0, maxAnzeigen)) + " → … (insgesamt " + folge.Count + " Werte)");
				else
					Console.WriteLine(string.Join(" → ", folge));

				Console.WriteLine($"\nStartwert: {start}\nSchritte: {schritte}\nMaximalwert: {max}\n");
            }
            catch (Exception ex)
            {
                Console.WriteLine($"Fehler: {ex.Message}\n");
            }
        }

        Console.WriteLine("Programm beendet.");
    }

    static BigInteger EvaluateExpression(string expr)
    {
        expr = expr.Replace(" ", "");
		
        while (expr.Contains("^"))
        {
            Match match = Regex.Match(expr, @"(\d+)\^(\d+)");
            if (!match.Success) throw new FormatException("Ungültige Potenzschreibweise.");

            BigInteger basis = BigInteger.Parse(match.Groups[1].Value);
            int exponent = int.Parse(match.Groups[2].Value);

            BigInteger result = BigInteger.Pow(basis, exponent);
            expr = expr.Replace(match.Value, result.ToString());
        }

		
        if (!BigInteger.TryParse(expr, out var value))
            throw new FormatException("Nur einfache Ausdrücke mit ^ sind erlaubt.");

        return value;
    }
}