C#
数学パズル

C#で数学パズル - 小町数となる単位分数を求めたら実に面白い結果が出た!

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

問題

単位分数が、1/n となる、1-9までの数を1回ずつ使った分数を求めよ。
ただし、n は、2から 9までの数とする。
たとえば、6729/13458 は、1/2かつ1-9までの数を1回ずつ使っているので、求める答えのひとつである。

どうやって解くか

この問題を解くプログラムは、すぐに2つのやり方が考えつきます。

  1. nが与えられたときに、小町数となる分数を求め、それが、1/n となるかどうかを調べる方法
  2. nが与えられたときに、m/(n*m)となる分数を求め、それが小町数になっているかを調べる方法

※ 1,2,3,4,5,6,7,8,9で構成される数を小町数と呼びます。

後者のほうがプログラムが簡単そうなので、後者の方法でプログラムを作成しました。

1/2, 1/3 ... 1/9 となる小町数を求めるわけですから、求める分数は、必ず 4桁/5桁となるはずです。
3桁/6桁だと、1/nにはなりえません。5桁/4桁だと、1以上になりますから、yはり、1/nにはなりません。

そのため、上記のm/(n*m)mは、1234から9876までの範囲ということになります。

たとえば、

1/2の時は、1234 / (1234 * 2)、つまり、1234/2468 が 1から9で構成されているかを調べます。

次に

1235 / (1235 * 2) -> 1235/2470 が1から9で構成されているかを調べます。

次に

1236 / (1236 * 2) -> 1236/2472 が1から9で構成されているかを調べます。

次に...

と順に調べていきます。

これは、123456789の順列を求める前者のやり方(小町数となる分数を求め、それが、1/nとなるかどうかを調べる方法)よりも明らかに効率が良さそうです。

小町数かどうかを調べるのは、文字列にして文字順に並べ替え、"123456789"と等しいかを調べています。

文字列の長さが9であることが保証されていれば

    "123456789".All(c => s.Contains(c))

で小町数かどうかを調べればいいのですが、ここでは以下のようなコードにしています。

    s.OrderBy(c => c).SequenceEqual("123456789")

これならば、長さが9以外の場合には、falseになるので、このほうが、汎用性が高いし、意図が明確になりますね。

C#のコード

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

namespace UnitFractionApp
{
    public class Program {
        static void Main(string[] args) {
            // n が2~9までのすべての場合の、解を求め、プリントする
            for (var denominator = 2; denominator <= 9; denominator++) {
                var ans = UnitFractionKomachi.Solve(denominator);
                PrintResult(denominator, ans);
            }
        }

        // n == denominatorの時の解をプリントする
        private static void PrintResult(int denominator, IEnumerable<int> numerators) {
            StringBuilder sb = new StringBuilder();
            int i = 1;
            foreach (var n in numerators) {
                int den2 = n * denominator;
                sb.AppendFormat("{0,2} : {1} / {2} = 1 / {3}\n", i++, n, den2, denominator);
            }
            Console.WriteLine(sb.ToString());
        }

    }

    static class UnitFractionKomachi {
        // denominator 分母 2-9 まで
        // 1/denominatorとなる小町数を求める
        // 単位分数の分母が 2-9までの場合は、小町数になる分数の分子と分母は、4桁/5桁になる
        public static IEnumerable<int> Solve(int denominator) {
            // 小町数で単位分数
            for (int m = 1000; m <= 9876; m++) {
                string s = (denominator * m).ToString() + m.ToString();
                if (s.OrderBy(c => c).SequenceEqual("123456789")) {
                    yield return m;
                }
            }
        }
    }
}

結果

最初の3つの分子を見てびっくりしました。6729, 6792, 6927 ですよ。
そして、さらに下を見ていくと、7269, 7692, 9267, 2697, 2769, 2967, 9627なんて数も出てきます。実に面白いですね。そして不思議です。

 1 : 6729 / 13458 = 1 / 2
 2 : 6792 / 13584 = 1 / 2
 3 : 6927 / 13854 = 1 / 2
 4 : 7269 / 14538 = 1 / 2
 5 : 7293 / 14586 = 1 / 2
 6 : 7329 / 14658 = 1 / 2
 7 : 7692 / 15384 = 1 / 2
 8 : 7923 / 15846 = 1 / 2
 9 : 7932 / 15864 = 1 / 2
10 : 9267 / 18534 = 1 / 2
11 : 9273 / 18546 = 1 / 2
12 : 9327 / 18654 = 1 / 2

 1 : 5823 / 17469 = 1 / 3
 2 : 5832 / 17496 = 1 / 3

 1 : 3942 / 15768 = 1 / 4
 2 : 4392 / 17568 = 1 / 4
 3 : 5796 / 23184 = 1 / 4
 4 : 7956 / 31824 = 1 / 4

 1 : 2697 / 13485 = 1 / 5
 2 : 2769 / 13845 = 1 / 5
 3 : 2937 / 14685 = 1 / 5
 4 : 2967 / 14835 = 1 / 5
 5 : 2973 / 14865 = 1 / 5
 6 : 3297 / 16485 = 1 / 5
 7 : 3729 / 18645 = 1 / 5
 8 : 6297 / 31485 = 1 / 5
 9 : 7629 / 38145 = 1 / 5
