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

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

More than 1 year has passed since last update.

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

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
ユーザーは見つかりませんでした