小町数を使った数学パズルの第5弾です。

問題

ある整数 N を素因数分解したときに、因数が1-9をひとつずつ使っている Nを求めよ。それぞれの因数は、100未満とする。
ただし、求める N は、intで表現できる数とする。

例えば、7334490 を素因数分解すると、2 * 3 * 5 * 41 * 67 * 89 となり、1から9までの数が一つずつ現れます。この 7334490 のような数を求めよう、ということです。

どうやって解くか

この問題をどうやって解くかですが、初めに思いつくのは以下のような手順です。

N=1とする。
Nを素因数分解する。因数に100以上のものがあれば、処理4に移る。
2で求めた素因数(複数)が、1-9を一つずつ使っているかを調べる。
Nに1足して、処理2へ戻る

このやり方は、ものすごく効率悪いです。さらに問題なのが、いつまで繰り返せば良いかがはっきりとわからないことです。

そのため、以下のような手順で求めることにします。

100未満の素数を全て求め、配列に格納します。
この素数を組み合わせ、小町数になるかどうかを調べます。
小町数になっていれば、それを掛け合わせ、求める N を導き出します。

それぞれの因数が、100未満という制限があるため、自然数を小さい値から順に素因数分解していった場合と比べると、かなり効率よく解を求めることができると思います。

手順2は、さらっと「この素数を組み合わせ」と書いていますが、これがこのプログラムのキモになるところです。ここで再帰処理を使っています。具体的には以下のコードを見てください。

C#のコード

この問題を解く、C#のコードを示します。

なお、素数を求めるPrimesメソッドは、C#:エラトステネスの篩を使った素数の計算で示した、もっとも基本的なバージョンを使用しています。

using System;
using System.Collections.Generic;
using System.Linq;

namespace KomachiFactorization {
    public class Solver {
        // 解を求める
        public IEnumerable<int[]> Solve() {
            return Solve(new int[0], Primes(100).ToArray());
        }

        // maxnumまでの素数を求める。 エラトステネスのふるいで求めている
        private static IEnumerable<int> Primes(int maxnum) {
            int[] sieve = Enumerable.Range(0, maxnum + 1).ToArray();
            sieve[1] = 0;  // 0 : 素数ではない
            int squareroot = (int)Math.Sqrt(maxnum);
            for (int i = 2; i <= squareroot; i++) {
                if (sieve[i] <= 0)
                    continue;
                for (int n = i * 2; n <= maxnum; n += i)
                    sieve[n] = 0;
            }
            return sieve.Where(n => n > 0);
        }


        // primesA 素因数分解した途中結果 (必ず小さい因数から順に並ぶ）
        // primesB 候補となる素数 （どんどん絞られてゆく）
        private IEnumerable<int[]> Solve(IEnumerable<int> primesA, IEnumerable<int> primesB) {
            // 素因数分解した結果を文字列にし、小町数かどうかを調べる
            var s = ToString(primesA);
            if (IsKomachi(s)) {
                yield return primesA.ToArray();
            } else {
                // 小町の可能性があるならば、PrimesBから一つ取り出し、
                // その因数を解PrimesAに加え、再帰処理してゆく。
                if (IsValid(s)) {
                    foreach (var n in primesB) {
                        var ans = Solve(primesA.Concat(new int[] { n }), primesB.SkipWhile(a => a <= n));
                        foreach (var primes in ans)
                            yield return primes;
                    }
                }
            }
        }

        // 適合しているか （同じ数字があるとダメ）
        private bool IsValid(string s) {
            var length = s.Length;
            // 重複していれば、Distinctした個数とは一致しない
            return s.Distinct().Count() == length;
        }

        // int配列を文字列に変換
        private string ToString(IEnumerable<int> nums) {
            var s = "";
            foreach (var n in nums) {
                s += n.ToString();
            }
            return s;
        }

        // 小町数か、（引数は数値を文字列に変換したもの）
        private bool IsKomachi(string s) {
            if (s.Length != 9)
                return false;
            return s.OrderBy(c => c).SequenceEqual("123456789");
        }
    }
}

using System;
using System.Linq;

namespace KomachiFactorization {
    class Program {
        static void Main(string[] args) {
            var solver = new Solver();
            foreach (var ans in solver.Solve()) {
                var s = ans.Aggregate((x, y) => x * y).ToString() + 
                        " = " +
                        String.Join(" * ", ans);
                Console.WriteLine(s);
            }
        }
    }
}

ちょっと解説

この問題を解くのに以下のようにSolveメソッドを再帰呼び出しをしています。

var ans = Solve(primesA.Concat(new int[] { n }), primesB.SkipWhile(a => a <= n));

nは、primesBに含まれる、因数の候補の一つです。これを解答を示すprimesA(素因数のリスト)に加え、候補を示すprimesBは、そのnよりも大きな値だけを残して、Solveメソッドを呼び出しています。

このコードを SkipWhileではなく、Whereを使って

// 解答primesAにnを追加。候補となる素数リストprimeBからnを除外
var ans = Solve(primesA.Concat(new int[] { n }), primesB.Where(a => a != n));

としてしまうと、

7334490 = 2 * 3 * 5 * 41 * 67 * 89
7334490 = 2 * 3 * 5 * 41 * 89 * 67
…… 
7334490 = 2 * 3 * 5 * 67 * 41 * 89
7334490 = 2 * 3 * 5 * 67 * 89 * 41
7334490 = 2 * 3 * 5 * 89 * 41 * 67
……

のように、数字を入れ替えただけの解を列挙してしまいます。
そのため、SkipWhileを使って素因数が必ず小さい値から並ぶようにし、重複を避けています。その部分が Solveメソッドの第2引数のprimesB.SkipWhile(a => a <= n)です。

結果

このプログラムの結果です。

7334490 = 2 * 3 * 5 * 41 * 67 * 89
7654890 = 2 * 3 * 5 * 47 * 61 * 89
16341290 = 2 * 5 * 7 * 43 * 61 * 89
25915198 = 2 * 41 * 53 * 67 * 89
26904118 = 2 * 41 * 59 * 67 * 83
27047278 = 2 * 47 * 53 * 61 * 89
28079398 = 2 * 47 * 59 * 61 * 83
28115545 = 5 * 23 * 41 * 67 * 89
29343745 = 5 * 23 * 47 * 61 * 89
33060145 = 5 * 29 * 41 * 67 * 83
34504345 = 5 * 29 * 47 * 61 * 83

結果をみて面白いと思うのは、最初の3つの下二桁が90、最後の4つの下二桁が45というところですね。
そしてその2つに挟まれている数は、下一桁がすべて8になっています。
なにか法則性があるのかな？

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