朋友问了一道题目：
统计从1至400亿之间的自然数中含有多少个1？
比如1-11中，有1，10，11这三个自然数有4个1

不知道你拿到这样的题目会怎样去算？
也许有同学会发现，用排列组合可以算，具体的算法不在这里列出了，我想说的是一种比较特殊的解法：

for (var i = 4; i < 40000; i*=10)
{
    var count = 0;
    for (var t = 0; t < i; t++)
    {
        count += t.toString().replace(/[^1]/g, "").length;
    }
    document.write(i + ":" + count + "<br />");
}

看到上面的代码，你也许会觉得很囧，这算是什么，难道是暴力解法？
别急，往下看：

4:1    S(0)
40:14    S(1)
400:180    S(2)
4000:2200    S(3)

也许有同学已经发现了，神奇的通项公式：
S(n) = (10+4*n)*10^(n-1) (n>=0)

所以：
(function(k){
    var i = 40;
    var n = 1;
    while(n <= k) {
        var x = (10 + 4 * n) * Math.pow(10,n-1);
        document.write(i + ":" + x + "<br/>");
        i*=10, n++;
    }
})(10);

得出答案：

40:14
400:180
4000:2200
40000:26000
400000:300000
4000000:3400000
40000000:38000000
400000000:420000000
4000000000:4600000000
40000000000:50000000000

那么结束了吗？没有。
不知道有没有同学去想怎么证明这个通项公式对于足够大的N仍然成立？
数学归纳法证明如下：

证明：
    p(0) = 4，sum(0) = (10 + 4 * 0) * 10^(0-1) = 1 成立
    1) 假设当 n = k 时， sum(k) = (10+4*k)*10^(k-1)
    2) 当 n = k + 1 时，
    p(k+1) = p(k) * 10， 所以
    sum(k+1) = 10 * sum(k) + 4 * 10^k
    = 10 * (10 + 4 * k) * 10^(k-1)    (将新增的位数放在最末一位，末位从0取到9一共10次）
        + 4 * 10^k                    (末位为1的补加）
    = (10 + 4 + 4 * k)) * 10 ^ k
    = (10 + 4 * (k+1))) * 10 ^ ((k+1)-1)
    因此综合1) 2)，对任意自然数n，p(n) = 4 * 10 ^ n，1的个数为sum(n) = (10+4*n)*10^(n-1)
证毕

想到求通项公式解题的思路的同学，应该在“数感”方面有些天赋吧？
用这个解法，比用排列组合的公式去算要简单很多。

当然，想到用排列组合以及最后对通项公式想到用数学归纳法证明的同学，有比较好的数学基础……