小町数を使った数学パズルの第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で公開したものをに加筆・修正したものです。