Cマガ電脳クラブ(第022回) 杉算

問題

材木をFig.1のように積んだ時、上辺と下辺を知ってその総数を出す計算を杉算というらしい。

さて広瀬昌一氏が発表した特異杉算は、たとえば
1+2+3+4+5=15
33+34+35+…+86+87+88=3388
のような、nからmまで合計した結果がnとmを単に並べただけになるというものだ。

さて問題だが、「mを5桁まで」としたときの、この種の特異杉算は全部でいくつみつかるだろうか。

Fig.1

ソース

using System;

class Program
{
    static void Main()
    {
        int AnswerCnt = 0;
        //末項のループ
        for (int m = 1; m <= 99999; m++) {
            int n;
            if (SearchAnswer(out n, m)) {
                long SumVal = (long)(n + m) * (m - n + 1) / 2;
                Console.WriteLine("解{0,2}を発見。n={1,5},m={2,5},SumVal={3,10}",
                    ++AnswerCnt, n, m, SumVal);
            }
        }
    }

    //mを固定として、解を2分法で探す
    static bool SearchAnswer(out int n, int pTargetM)
    {
        int BekiJyousuu = GetBekiJyousuu(pTargetM);

        int LeftVal = 1;
        int RightVal = pTargetM - 1;
        int MidVal;

        while (LeftVal <= RightVal) {
            MidVal = (LeftVal + RightVal) / 2;

            //n*(n - 1 + 2*10の(mの桁数乗)) = m*m - m

            long wkSahen = (long)MidVal * (MidVal - 1 + 2 * BekiJyousuu);
            long wkUhen = (long)pTargetM * pTargetM - pTargetM;
            if (wkSahen == wkUhen) {
                n = MidVal;
                return true;
            }
            if (wkSahen < wkUhen) LeftVal = MidVal + 1;
            else RightVal = MidVal - 1;
        }
        n = 0;
        return false;
    }

    //mを引数として、10の(mの桁数乗)を返す
    static int GetBekiJyousuu(int pTargetM)
    {
        if (pTargetM < 10) return 10;
        if (pTargetM < 100) return 100;
        if (pTargetM < 1000) return 1000;
        if (pTargetM < 10000) return 10000;
        return 100000;
    }
}

実行結果

解 1を発見。n=    1,m=    5,SumVal=        15
解 2を発見。n=    2,m=    7,SumVal=        27
解 3を発見。n=    4,m=   29,SumVal=       429
解 4を発見。n=   13,m=   53,SumVal=      1353
解 5を発見。n=   18,m=   63,SumVal=      1863
解 6を発見。n=   33,m=   88,SumVal=      3388
解 7を発見。n=   35,m=   91,SumVal=      3591
解 8を発見。n=    7,m=  119,SumVal=      7119
解 9を発見。n=   78,m=  403,SumVal=     78403
解10を発見。n=  133,m=  533,SumVal=    133533
解11を発見。n=  178,m=  623,SumVal=    178623
解12を発見。n=  228,m= 2148,SumVal=   2282148
解13を発見。n=  273,m= 2353,SumVal=   2732353
解14を発見。n=  388,m= 2813,SumVal=   3882813
解15を発見。n=  710,m= 3835,SumVal=   7103835
解16を発見。n= 1333,m= 5333,SumVal=  13335333
解17を発見。n= 1701,m= 6076,SumVal=  17016076
解18を発見。n= 1778,m= 6223,SumVal=  17786223
解19を発見。n= 2737,m= 7889,SumVal=  27377889
解20を発見。n= 3273,m= 8728,SumVal=  32738728
解21を発見。n= 3563,m= 9163,SumVal=  35639163
解22を発見。n= 3087,m=25039,SumVal= 308725039
解23を発見。n= 3478,m=26603,SumVal= 347826603
解24を発見。n=12488,m=51513,SumVal=1248851513
解25を発見。n=13333,m=53333,SumVal=1333353333
解26を発見。n=14208,m=55168,SumVal=1420855168
解27を発見。n=17778,m=62223,SumVal=1777862223
解28を発見。n=31463,m=85338,SumVal=3146385338
解29を発見。n=36993,m=93633,SumVal=3699393633

解説

初項をn 末項をmとすると、
等差数列の和 = (初項 + 末項) * 項数 / 2 なので
数列の和 = (n+m)*(m-n+1) / 2

特異杉算での計算結果 = 10の(mの桁数乗)*n + m

等差数列の和と、特異杉算での計算結果が等しくなるので

(n+m)*(m-n+1) /2 = 10の(mの桁数乗)*n + m
(nm-n*n+n+ m*m-nm+m) = 2*10の(mの桁数乗)*n + 2*m
(-n*n + n + m*m + m) = 2*10の(mの桁数乗)*n + 2*m
-n*n + n - 2*10の(mの桁数乗)*n = -m*m - m + 2*m
-n*n + n - 2*10の(mの桁数乗)*n = -m*m + m
n*n - n + 2*10の(mの桁数乗)*n = m*m - m

nで因数分解して、
n*(n - 1 + 2*10の(mの桁数乗)) = m*m - m

左辺はnに対して単調増加であるため、
(nはnに対して単調増加であり、(n - 1 + 2*10の(mの桁数乗))もnに対して単調増加のため、これらの積も単調増加)
2分法を使用して、解を探してます。