2006年3月に休刊となった月刊Cマガジン（ソフトバンククリエイティブ発行）に「Cマガ電脳クラブ」という連載コーナーがありました。そこで見た問題。
3435という数は、1桁ずつに分けて、それぞれの数を自分と同じ数でべき乗して足し合わせると、元の数である3435になる。
3435 ＝ 3の3乗 + 4の4乗 + 3の3乗 + 5の5乗
このような数を“開き直り数”と呼ぶことにする。ちょっと考えれば1(=1の1乗)もこの種の数であることがわかる。
では1以上の整数で、この1と3435以外の開き直り数をすべて見つけていただきたい。
ただし、ここでは0の0乗は0とする。
CマガジンはおもにC言語を扱っていた情報誌です。しかしここではC#をつかって解くことにします。
考え方
まず問題文に「すべて見つけていただきたい」とあるので解は有限であることがわかります。ではどうやって解の候補を有限個に絞り込めばいいのでしょうか？
まず「1桁ずつに分けてそれぞれの数を自分と同じ数でべき乗して足し合わせる」という操作を「開き直り操作」と定義します（あくまでも個人的な定義）。
するとある自然数に開き直り操作をすると得られる数は以下のメソッドで得られます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
long GetHirakinaori(long value) { string str = value.ToString(); char[] vs = str.ToArray(); long ret = 0; foreach(char c in vs) { string s = new string(c, 1); int i = int.Parse(s); ret += GetPow(i); } return ret; } int GetPow(int i) { if(i == 0) return 0; // 問題文でそのように定義されているので else return (int)Math.Pow(i, i); } |
それからi桁の自然数の最大値は
となり、最小値は
となります。
またi桁の自然数に開き直り操作をして得られる数の最大値は
なり、最小値は 1 となります。
そこで
であったり
である場合は、開き直り数は存在しないということになります。
とは
なので、これを満たすiは存在しません。そこで
が存在するかどうかを調べます。
を満たすiがあるならi桁以上の自然数には開き直り数が存在しないことになります。
実際に調べてみましょう。
|
1 2 3 4 5 6 |
// i * Math.Pow(9, 9) i桁の開き直り数の最大値 // Math.Pow(10, i)-1 i桁の数の最大値 int i = 1; while(!(i * Math.Pow(9, 9) < Math.Pow(10, i) - 1)) i++; |
これを実行するとループを抜けたときに i = 10 になっていることがわかります。10桁以上の数には開き直り数は存在しないことがわかります。
全部調べるのは効率が悪すぎ
上限がわかったのであとはループ文を使えば答えがわかるかもしれません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
void Method() { // 見つかった開き直り数を格納するためのリスト List<long> ret = new List<long>(); for(long value = 1; value < 999999; value++) { if(IsHirakinaori(value)) ret.Add(value); } foreach(long l in ret) { // 得られた答えを取り出して表示する } } bool IsHirakinaori(long value) { string str1 = value.ToString(); char[] vs1 = str1.ToArray(); long val = 0; foreach(char c in vs1) { if(c == '0') val += GetPow(0); if(c == '1') val += GetPow(1); if(c == '2') val += GetPow(2); if(c == '3') val += GetPow(3); if(c == '4') val += GetPow(4); if(c == '5') val += GetPow(5); if(c == '6') val += GetPow(6); if(c == '7') val += GetPow(7); if(c == '8') val += GetPow(8); if(c == '9') val += GetPow(9); // オーバーしたら明らかに違う if(val > value) return false; } if(val == value) return true; else return false; } |
しかしこれは処理に時間がかかりそうです。ためしに 1 ～ 999999（6桁）でやってみましたが、1分くらいかかりました。9桁の数までやろうとすると相当時間がかかるのではないでしょうか？
そこでもっと短い時間でやる方法を考えます。
上記のやりかたでは同じ数字の組み合わせでできる数を何度も検証していることになります。3桁に限定すると、123 / 132 / 213 / 231 / 312 / 321 に対して開き直り数操作をするとすべて同じ値(1+4+27=32)になります。
そこでまず「桁の組み合わせ」を考えて、これが開き直り数の条件を満たすかを考えたほうがよさそうです。
0～9の重複組み合わせを考える
10桁で0～9の10種類の数字で構成される組み合わせを考えます。同じ数字を同じ回数使うのであればそれで1つと考えます。
1234 と 1324は同じと見なします。また1231と1223は2を使っている回数が違うので別物として見なします。
重複組み合わせをC#で簡単にできないかと探したところ、こんなページが見つかりました。
C#:n個の要素からk個を選ぶ組合せを列挙する – Qiita
ここで紹介されているコードをパクらせて参考にさせていただきましょう。
ちょっとだけ手直ししています。引数を減らしたのと組み合わせでも重複はカウントしないといけないのでその部分を変更しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items, int k) { if(k == 1) { foreach(var item in items) yield return new T[] { item }; yield break; } foreach(var item in items) { var leftside = new T[] { item }; // 順列ではなく組み合わせなのでitem よりも前のものを除く var unused = items.SkipWhile(e => !e.Equals(item)).ToList(); foreach(var rightside in Enumerate(unused, k - 1)) { yield return leftside.Concat(rightside).ToArray(); } } } |
これを使えば、9桁の重複組み合わせを取得することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void Method() { int n = 10; int k = 9; var nums = Enumerable.Range(0, n).ToArray(); var combinations = Enumerate(nums, k).ToList(); foreach(var elem in combinations) { // 得られた重複組み合わせに対する処理 } } |
では得られた重複組み合わせに対してどのような処理をすればよいのでしょうか？
まず開き直り操作をして得られる値を計算します。そして得られた重複組み合わせを並べ替えて開き直り操作をして得られる値に一致するものがあるかどうか調べます。
重複組み合わせを並べ替えて開き直り操作をして得られる値に一致するものがあるかどうかは、以下の方法でわかります。
これで文字列をつくる
0は消去する
ふたつの文字列が一致するかどうか？
これを判定するのが自作メソッド bool IsHirakinaori(long value, int[] ints)です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
void Method() { int n = 10; int k = 9; var nums = Enumerable.Range(0, n).ToArray(); var combinations = Enumerate(nums, k); foreach(var elem in combinations) { long l = GetHirakinaori(elem); if(l > 0 && IsHirakinaori(l, elem)) Console.WriteLine(l); } } /// <summary> /// 第一引数の配列を並べ替えることで第二引数に一致するものがあるかどうかを調べる /// </summary> bool IsHirakinaori(long value, int[] ints) { string str = value.ToString(); char[] vs11 = str.ToArray(); char[] vs12 = vs11.OrderBy(x => x).ToArray(); string str1 = new string(vs12); str1 = str1.Replace("0", ""); string[] strs = ints.OrderBy(x => x).Select(x => x.ToString()).ToArray(); string str21 = string.Join("", strs); string str2 = str21.Replace("0", ""); if(str1 == str2) return true; else return false; } |
実行結果
3435
438579088
1以上の整数で1と3435以外の開き直り数は438579088だけでした。
