このCollat​​zシーケンスマイナスが

Question

のエラーは、次の反復配列は、正の整数の集合のために定義される：

N→N/2（nは偶数）→

N 3N + 1（nは奇数）

上記のルールを使用し、13で始まる、我々は以下の配列を生成：→8

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

をそれこのシーケンス（13で開始し、1で終わる）が 10項を含むことが分かる。まだ証明されていませんが（Collat​​z Problem）、すべての開始数は1で終わると考えられます。

100万未満の最初の数字が最も長いチェーンを生成していますか？

これは手元の問題に対する私の解決策です。

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(); 
} 

私は自分のコードが正しく動作していた場合だけチェックするpossCounter++後Console.WriteLine(chainNum)を置きました。しかし、ある特定の時点では、それは正しく実行され、の負の数値を実行し始めました。私は自分のコードでどこが間違っているのか分かりません。

Answer 1

これは整数オーバーフローです。代わりに長いタイプのような大きなタイプを使用すると、正常に動作するはずです。

Answer 2

問題（シーケンスを追跡する）あなたはint.MaxValueより大きい数

56991483520 

に実行されますので、あなたがオーバーフローがあるでしょうを解決します。シーケンスメンバーにlongを使用することをお勧めします。あなたが40、20と16のための長さを知っているし、再びこれらの数字のために

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); 

を計算する必要がない

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

を追跡した：より多くの最適化の1つのヒントは、シーケンス項目のシリーズで更新することです

結果は

837799 generates 525 values