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

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

More than 1 year has passed since last update.

この記事は、もう数十年前に出版された『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を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で公開したものを加筆・修正したものです。

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