各位来看看：用高中数学知识：首位为 9 的数有几个？

[panchina]

前几天培训时提出的一个问题：
9, 9^1, 9^2, ... 9^2016

首位为 9 的数有几个？
思路是是什么？
方法如何实现？

ps:不能一个个排查
pps:说用高中数学知识就可以了 =_=!

[Dannytmp]

难点在于高中知识的范围啊

[shshilmh]

http://lmgtfy.com/?q=%E6%AC%A1%E6%96%B9%E7%9A%84%E9%A6%96%E4%BD%8D%E6%95%B0

[ffffwh]

9 * (10 - 1)^n, for n = 0 -> 2016 。看(10-1)^n 怎么给出首位为 1 的？

[Kirscheis]

这个用得着高中知识吗。。初中差不多了，考点对数换底公式啊。

10^([log(9^n)]+1) > 9^n > 9^[log(9^n)]
解不等式，得 log(9) < nlog(9)-[nlog(9)] < 1
也就是说 nlog(9) 的小数部分大于 log(9) 就可以了。列等差数列，做一个除法，问题结束。

[panchina]

@ffffwh 这不就是相当于一个个排查了么？

[lightening]

@Kirscheis 能不能解释一下为什么 10^([log(9^n)]+1) > 9^n > 9^[log(9^n)] 代表首位为 9 ？

[Kirscheis]

@lightening
p 位整数首位为 9 的充要条件是 10^p > x >= 10^(p-1)，这里因为 9 的幂次个位不可能为 0 ，故条件退化为 10^p > x > 10^(p-1)
又因为任意 p 位整数 n 可化为级数 ∑(a,i) aᵢ*(10^i)，故 n 的位数 p = [log(9^n)]+1
上面两个条件合起来就是了

[Kirscheis]

@lightening
手机打字变量名打错了。。漏了个条件
p 位整数 x 首位为 9 的充要条件是 10^p > x >= 10^(p-1)，这里因为 9 的幂次个位不可能为 0 ，故条件退化为 10^p > x > 10^(p-1)
又因为任意 p 位整数 x 可化为级数 ∑(a,i) aᵢ*(10^i)，故 n 的位数 p = [log(x)]+1 ，题设中的 x = 9^n ，故 p = [log(9^n)]+1
上面两个条件合起来就是了

[Kirscheis]

@lightening
报警，发出去发现还有一处没改。。请忽略上面两条
p 位整数 x 首位为 9 的充要条件是 10^p > x >= 10^(p-1)，这里因为 9 的幂次个位不可能为 0 ，故条件退化为 10^p > x > 10^(p-1)
又因为任意 p 位整数 x 可化为级数 ∑(a,i) aᵢ*(10^i)，故 x 的位数 p = [log(x)]+1 ，题设中的 x = 9^n ，故 p = [log(9^n)]+1
上面两个条件合起来就是了

[luban]

http://blog.udn.com/ivan5chess/1636470

这里有个很巧妙的解法，但是要知道最后一个，也就是 9 的 2016 次方首位是不是 9

[luban]

上面说错了，应该是要知道最大的一个 9 的 n 次方首位是 9 才行

[luban]

经过少量测试， 9^2011 的首位是 9 ， 9^2011 长度是 1919 ，也就是 2011-1919=92 个

[billion]

9^1---> 1 个 9 开头
9^2--->1 个 9 开头
9^3--->11 个 9 开头，分别为:9, 90,91,92,93,94,95,96,97,98,99 ->1+10
9^4 --->111 个 9 开头->1+10+100
……
9^2016 ---> 1 + 10 +100 + 1000 + …… + 10 …… 2015 = 11111111 …… 1111 （ 2015 个 1 ）个 9 开头

[yuuki]

算出来是 21 个，不知道对不对🐸
用到了科学计数法，对数和不等式的知识
9^n=a·10^(n-1)，满足首位为 9→9≤a<10 ，解不等式得 1≤n≤21

[qqmishi]

想了半天才发现是要求有几个，，，
首位是 9 意味着本次运算没有进位，所以看看位数与指数的差就行了，理论上只需要算 9^2016 的位数

