エマープでかつ上昇数とは

素数を逆転させた数もまた素数である自然数のことを 「エマープ(Emirp)」と言います。

例えば、167 は、素数ですが、これを反転した 761 も素数であり、この2つはエマープです。 Prime(素数)という単語を 反転させると Emirp になるので、そう呼ばれているそうです。

また、1479のように、左から右へどんどん大きな数字になってゆく数を、ここでは「上昇数」と呼ぶことにします。

エマープでかつ上昇数を求めるには

さて、エマープでかつ上昇数を求める方法ですが、 1 から 123456789 までのすべての数字に対して、一つずつ条件を満たすかを調べていては 効率が悪すぎます。

そのため、「全ての上昇数を求め、それが、エマープかどうかを調べる」という方法で、答えを見つけることとします。

C#のコード

RisingEmirpNumbers.cs
    class Program {
        static void Main(string[] args) {
            var solver = new RisingEmirpNumbers();
            foreach (var n in solver.Solve().OrderBy(s => s.Length))
                Console.WriteLine(n);
        }
    }

    public class RisingEmirpNumbers {
        // 問題を解く 答えは文字列として列挙する
        public IEnumerable<string> Solve() {
            int[] nums = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            foreach (var s in GetRisingNumbers("", nums)) {
                if (IsEmirp(s))
                    yield return s;
            }
        }

        // 上昇数 を求める 再帰メソッドの中で、yield return を使っている。
        private IEnumerable<string> GetRisingNumbers(string rn, IEnumerable<int> nums) {
            if (nums.Count() == 0)
                yield break;
            int i = 0;
            foreach (var n in nums) {
                i++;
                string s = rn + n.ToString();
                yield return s;
                foreach (var r in GetRisingNumbers(s, nums.Skip(i)))
                    yield return r;
            }
        }

        // エマープか?
        private bool IsEmirp(string s) {
            if (s.Length >= 2 &&
                PrimeNumber.IsPrime(long.Parse(s)) &&
                PrimeNumber.IsPrime(long.Parse(ReverseString(s))))
                return true;
            return false;
        }

        // 文字列を反転する
        private string ReverseString(string s) {
            return new string(s.Reverse().ToArray());
        }
    }

上記コードの説明を簡単にします。

Solveメソッド

エマープでかつ上昇数をすべて列挙するメソッドです。このメソッドは、上昇数を列挙し、その値が、エマープかどうかを調べています。

GetRisingNumbersメソッド

上昇数を列挙するメソッドです。IEnumerable<string> 型を返す再帰メソッドとなっています。 メソッドの第1引数には、上昇数の途中結果が渡されます。初期値は 空文字列です。 第2引数には、上昇数で利用できる数字が小さい順に格納されている IEnumerable<int> 型です。 初期値は、 { 1,2,3,4,5,6,7,8,9 } です。

例えば、第1引数に "24" という文字列が渡された時には、 第2引数には、{ 5,6,7,8,9 } が渡されます。

再帰メソッドで、IEnumerable<T> を戻り値にする方法については、僕のブログの記事「再帰メソッドで、yield returnしたい」を読んでください。

IsEmirpメソッド

素数判定は、「ミラー・ラビン素数判定法による素数判定メソッド」で示したクラスを使って素数判定をしています。この PrimeNumber.IsPrimeメソッドと下記の文字列を反転するReverseStringを使い、エマープかどうかを判定しています。

ReverseStringメソッド

LINQの Reverse拡張メソッドを利用し反転させ、文字列に変換しています。
これを拡張メソッドとして定義すれば、 string rs = s.ReverseString(); なんて書けますね。

これらのメソッドができあがれば、Solveメソッドを書くのは簡単ですね。

結果

上記コードを実行した結果(エマープでかつ上昇数の一覧)です。

13
17
37
79
149
157
167
179
347
359
389
1237
1249
1259
1279
1789
3467
3469
12689
13457
13469
13789
15679
34589
345689
1235789

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

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.