Cマガ電脳クラブ(第055回) カウント・ワン

問題

1､2､3・・・Nまでの数を並べて､その中に1という数字がいくつあるかを数える｡
つまり､N=1､2､3・・・9までは数字の1は合計1個､N=10で2個､N=11で4個というように数えるわけだ｡

さて､Nまでの数を並べたら､数字の1がちょうどN個含まれていた｡このようなNが全部でいくつあるのだろうか｡
個数を調べてほしい｡

最初にあてはまるのはN=1ですよ､念のため｡

ソース

using System;

class Program
{
    const int Jyougen = 1999999999;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        long SumCnt = 0;
        int AnsCnt = 0;

        int CurrCnt = 0;
        for (int I = 1; I <= Jyougen; I++) {
            if (I % 10 == 0) CurrCnt = DeriveOneCnt(I);
            else if (I % 10 == 1) CurrCnt++;
            else if (I % 10 == 2) CurrCnt--;

            SumCnt += CurrCnt;
            if (SumCnt == I) Console.WriteLine("{0}で一致({1}個目)。経過時間={2}",
                I, ++AnsCnt, sw.Elapsed);
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //pTarget.ToString().Count(X => X == '1')の高速化版
    static int DeriveOneCnt(int pTarget)
    {
        int OneCnt = 0;
        do {
            int wkInt = pTarget % 10;
            if (wkInt % 10 == 1) OneCnt++;
        } while ((pTarget /= 10) > 0);
        return OneCnt;
    }
}

実行結果

省略
535000000で一致(69個目)。経過時間=00:00:34.1693382
535000001で一致(70個目)。経過時間=00:00:34.1738631
535199981で一致(71個目)。経過時間=00:00:34.1906055
535199982で一致(72個目)。経過時間=00:00:34.1950024
535199983で一致(73個目)。経過時間=00:00:34.1994795
535199984で一致(74個目)。経過時間=00:00:34.2035828
535199985で一致(75個目)。経過時間=00:00:34.2078021
535199986で一致(76個目)。経過時間=00:00:34.2122962
535199987で一致(77個目)。経過時間=00:00:34.2169194
535199988で一致(78個目)。経過時間=00:00:34.2212448
535199989で一致(79個目)。経過時間=00:00:34.2254373
535199990で一致(80個目)。経過時間=00:00:34.2296649
535200000で一致(81個目)。経過時間=00:00:34.2341632
535200001で一致(82個目)。経過時間=00:00:34.2383934
1111111110で一致(83個目)。経過時間=00:01:11.3469896
経過時間=00:02:11.1812856

解説

1桁の数での1の数は、1個
2桁の数での1の数は、19個(10から19の2桁目の分で10、10から90の1桁目の分で9)
3桁の数での1の数は、280個
                    100から199の3桁目の分で100、
                    100から900の2桁の数の分で9*19 = 171
                    100から900の1桁の数の分で9* 1 =   9
4桁の数での1の数は、3700個
                    1000から1999の4桁目の分で1000、
                    1000から9000の3桁目の分で9*280 = 2520
                    1000から9000の2桁目の分で9* 19 =  171
                    1000から9000の1桁目の分で9*  1 =    9

1桁の数の最大値は、9
1の数は1 (累計は1)
2桁の数の最大値は、99
1の数は19 (累計は20)
3桁の数の最大値は、999
1の数は280 (累計は300)
4桁の数の最大値は、9999
1の数は3700 (累計は4000)
5桁の数の最大値は、 99999
1の数は46000 (累計は50000)
6桁の数の最大値は、  999999
1の数は550000 (累計は600000)
7桁の数の最大値は、   9999999
1の数は6400000 (累計は7000000)
8桁の数の最大値は、    99999999
1の数は73000000 (累計は80000000)
9桁の数の最大値は、     999999999
1の数は820000000 (累計は900000000)
10桁の数の最大値は、      9999999999   ← ここに注目！！！
1の数は9100000000 (累計は10000000000)  ← ここに注目！！！
11桁の数の最大値は、        99999999999
1の数は100000000000 (累計は110000000000)
12桁の数の最大値は、         999999999999
1の数は1090000000000 (累計は1200000000000)
13桁の数の最大値は、          9999999999999
1の数は11800000000000 (累計は13000000000000)
14桁の数の最大値は、           99999999999999
1の数は127000000000000 (累計は140000000000000)
15桁の数の最大値は、            999999999999999
1の数は1360000000000000 (累計は1500000000000000)

1の数は、各桁で最上位桁が1の時が最も増加数が多く
最上位桁が2から9で増加数が一定なのは明らかです。

10桁の最大値の9999999999で1の数の累計が、その数の値を超え、11桁以降も同様であること。

10桁目では、最上位桁が1の時に、その数の値を超え、
以後、最上位桁が2から9での時には、1の数の累計が、その数の値を超えることはない。

と導いて、上限を1999999999としてます。