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


## カプレカ数とは


[Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%97%E3%83%AC%E3%82%AB%E6%95%B0) を見るとカプレカ数には定義１と定義2の２つの定義があります。

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

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

$297^2 = 88209 => 88 + 209 = 297$
   
となるので、297はカプレカ数ということになります。 

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

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

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

[Wikipedia(日本語)のページ](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%97%E3%83%AC%E3%82%AB%E6%95%B0)の定義１には、


>正の整数を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](https://oeis.org/A006886)」(Kaprekar numbers)

「[The On-Line Encyclopedia of Integer Sequences: A053816](https://oeis.org/A053816)」(Another version of the Kaprekar numbers)

で、ここでは、[英語のWikipediaの定義](https://en.wikipedia.org/wiki/Kaprekar_number)（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)](http://gushwell.ldblog.jp/archives/51949651.html) 


## 初期バージョン

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

```csharp: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;
            }
        }
    }
```

使い方はこんな感じ。

```csharp
    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()などの文字列操作を使わず使わずに書いてみました。

```csharp: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](https://github.com/gushwell/CSharpAlgorithmCollection)でコードを公開しています。


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

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

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

以下の通りです。

<pre>
1
9
45
55
99
297
703
999
2223
2728
4879
4950
5050
5292
7272
7777
9999
17344
22222
38962
77778
82656
95121
99999
142857
148149
181819
187110
208495
318682
329967
351352
356643
390313
461539
466830
499500
500500
533170
538461
609687
627615
643357
648648
670033
681318
791505
812890
818181
851851
</pre>


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