10 : 9237 / 46185 = 1 / 5
11 : 9627 / 48135 = 1 / 5
12 : 9723 / 48615 = 1 / 5

 1 : 2943 / 17658 = 1 / 6
 2 : 4653 / 27918 = 1 / 6
 3 : 5697 / 34182 = 1 / 6

 1 : 2394 / 16758 = 1 / 7
 2 : 2637 / 18459 = 1 / 7
 3 : 4527 / 31689 = 1 / 7
 4 : 5274 / 36918 = 1 / 7
 5 : 5418 / 37926 = 1 / 7
 6 : 5976 / 41832 = 1 / 7
 7 : 7614 / 53298 = 1 / 7

 1 : 3187 / 25496 = 1 / 8
 2 : 4589 / 36712 = 1 / 8
 3 : 4591 / 36728 = 1 / 8
 4 : 4689 / 37512 = 1 / 8
 5 : 4691 / 37528 = 1 / 8
 6 : 4769 / 38152 = 1 / 8
 7 : 5237 / 41896 = 1 / 8
 8 : 5371 / 42968 = 1 / 8
 9 : 5789 / 46312 = 1 / 8
10 : 5791 / 46328 = 1 / 8
11 : 5839 / 46712 = 1 / 8
12 : 5892 / 47136 = 1 / 8
13 : 5916 / 47328 = 1 / 8
14 : 5921 / 47368 = 1 / 8
15 : 6479 / 51832 = 1 / 8
16 : 6741 / 53928 = 1 / 8
17 : 6789 / 54312 = 1 / 8
18 : 6791 / 54328 = 1 / 8
19 : 6839 / 54712 = 1 / 8
20 : 7123 / 56984 = 1 / 8
21 : 7312 / 58496 = 1 / 8
22 : 7364 / 58912 = 1 / 8
23 : 7416 / 59328 = 1 / 8
24 : 7421 / 59368 = 1 / 8
25 : 7894 / 63152 = 1 / 8
26 : 7941 / 63528 = 1 / 8
27 : 8174 / 65392 = 1 / 8
28 : 8179 / 65432 = 1 / 8
29 : 8394 / 67152 = 1 / 8
30 : 8419 / 67352 = 1 / 8
31 : 8439 / 67512 = 1 / 8
32 : 8932 / 71456 = 1 / 8
33 : 8942 / 71536 = 1 / 8
34 : 8953 / 71624 = 1 / 8
35 : 8954 / 71632 = 1 / 8
36 : 9156 / 73248 = 1 / 8
37 : 9158 / 73264 = 1 / 8
38 : 9182 / 73456 = 1 / 8
39 : 9316 / 74528 = 1 / 8
40 : 9321 / 74568 = 1 / 8
41 : 9352 / 74816 = 1 / 8
42 : 9416 / 75328 = 1 / 8
43 : 9421 / 75368 = 1 / 8
44 : 9523 / 76184 = 1 / 8
45 : 9531 / 76248 = 1 / 8
46 : 9541 / 76328 = 1 / 8

 1 : 6381 / 57429 = 1 / 9
 2 : 6471 / 58239 = 1 / 9
 3 : 8361 / 75249 = 1 / 9

分数 1/2 と 1/5 のところだけぬきだして並び替えしてみると、以下のようになり、分子が2,3,7,9からなるグループと、分子が2,6,7,9の2つのグループに綺麗に分かれました。
2,7,9 が共通していて、違いは3と6だけ、数字のもつ不思議さを感じた問題でした。

7293 / 14586 = 1 / 2
7329 / 14658 = 1 / 2
7923 / 15846 = 1 / 2
7932 / 15864 = 1 / 2
9273 / 18546 = 1 / 2
9327 / 18654 = 1 / 2
2937 / 14685 = 1 / 5
2973 / 14865 = 1 / 5
3297 / 16485 = 1 / 5
3729 / 18645 = 1 / 5
9237 / 46185 = 1 / 5
9723 / 48615 = 1 / 5

6729 / 13458 = 1 / 2
6792 / 13584 = 1 / 2
6927 / 13854 = 1 / 2
7269 / 14538 = 1 / 2
7692 / 15384 = 1 / 2
9267 / 18534 = 1 / 2
2697 / 13485 = 1 / 5
2769 / 13845 = 1 / 5
2967 / 14835 = 1 / 5
6297 / 31485 = 1 / 5
7629 / 38145 = 1 / 5
9627 / 48135 = 1 / 5

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