C#:カプレカ数を求める #C#

カプレカ数とは

Wikipedia を見るとカプレカ数には定義１と定義2の２つの定義があります。

カプレカ数（カプレカすう、Kaprekar Number）とは、次のいずれかで定義される整数である。
1. 2乗して前の部分と後ろの部分に分けて和を取ったとき、元の値に等しくなるもの
2. 桁を並べ替えて最大にしたものから最小にしたものの差を取ったとき、元の値に等しくなるもの

ここでは、定義１のカプレカ数を求めています。
例えば、 297という整数は、

$297^2 = 88209 => 88 + 209 = 297$

となるので、297はカプレカ数ということになります。

なお、この定義１にも２つのバージョンがあるらしく、その定義が微妙に異なっています。

4879はカプレカ数かどうかについて考えてみます。

$4879^2 = 23804641$ で、 238 + 04641 = 4879 となるので、これはカプレカ数と判断できるのですが、

Wikipedia(日本語)のページの定義１には、

正の整数を2乗し、それが偶数桁 2n 桁である場合は先頭 n 桁と末尾 n 桁に分け、奇数桁 2n + 1 桁である場合は先頭 n 桁と末尾 n + 1 桁に分けて和を取る。この操作によって元の値に等しくなる数をカプレカ数と呼ぶ。

とあり、この通りに考えると、2380 + 4641 != 4879 だから、カプレカ数ではない、ということになります。

それにも関わらず、同じページにカプレカ数として、

1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, …（オンライン整数列大辞典の数列 A006886）

と載っているんですよね。
つまり、定義１でも、２つの解釈があるということみたいです。

「The On-Line Encyclopedia of Integer Sequences: A006886」(Kaprekar numbers)

「The On-Line Encyclopedia of Integer Sequences: A053816」(Another version of the Kaprekar numbers)

で、ここでは、英語のWikipediaの定義（base == 10 の時のカプレカ数、以下の定義で b = 10）を採用しています。

$X^2 = Ab^n + B, where 0 < B < b^n$

$X = A + B$

whereの条件を考慮しないと、10 もカプレカ数と判断してしまうので注意です。

ところで、あの巡回数である 142857 もカプレカ数なんですね。面白いですね。

巡回数(http://gushwell.ldblog.jp/archives/51949651.html)

初期バージョン

最初に書いたカプレカ数を求めるC#のコードです。

KaprekarNumberOld.cs

    public class KaprekarValue {
        public long Number { get; set; }
        public int Part1 { get; set; }
        public int Part2 { get; set; }
    }

    public class KaprekarNumber {
        public static IEnumerable<int> Enumerate() {
            for (int n = 1; n <= int.MaxValue; n++) {
                var kv = Analyze(n);
                if (kv != null)
                    yield return n;
            }
        }
        public static KaprekarValue Analyze(int num) {
            checked {
                long num2 = (long)num * num;
                string s = num2.ToString();

                for (int i = 1; i < s.Length; i++) {
                    long a = long.Parse(s.Substring(0, i));
                    long b = long.Parse(s.Substring(i));
                    if (a >= num)
                        break;
                    if (a + b == num) {
                        return new KaprekarValue {
                            Number = num,
                            Part1 = (int)a,
                            Part2 = (int)b
                        };
                    }
                }
                return null;
            }
        }
    }

使い方はこんな感じ。

    var kaprekars = KaprekarNumber.Enumerate().Take(10);
    foreach (var n in kaprekars) {
        Console.WriteLine(n);
    }


    var k = KaprekarNumber.Analyze(2728);
    if (k != null)
        Console.WriteLine($"{k.Number} {k.Part1} {k.Part2}");

改良バージョン

どうも、Substringを使っているのが気に入らないし、Take(50)とかすると結構時間がかかります。
ということで、少し改良してみました。
数学の問題らしくSubstring()やToString()などの文字列操作を使わず使わずに書いてみました。

KaprekarNumber.cs

    public class KaprekarNumber {

        public static IEnumerable<int> Enumerate() {
            for (int n = 1; n <= int.MaxValue; n++) {
                var kv = Analyze(n);
                if (kv != null)
                    yield return n;
            }
        }

        public static KaprekarValue Analyze(int x) {
            long x2 = (long)x * x;
            var xDigits = (int)Math.Log10(x) + 1;
            var x2Digits = (int)Math.Log10(x2) + 1;
            for (int n = x2Digits - xDigits; n <= x2Digits ; n++) {
                var dn = (long)Math.Pow(10, n);
                var a = x2 / dn;
                var b = x2 % dn;
                if ((0 < b && b < dn) && (a + b == x)) {
                    return new KaprekarValue {
                        Number = x,
                        Part1 = (int)a,
                        Part2 = (int)b
                    };
                }
            }
            return null;
        }
    }

僕の手元のPCでは、約4倍弱の速度アップが認められました。

GitHubでコードを公開しています。

カプレカ数一覧 (最初の50個)

前述のコードを使い、最初の50個のカプレカ数を求めるコード書いてみました。

    var kaprekars = KaprekarNumber.Enumerate().Take(50);
    foreach (var n in kaprekars) {
        Console.WriteLine(n);
    }

以下の通りです。

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。