这是一个创建于 3103 天前的主题，其中的信息可能已经有所发展或是发生改变。
前几天培训时提出的一个问题：
9, 9^1, 9^2, ... 9^2016
首位为 9 的数有几个？
思路是是什么？
方法如何实现？
ps:不能一个个排查
pps:说用高中数学知识就可以了 =_=!
9, 9^1, 9^2, ... 9^2016
首位为 9 的数有几个？
思路是是什么？
方法如何实现？
ps:不能一个个排查
pps:说用高中数学知识就可以了 =_=!
 |
1
Dannytmp 2016-05-11 16:38:46 +08:00
难点在于高中知识的范围啊
|
 |
2
shshilmh 2016-05-11 17:15:52 +08:00
|
 |
3
ffffwh 2016-05-11 17:57:03 +08:00  1
9 * (10 - 1)^n, for n = 0 -> 2016 。看(10-1)^n 怎么给出首位为 1 的？
|
 |
4
Kirscheis 2016-05-11 18:00:03 +08:00 via iPhone 1
这个用得着高中知识吗。。初中差不多了，考点对数换底公式啊。
10^([log(9^n)]+1) > 9^n > 9^[log(9^n)] 解不等式，得 log(9) < nlog(9)-[nlog(9)] < 1 也就是说 nlog(9) 的小数部分大于 log(9) 就可以了。列等差数列，做一个除法，问题结束。 |
 |
6
lightening 2016-05-11 18:15:38 +08:00
@Kirscheis 能不能解释一下为什么 10^([log(9^n)]+1) > 9^n > 9^[log(9^n)] 代表首位为 9 ？
|
|
7
Kirscheis 2016-05-11 18:28:50 +08:00 via iPhone
@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 上面两个条件合起来就是了 |
|
8
Kirscheis 2016-05-11 18:31:20 +08:00 via iPhone 1
@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 上面两个条件合起来就是了 |
|
9
Kirscheis 2016-05-11 18:32:43 +08:00 via iPhone 2
@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 上面两个条件合起来就是了 |
 |
10
luban 2016-05-11 18:37:26 +08:00 2
|
|
11
luban 2016-05-11 18:39:20 +08:00 1
上面说错了，应该是要知道最大的一个 9 的 n 次方首位是 9 才行
|
|
12
luban 2016-05-11 18:57:24 +08:00 1
经过少量测试， 9^2011 的首位是 9 ， 9^2011 长度是 1919 ，也就是 2011-1919=92 个
|
 |
13
billion 2016-05-11 19:39:32 +08:00
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 开头 |
 |
14
yuuki 2016-05-11 19:40:49 +08:00
算出来是 21 个，不知道对不对🐸
用到了科学计数法，对数和不等式的知识 9^n=a·10^(n-1)，满足首位为 9→9≤a<10 ，解不等式得 1≤n≤21 |
 |
15
qqmishi 2016-05-11 19:43:43 +08:00 via Android 1
想了半天才发现是要求有几个，，，
首位是 9 意味着本次运算没有进位，所以看看位数与指数的差就行了，理论上只需要算 9^2016 的位数 实际上差不多每隔 22 或者 21 就会出现一个首位是 9 的 |
 |
16
loading 2016-05-11 19:52:31 +08:00 via Android
完全不懂……
|
 |
17
zingl 2016-05-11 23:47:35 +08:00 1
2016*(1-log9)
|
|
18
lightening 2016-05-11 23:56:58 +08:00
@Kirscheis
谢谢。这里 [ ] 是取整数的意思吗？ |
 |
19
jimages 2016-05-12 00:11:56 +08:00 via Android
@Kirscheis 有误，应为， p 位整数 x 首位为 9 的充要条件是 10^p > x >= 10^p - 10^(p-1)
|
|
20
jimages 2016-05-12 00:16:49 +08:00
@jimages 于是 变形 10^p > x >= 9*10^(p-1) 这里在 x 为 9 的时候需要取等号，因此不能退化。
|
 |
22
MCVector 2016-05-12 02:41:23 +08:00 via Android
首位肯定是个循环数组，找到循环的周期就行了。
|
 |
23
maomaomao001 2016-05-12 02:47:20 +08:00 via Android
首位为 9 的数不是有无数个吗？
9 9x 9xx 9xxx |
|
24
Kirscheis 2016-05-12 03:37:01 +08:00 via Android 1
@jimages 抱歉，是有点问题。吃晚饭的时候看见题目随手打的，脑抽忘了乘 9 。果然口算不怎么靠谱。不过基础思路就是取对数换底，把常数替换一下就行了。 n=1 的时候确实不能退化了，不等式里的小于应该换成小于等于。
楼上已经出现更好的算法了，我考虑过 9 开头的数是否前一个一定 1 开头后一个一定进位，但是当时吃着饭感觉证明比较麻烦，没想到挺容易的。 |
 |
26
panchina OP @lightening 是的
|
 |
27
yszx 2016-05-12 09:27:34 +08:00
@luban 并不需要知道最后一个数是否开头是 9 ，因为他的原理是 位数差=出现重复位数的次数=9 开头的次数，这个思路太强大了···
|
|
28
zingl 2016-05-12 11:35:26 +08:00 1
不需要知道最后一个数开头是什么，但需要知道最后一个数有多少位，也就是要知道 log(9^k)=k*2*log3 的整数部分，所以告诉你了 log3 等于多少
链接里的解是不完全的，因为除了要证明“若 9 的 a 次方首位數字為 9, 那麼 9 的 a-1 次方位數與 9 的 a 次方位數相同(這是明顯的)”，还要证明对于任意 b 位数的自然数，其中至少有 1 个是 9 的整数次幂（引号内容表明可以有 2 个，引申可证得不会有 2 个以上），否则解法是不成立的。 最后就是个抽屉原理了。 |
 |
31
Rorysky 2016-05-12 13:25:21 +08:00 via Android
|
|
32
zingl 2016-05-12 13:30:25 +08:00 1
@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 无正整数解，所以上面的不等式不需要考虑相等 |
|
33
Kirscheis 2016-05-12 15:03:16 +08:00 via Android 1
@Rorysky 昨天吃饭的时候打的，手抽少乘了个 9 ，见 24 楼。两位整数首位为 9 条件是 100>x>=90 。
|
 |
35
whh945atsyzx 2016-05-12 17:28:17 +08:00
难道不是无数个吗....在 9 后面无限加数字...
|
|
36
panchina OP @whh945atsyzx 9^n 指的是 9 的 n 次方幂
|
 |
38
programgou 2016-06-26 02:45:48 +08:00
把问题推广开来， w,w^1,w^2,w^3,....,w^n 首位为 w 的有几个？
|
Select Language