C#で数学パズル - 二乗して回文となる非回文数を求める

二乗すると回文数となる数で、二乗する前の数が回文でない正の整数を求めるプログラムを書いてみました。

回文数とは、21512 のように、逆から読んでも同じ数になる数字のことです。

C#のコード

PalindromicSquare.cs

    class Program {
        static void Main(string[] args) {
            using(new Timewatch()) { 
                var solver = new PalindromicSquare();
                foreach (var n in solver.Solve(100000000)) {
                    Console.WriteLine($"{n} * {n} = {(long)n * n}");
                }
            }

        }
    }

    public class PalindromicSquare {
        private bool IsPalindrome(long num) {
            string s = num.ToString();
            int len = s.Length;
            int rx = len - 1;
            int lx = 0;
            while (lx < len / 2)
                if (s[lx++] != s[rx--])
                    return false;
            return true;
        }

        public IEnumerable<int> Solve(int maxnum) {
            for (var i = 1; i <= maxnum; i++) {
                if (IsPalindrome((long)i * i) && !IsPalindrome(i))
                    yield return i;
            }
        }
    }

    public class Timewatch : IDisposable {
        private Stopwatch sw = new Stopwatch();

        public Timewatch() {
            sw.Start();
        }
        public void Dispose() {
            sw.Stop();
            Console.WriteLine($"{sw.ElapsedMilliseconds}ミリ秒 (約{sw.Elapsed.TotalSeconds:#.0}秒)");
        }
    }

PalindromicSquareクラスがその解を求めるクラスで、Solveメソッドは、IEnumerabl<int>を返すメソッドとしています。

少しでも速くなるように、回文かどうかを判定するIsPalindromeでは、文字列を反転させ比較するのではなく、文字列の両端から内側に向かって比較するようにしています。

また、Solveメソッドの中では、IsPalindrome((long)i * i)をIsPalindrome(i)よりも先に呼び出すようにしています。

iが非回文である確率よりもi * iが回文となる確率の方が低いはずですから、以下のコードよりもメソッドの呼び出し回数が減り多少速くなります。

      if (!IsPalindrome(i) && IsPalindrome((long)i * i))
          yield return i;

このプログラムでは、100000000以下の値を対象にしました。
手元のPCだと、30秒弱で答えが求まりました。

これよりも大きな値を対象にすると、もっと速度を上げる必要がありますが、処理速度を上げるには根本的にアルゴリズムを考え直す必要がありそうです。
残念ながら、その答えを持ち合わせていません。

Solveメソッドは(IsPalindromeも含めて)、LINQ使えば、もっと簡潔に書けると思います。

なお、このプログラムでは、Timewatchというクラスを定義し、簡単に時間計測ができるようにしています。

結果

26 * 26 = 676
264 * 264 = 69696
307 * 307 = 94249
836 * 836 = 698896
2285 * 2285 = 5221225
2636 * 2636 = 6948496
22865 * 22865 = 522808225
24846 * 24846 = 617323716
30693 * 30693 = 942060249
798644 * 798644 = 637832238736
1042151 * 1042151 = 1086078706801
1109111 * 1109111 = 1230127210321
1270869 * 1270869 = 1615108015161
2012748 * 2012748 = 4051154511504
2294675 * 2294675 = 5265533355625
3069307 * 3069307 = 9420645460249
11129361 * 11129361 = 123862676268321
12028229 * 12028229 = 144678292876441
12866669 * 12866669 = 165551171155561
30001253 * 30001253 = 900075181570009
64030648 * 64030648 = 4099923883299904
11764ミリ秒 (約11.8秒)

---

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