C#
数学パズル

C#で数学パズル - N倍すると巡回する自然数を求める

この記事は、もう数十年前に出版された『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をC#で解いたものです。

問題

n倍して桁が巡回する自然数を求めてください。 nは、2 <= n <= 9 とします。この時の自然数を巡回数と言います。

例えば、1234の場合は、2倍した値が、2341, 3412, 4123 のいずれかになれば、巡回すると言えます。実際には、2倍した値は2468なので、巡回はしません。
巡回数は循環数と言う場合もあるようです。

解答コード

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

namespace CyclicNumberApp {
    public class CyclicNumber {
        private int multiplier;
        public CyclicNumber(int multiplier) {
            this.multiplier = multiplier;
        }

        // multiplier倍すると巡回する数を求める。
        public IEnumerable<int> Solve() {
            // 計算時間を考慮して、1-9999999までの自然数に限定しました。
            foreach (var num in Enumerable.Range(1, 10000000 / multiplier)) {
                if (IsCyclicNumber(num)) {
                    yield return num;
                }
            }
        }

        // numが巡回数かどうかを調べる
        private bool IsCyclicNumber(int num) {
            string numstr = num.ToString();
            string result = (num * multiplier).ToString();
            // 速度を速めるための泥臭い判断  ここから ↓
            if (result.Length != numstr.Length)
                return false;
            foreach (var c in result)
                if (!numstr.Contains(c))
                    return false;
            // ↑ ここまで (無くても正しく動作する)
            return (GetCyclics(num).Any(x => result == x));
        }

        // numを巡回させた数を文字列に変換し列挙する。
        private IEnumerable<string> GetCyclics(int num) {
            string s = num.ToString();
            for (int i = 0; i < s.Length - 1; i++) {
                s = s.Substring(1) + s[0];
                yield return s;
            }
        }
    }
}

using System;
using System.Linq;

namespace CyclicNumberApp {
    class Program {
        static void Main(string[] args) {
            for (var multiplier = 2; multiplier < 10; multiplier++) {
                Console.WriteLine($"{multiplier}倍");
                CyclicNumber cn = new CyclicNumber(multiplier);
                var ans = cn.Solve().ToList();
                foreach (var num in ans) {
                    Console.WriteLine($"{num} * {multiplier} = {num * multiplier}");
                }
                if (ans.Count == 0) {
                    Console.WriteLine("見つかりませんでした");
                }
            }
            Console.WriteLine("end.");
        }
    }
}

さらっと解説

CyclicNumberクラス

CyclicNumberクラスは、n倍して桁が巡回する自然数を求めます。この問題を解く本質部分を担当しています。
求める自然数は、計算時間を考慮して、1〜999,999までの自然数に限定しました。

n倍した数が、nを巡回した数(複数個存在)の中にあるかどうかをしらみつぶしに調べる、という実に当たり前のやり方です。
ただ、高速化のため、泥臭い判定処理を入れています。

コンストラクタ

コンストラクタにn倍する値(乗数:multiplier)を与えています。

Solveメソッド

multiplier倍して巡回する自然数を列挙するpublicメソッドです。multiplierの値はコンストラクタの引数で受け取っています。
泥臭く、1から始めて、2,3,4と一つずつ巡回数かどうかを調べています。巡回数ならば、yield returnで列挙しています。

IsCyclicNumberメソッド

引数numが巡回数かどうかを調べています。
高速化のため、泥臭い判定処理を入れています。詳しくはソースコードを読んでください。

GetCyclicsメソッド

引数numを巡回させた数を文字列に変換し列挙しています。

Programクラス

Mainメソッドで、CyclicNumberクラスを使って、2倍から9倍までの解を求めています。
特にむずかしいことはやっていません。

結果

以下結果です。

2倍
142857 * 2 = 285714
285714 * 2 = 571428
428571 * 2 = 857142
3倍
142857 * 3 = 428571
153846 * 3 = 461538
230769 * 3 = 692307
285714 * 3 = 857142
307692 * 3 = 923076
4倍
102564 * 4 = 410256
128205 * 4 = 512820
142857 * 4 = 571428
153846 * 4 = 615384
179487 * 4 = 717948
190476 * 4 = 761904
205128 * 4 = 820512
230769 * 4 = 923076
238095 * 4 = 952380
5倍
142857 * 5 = 714285
6倍
142857 * 6 = 857142
7倍
見つかりませんでした
8倍
見つかりませんでした
9倍
109890 * 9 = 989010

なんとすべてが6桁です。
結果を眺めてみると、142857は、2倍、3倍、4倍、5倍、6倍のすべての解になっています。
それと、2倍の結果に出てくる6つの数は、3~6倍の結果のいずれかに表れています。
面白いですね。


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