トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Cマガ電脳クラブ(第069回) 割り切れ魔数?

問題

3816547290
この大町数 (0から9までの10個の数字が1度ずつ登場する数) は、
おもしろいことに左端からN桁を切り出したとき、その数がNで割り切れる。

たとえば3816は4で,3816547は7で割り切れるのだ。
このような大町数はこれひとつしかない。

さて、今回は「大町」の条件を取り外してみよう。
つまり、「どこにどんな数字を使ってもよい」ということにしたら、
「左端からN桁を切り出した数が、いつもNで割り切れる数」はどこまで大きくできるだろうか。
ここでは、10進法以外は考えないことにする。


ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int KetaSuu;
        internal int[] ValArr;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.KetaSuu = 1;
        for (int I = 1; I <= 9; I++) {
            WillPush.ValArr = new int[] { I };
            stk.Push(WillPush);
        }

        int MaxKeta = 0;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (MaxKeta <= Popped.KetaSuu) {
                MaxKeta = Popped.KetaSuu;
                var sb = new System.Text.StringBuilder();
                Array.ForEach(Popped.ValArr, X => sb.Append(X));
                Console.WriteLine("{0}桁の解{1}を発見", Popped.KetaSuu, sb.ToString());
            }

            for (int I = 0; I <= 9; I++) {
                WillPush.KetaSuu = Popped.KetaSuu + 1;
                WillPush.ValArr = Popped.ValArr.Concat(new int[] { I }).ToArray();
                if (IsBaisuu(WillPush.ValArr, WillPush.KetaSuu))
                    stk.Push(WillPush);
            }
        }
    }

    static bool IsBaisuu(int[] pValArr, int pWarukazu)
    {
        //余りの法則その1 (A+B)%C = A%C + B%C
        //余りの法則その2 (A*B)%C = (A%C) * (B%C)
        int SumVal = 0;
        for (int I = 0; I <= pValArr.GetUpperBound(0); I++) {
            SumVal *= 10;
            SumVal += pValArr[I];
            SumVal %= pWarukazu;
        }
        return SumVal == 0;
    }
}


実行結果

省略
20桁の解96685896604836004260を発見
21桁の解966858966048360042609を発見
22桁の解9668589660483600426096を発見
22桁の解9068584050968400006092を発見
22桁の解8468047260244656728072を発見
22桁の解7412580810843600420006を発見
22桁の解7264565640241056724082を発見
23桁の解72645656402410567240820を発見
23桁の解40285216807290082800921を発見
24桁の解402852168072900828009216を発見
24桁の解360852885036840078603672を発見
25桁の解3608528850368400786036725を発見


解説

余りの法則その1 (A+B)%C = A%C + B%C
余りの法則その2 (A*B)%C = (A%C) * (B%C)
を使って、余りを求めてます。

Decimal型を使用したソースは、第130回 こだ割り数で扱ってます。
(第069回と第130回は、同じ問題であるため)