Collatz sequence - minuser Fehler

Question

Die folgende iterative Sequenz wird für den Satz von positiven ganzen Zahlen definiert:

n → n/2 (n gerade)

n → 3N + 1 (n ungerade)

Verwenden der Regel über und mit 13 beginnen, erzeugen wir die folgende Sequenz:

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

Es Zu erkennen ist, dass diese Sequenz (ab 13 beginnend und bei 1 endend) 10 Terme enthält. Obwohl es noch nicht bewiesen ist (Collatz-Problem), wird angenommen, dass alle Startnummern bei 1 enden.

Welche Startnummer, unter einer Million, produziert die längste Kette?

Dies ist meine Lösung für das Problem zur Hand.

static void Main(string[] args) 
{ 
    int possCounter = 0; 
    int largestChain = 0; 
    int largestChainNum = 0; 
    int chainNum = 0; 
    for (int i = 2; i <= 999999; i++) 
    { 
     chainNum = i; 
     possCounter = 1; 
     while (chainNum != 1) 
     { 
      if (chainNum % 2 == 0) 
      { 
       chainNum = chainNum/2; 
      } 
      else 
      { 
       chainNum = (3 * chainNum) + 1; 
      } 
      possCounter++; 
      Console.WriteLine(chainNum); 
     } 
     if (possCounter > largestChain) 
     { 
      largestChainNum = i; 
      largestChain = possCounter; 
     } 
    } 
    Console.WriteLine(largestChainNum); 
    Console.ReadLine(); 
} 

Ich legte die Console.WriteLine(chainNum) nach possCounter++ nur, wenn mein Code zu überprüfen korrekt ausgeführt wurde. Es würde korrekt laufen, aber an einem bestimmten Punkt begann es zu laufen negative Zahlen. Ich bin mir nicht sicher, wo ich mit meinem Code falsch gelaufen bin.

Answer 1

Es ist ein Integer Overflow. Wenn Sie stattdessen einen größeren Typ (wie Long) verwenden, sollte es gut funktionieren.

Answer 2

Wenn das Problem zu lösen (die Verfolgung der Sequenzen) werden Sie in die Zahl laufen

56991483520 

, die größer als int.MaxValue ist und somit werden Sie haben einen Überlauf; Ich schlage vor, long für Sequenzmitglieder zu verwenden. Eine Optimierung Spitze mehr ist von Serie der Sequenzelemente zu aktualisieren: aufgespürt zu haben

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

kennen Sie die Längen für 40, 20 und 16 und haben keine Notwendigkeit für diese Zahlen zu berechnen wieder

private static Dictionary<long, int> s_Counts = new Dictionary<long, int>() { 
    {1, 1}, 
}; 

private static void AppendCounts(long n) { 
    List<long> list = new List<long>(); 

    for (; !s_Counts.ContainsKey(n); n = n % 2 == 0 ? n/2 : 3 * n + 1) 
    list.Add(n); 

    int count = s_Counts[n]; 

    for (int i = list.Count - 1; i >= 0; --i) 
    s_Counts.Add(list[i], count + list.Count - i); 
} 

... 

for (int i = 1; i < 1000000; ++i) 
    AppendCounts(i); 

KeyValuePair<long, int> max = new KeyValuePair<long, int>(0, 0); 

foreach (var pair in s_Counts) 
    if (pair.Value > max.Value) 
    max = pair; 

Console("{0} generates {1} values", max.Key, max.Value); 

Das Ergebnis ist

837799 generates 525 values