この記事は、もう数十年前に出版された『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を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の値はコンストラクタの引数で受け取っています。
泥臭く、１から始めて、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
なんとすべてが６桁です。
結果を眺めてみると、142857は、2倍、3倍、4倍、5倍、6倍のすべての解になっています。
それと、2倍の結果に出てくる６つの数は、3～6倍の結果のいずれかに表れています。
面白いですね。
この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。