实际上差不多每隔 22 或者 21 就会出现一个首位是 9 的

[loading]

完全不懂……

[zingl]

2016*(1-log9)

[lightening]

@Kirscheis
谢谢。这里 [ ] 是取整数的意思吗？

[jimages]

@Kirscheis 有误，应为， p 位整数 x 首位为 9 的充要条件是 10^p > x >= 10^p - 10^(p-1)

[jimages]

@jimages 于是 变形 10^p > x >= 9*10^(p-1) 这里在 x 为 9 的时候需要取等号，因此不能退化。

[ceoimon]

@luban 这个思路太吊了

[MCVector]

首位肯定是个循环数组，找到循环的周期就行了。

[maomaomao001]

首位为 9 的数不是有无数个吗？
9
9x
9xx
9xxx

[Kirscheis]

@jimages 抱歉，是有点问题。吃晚饭的时候看见题目随手打的，脑抽忘了乘 9 。果然口算不怎么靠谱。不过基础思路就是取对数换底，把常数替换一下就行了。 n=1 的时候确实不能退化了，不等式里的小于应该换成小于等于。
楼上已经出现更好的算法了，我考虑过 9 开头的数是否前一个一定 1 开头后一个一定进位，但是当时吃着饭感觉证明比较麻烦，没想到挺容易的。

[panchina]

@luban bingo~

[panchina]

@lightening 是的

[yszx]

@luban 并不需要知道最后一个数是否开头是 9 ，因为他的原理是 位数差=出现重复位数的次数=9 开头的次数，这个思路太强大了···

[zingl]

不需要知道最后一个数开头是什么，但需要知道最后一个数有多少位，也就是要知道 log(9^k)=k*2*log3 的整数部分，所以告诉你了 log3 等于多少

链接里的解是不完全的，因为除了要证明“若 9 的 a 次方首位數字為 9, 那麼 9 的 a-1 次方位數與 9 的 a 次方位數相同(這是明顯的)”，还要证明对于任意 b 位数的自然数，其中至少有 1 个是 9 的整数次幂（引号内容表明可以有 2 个，引申可证得不会有 2 个以上），否则解法是不成立的。

最后就是个抽屉原理了。

[panchina]

@zingl 第二个证明只需要考虑： 10^(n-1) < 9^n <10^n

[jimages]

@Kirscheis 我没有收到你的提醒，是不是你被降级了？

[Rorysky]

@Kirscheis 还厉害 我初中肯定不会这些。。。

疑问 对于一个 2 位整数 X ， X 首位为 9 的 条件是 100<X<10 ？

@lightening

[zingl]

@panchina n 值大了以后中间就肯定不是 9^n 了

首先要证明：对任意正整数 i ， 10^i < 9^j < 10^(i+1)，至少有 1 个、至多有 2 个整数解

然后要证明： 当且仅当 有 2 个解时，大的解是 9 开头

那么对于 9^1 至 9^k ， k 个解分布于 10^1 至 10^(log(9^k))，那么其中上述两个解的情况出现的次数 k-log(9^k)=k(1-log9) 见 17 楼

精确解要考虑 10^0 = 9^0 < 9^1 < 10^1 的特例加 1 ，除此以外， 9^i=10^j 无正整数解，所以上面的不等式不需要考虑相等

[Kirscheis]

@Rorysky 昨天吃饭的时候打的，手抽少乘了个 9 ，见 24 楼。两位整数首位为 9 条件是 100>x>=90 。

[Kirscheis]

@jimages 多谢提醒，很有可能。以前在 V2 发非法爬虫被封过

[whh945atsyzx]

难道不是无数个吗....在 9 后面无限加数字...

[panchina]

@whh945atsyzx 9^n 指的是 9 的 n 次方幂

[snsd]

@Kirscheis 你们那边初中就讲对数的知识了？

[programgou]

把问题推广开来， w,w^1,w^2,w^3,....,w^n 首位为 w 的有几个？

[rushcheyo]

@snsd 对啊，初一上一进来第一课就是对数换底公式。

[snsd]

@rushcheyo 你那是什么地方？讲得那么先进。我这到了高一才讲的对数

[rushcheyo]

@snsd 安徽芜湖。