2015年02月18日

C#でコラッツ・角谷の問題のステップ数(2^20まで)

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その71

■問題 (出題者:ところてん さん)
任意の数nを与えたときに
・nが偶数ならば2で割る (n=n/2)
・nが奇数ならば3倍して1を足す (n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
(すべての数について成り立つかは不明) 参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1〜2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

参考: コラッツの問題の成り立つ範囲
http://q.hatena.ne.jp/1115469752

C#のプログラミング的にもアルゴリズム的にも、普通のコードなので説明の必要はありませんね。
しいて言えば、コラッツ・角谷の予想が成立することが大前提で書かれたコードです。
成り立たないと無限ループに陥ります。まあ、その心配はなさそうですが...
また、オーバーフローは考慮していません。
もうすこし大きな値で確認するには、BigIntegerを使ったほうがよさげですね。


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Stopwatch sw = Stopwatch.StartNew();
            CollatzKakutani.PrintMaxStep((long)Math.Pow(2, 20));
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds + "ミリ秒");
            Console.ReadLine();
        }
    }

    static class CollatzKakutani {
        public static void PrintMaxStep(long limit) {
            long maxn = long.MinValue;
            long maxfn = long.MinValue;           
            for (long i = 1; i <= limit; i++) {
                long r = Calc(i);
                if (r > maxfn) {
                    maxfn = r;
                    maxn = i;
                }
            }
            Console.WriteLine("f({0})={1}", maxn, maxfn);
        }

        public static long Calc(long n) {
            long result = 0;
            while (n != 1) {
                result++;
                if (n % 2 == 0)
                    n = n / 2;
                else
                    n = n * 3 + 1;
            }
            return result;
        }
    }
}

僕のPCでの実行結果 (Releaseモード)
f(837799)=524
401ミリ秒


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52407163