N-Parastic Number とは
ある正の整数 A を N 倍した値と、Aを右へ一桁分ローテートシフトした値が等しい数を「N-Parastic Number」と言います。 ただし、1<=N<=9 とします。
例えば、N=4 の時、102564 は N-Parastic Numberとなります。
102564 * 4 = 410256
となり、102564を右に1桁分ローテートシフトした値と、410256が等しくなります。
ところで、Parastic Numberは日本語でどう訳せばいいんでしょうか。 勝手に「寄生数」と訳しましたが、どなたか知っていれば教えてください。
解き方を考える
N = 4 で考えてみます。求める数Aの 1桁目が4であると仮定しましょう。つまり、
_____4 * 4 = ____6
となります。
この右辺の数が、数Aを右ローテートした値に等しいのだから、求める数Aの下２桁は 64 です。
２桁目がわかれば、同じように 64 を4倍して 256 が得られますから
_____64 * 4 = ____56
となり、これからAの 3桁目が 5であることがわかります。
実際には 64を4倍するのではなく、1桁目を 4 倍したときに得られた繰り上がり数である 1 を記憶しておき、
この１と 6を4倍した値24を加え、25を求めます。この1桁目の5が求める3桁目の値です。
ここまでで、求める数Aが ____564 であることがわかりました。
これを 4桁、5桁... と求めていきます。
_____564 * 4 = ____256
____2564 * 4 = ___0256
___02564 * 4 = __10256
__102564 * 4 = _410256 ここで終わり
そして、上記右辺の最上位桁の数が 4 で、繰り上がりの数が 0 になるまで繰り返します。
このときの左辺の数が、求める数Aです。
こうすれば、求める数Aが巨大な数であっても対応できます。
手順を言葉で理解するよりも、実際に紙と鉛筆をつかって手計算してみたほうが、 すぐに理解できると思います。
C#で最小のN-Parastic Numberを求める。
WikipediaのParasitic numberを見てみると、「Smallest n-parasitic numbers」として、1<=N<=9の最小のN-Parasitic Numbersが掲載されています。これをC#で求めるコードを書いてみたいと思います。
ちなみにこの「Smallest n-parasitic numbers」は、Dyson numbersという数学パズルとしても知られているそうです。
例えば、4-Parastic Numberを求めるには、上で示した手順で1桁目を1から9までに当てはめていって、最小値を求めればよいのですが、もしかしたら、1桁目が1の時は、4-Parastic Numberは存在しないかもしれません。そうなると、上で示した処理を永遠と続けることになり、いつまでたっても答えが求まらないことになります。
そのため、プログラムでこれに対応するにはちょっとした工夫が必要になります。
まず、1桁の整数Aに対して、1桁目が1から9までの4-Parastic Numberがあるかどうかを調べます。見つかれば、これが最小の4-Parastic Numberです。（複数見つかる可能性もあるので、そこも考慮します）。
見つからなければ、2桁の整数Aに対して同じ処理をします。見つからなければ、3桁の整数、4桁の整数...と調べていくことになります。
この考えをコードに落としたのが次に示すコードです。
using System;
using System.Collections.Generic;
using System.Linq;
namespace Gushwell.Etude {
class Program {
static void Main(string[] args) {
var pn = new NParasiticNumber();
for (int n = 1; n <= 9; n++) {
var ans = pn.Get(n);
Console.WriteLine("{0}: {1}", n, ans);
}
}
}
// n 倍すると右へローテートシフトする数を求める
class NParasiticNumber {
public string Get(int n) {
var candidates = Candidates(n).ToArray();
var min = candidates.Min(s => s[0]);
return candidates.First(x => x[0] == min);
}
public IEnumerable<string> Candidates(int n) {
var found = false;
for (int digits = 1; digits < int.MaxValue; digits++) {
for (int i = 1; i <= 9; i++) {
var candidate = GetCandidate(n, i, digits);
if (candidate != null) {
yield return candidate;
found = true;
}
}
if (found == true)
break;
}
}
// 1桁目がfirstDigitであるn-Parasitic_numberを求める。
// ただし、最大桁はmaxDigitsまでとし、これを超えたら、nullを返す。
private string GetCandidate(int n, int firstDigit, int maxDigits) {
int b = firstDigit; // 求める数値の現時点での最上位桁の数
string r = b.ToString(); // 求める数を文字列として保持
int carry = 0; // 繰り上がりの数
while (true) {
// 例えば N=6,firstDigit=4の場合、最初のループでは、
int a = b * n + carry; // a <- 24 (= 6 * 4 + 0)
int m = a % 10; // m <- 4 (= 24 % 10)
carry = a / 10; // carry <- 2 (= 24 / 10)
b = m; // 現時点での最上位の桁の数は 4 である。
if (carry == 0 && b == firstDigit && r[0] != '0')
break;
r = b.ToString() + r;
if (r.Length > maxDigits)
return null;
}
return r;
}
}
}
実行結果
以下のようになり、Wikipediaと同じ結果となりました。
1: 1
2: 105263157894736842
3: 1034482758620689655172413793
4: 102564
5: 142857
6: 1016949152542372881355932203389830508474576271186440677966
7: 1014492753623188405797
8: 1012658227848
9: 10112359550561797752808988764044943820224719
この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。