Help us understand the problem. What is going on with this article?

C#で数学パズル - 素因数分解した結果が小町になる数を求める

More than 1 year has passed since last update.

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

問題

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

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

どうやって解くか

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

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

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

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

  1. 100未満の素数を全て求め、配列に格納します。
  2. この素数を組み合わせ、小町数になるかどうかを調べます。
  3. 小町数になっていれば、それを掛け合わせ、求める 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で公開したものをに加筆・修正したものです。

gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2019 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』
https://github.com/gushwell
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした