V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
panchina
V2EX  ›  数学

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

  •  
  •   panchina · 2016-05-11 16:36:21 +08:00 · 6023 次点击
    这是一个创建于 2879 天前的主题,其中的信息可能已经有所发展或是发生改变。
    前几天培训时提出的一个问题:
    9, 9^1, 9^2, ... 9^2016

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

    ps:不能一个个排查
    pps:说用高中数学知识就可以了 =_=!
    41 条回复    2016-07-23 10:40:47 +08:00
    Dannytmp
        1
    Dannytmp  
       2016-05-11 16:38:46 +08:00
    难点在于高中知识的范围啊
    ffffwh
        3
    ffffwh  
       2016-05-11 17:57:03 +08:00   ❤️ 1
    9 * (10 - 1)^n, for n = 0 -> 2016 。看(10-1)^n 怎么给出首位为 1 的?
    Kirscheis
        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) 就可以了。列等差数列,做一个除法,问题结束。
    panchina
        5
    panchina  
    OP
       2016-05-11 18:00:16 +08:00
    @ffffwh 这不就是相当于一个个排查了么?
    lightening
        6
    lightening  
       2016-05-11 18:15:38 +08:00
    @Kirscheis 能不能解释一下为什么 10^([log(9^n)]+1) > 9^n > 9^[log(9^n)] 代表首位为 9 ?
    Kirscheis
        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
    上面两个条件合起来就是了
    Kirscheis
        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
    上面两个条件合起来就是了
    Kirscheis
        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
    上面两个条件合起来就是了
    luban
        10
    luban  
       2016-05-11 18:37:26 +08:00   ❤️ 2
    http://blog.udn.com/ivan5chess/1636470

    这里有个很巧妙的解法,但是要知道最后一个,也就是 9 的 2016 次方首位是不是 9
    luban
        11
    luban  
       2016-05-11 18:39:20 +08:00   ❤️ 1
    上面说错了,应该是要知道最大的一个 9 的 n 次方首位是 9 才行
    luban
        12
    luban  
       2016-05-11 18:57:24 +08:00   ❤️ 1
    经过少量测试, 9^2011 的首位是 9 , 9^2011 长度是 1919 ,也就是 2011-1919=92 个
    billion
        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 开头
    yuuki
        14
    yuuki  
       2016-05-11 19:40:49 +08:00
    算出来是 21 个,不知道对不对🐸
    用到了科学计数法,对数和不等式的知识
    9^n=a·10^(n-1),满足首位为 9→9≤a<10 ,解不等式得 1≤n≤21
    qqmishi
        15
    qqmishi  
       2016-05-11 19:43:43 +08:00 via Android   ❤️ 1
    想了半天才发现是要求有几个,,,
    首位是 9 意味着本次运算没有进位,所以看看位数与指数的差就行了,理论上只需要算 9^2016 的位数

    实际上差不多每隔 22 或者 21 就会出现一个首位是 9 的
    loading
        16
    loading  
       2016-05-11 19:52:31 +08:00 via Android
    完全不懂……
    zingl
        17
    zingl  
       2016-05-11 23:47:35 +08:00   ❤️ 1
    2016*(1-log9)
    lightening
        18
    lightening  
       2016-05-11 23:56:58 +08:00
    @Kirscheis
    谢谢。这里 [ ] 是取整数的意思吗?
    jimages
        19
    jimages  
       2016-05-12 00:11:56 +08:00 via Android
    @Kirscheis 有误,应为, p 位整数 x 首位为 9 的充要条件是 10^p > x >= 10^p - 10^(p-1)
    jimages
        20
    jimages  
       2016-05-12 00:16:49 +08:00
    @jimages 于是 变形 10^p > x >= 9*10^(p-1) 这里在 x 为 9 的时候需要取等号,因此不能退化。
    ceoimon
        21
    ceoimon  
       2016-05-12 00:46:09 +08:00
    @luban 这个思路太吊了
    MCVector
        22
    MCVector  
       2016-05-12 02:41:23 +08:00 via Android
    首位肯定是个循环数组,找到循环的周期就行了。
    maomaomao001
        23
    maomaomao001  
       2016-05-12 02:47:20 +08:00 via Android
    首位为 9 的数不是有无数个吗?
    9
    9x
    9xx
    9xxx
    Kirscheis
        24
    Kirscheis  
       2016-05-12 03:37:01 +08:00 via Android   ❤️ 1
    @jimages 抱歉,是有点问题。吃晚饭的时候看见题目随手打的,脑抽忘了乘 9 。果然口算不怎么靠谱。不过基础思路就是取对数换底,把常数替换一下就行了。 n=1 的时候确实不能退化了,不等式里的小于应该换成小于等于。
    楼上已经出现更好的算法了,我考虑过 9 开头的数是否前一个一定 1 开头后一个一定进位,但是当时吃着饭感觉证明比较麻烦,没想到挺容易的。
    panchina
        25
    panchina  
    OP
       2016-05-12 09:16:36 +08:00
    @luban bingo~
    panchina
        26
    panchina  
    OP
       2016-05-12 09:18:38 +08:00
    @lightening 是的
    yszx
        27
    yszx  
       2016-05-12 09:27:34 +08:00
    @luban 并不需要知道最后一个数是否开头是 9 ,因为他的原理是 位数差=出现重复位数的次数=9 开头的次数,这个思路太强大了···
    zingl
        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 个以上),否则解法是不成立的。

    最后就是个抽屉原理了。
    panchina
        29
    panchina  
    OP
       2016-05-12 12:35:58 +08:00
    @zingl 第二个证明只需要考虑: 10^(n-1) < 9^n <10^n
    jimages
        30
    jimages  
       2016-05-12 12:59:09 +08:00 via Android
    @Kirscheis 我没有收到你的提醒,是不是你被降级了?
    Rorysky
        31
    Rorysky  
       2016-05-12 13:25:21 +08:00 via Android
    @Kirscheis 还厉害 我初中肯定不会这些。。。

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

    @lightening
    zingl
        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 无正整数解,所以上面的不等式不需要考虑相等
    Kirscheis
        33
    Kirscheis  
       2016-05-12 15:03:16 +08:00 via Android   ❤️ 1
    @Rorysky 昨天吃饭的时候打的,手抽少乘了个 9 ,见 24 楼。两位整数首位为 9 条件是 100>x>=90 。
    Kirscheis
        34
    Kirscheis  
       2016-05-12 15:05:08 +08:00 via Android
    @jimages 多谢提醒,很有可能。以前在 V2 发非法爬虫被封过
    whh945atsyzx
        35
    whh945atsyzx  
       2016-05-12 17:28:17 +08:00
    难道不是无数个吗....在 9 后面无限加数字...
    panchina
        36
    panchina  
    OP
       2016-05-12 17:46:08 +08:00
    @whh945atsyzx 9^n 指的是 9 的 n 次方幂
    snsd
        37
    snsd  
       2016-05-15 22:49:35 +08:00
    @Kirscheis 你们那边初中就讲对数的知识了?
    programgou
        38
    programgou  
       2016-06-26 02:45:48 +08:00
    把问题推广开来, w,w^1,w^2,w^3,....,w^n 首位为 w 的有几个?
    rushcheyo
        39
    rushcheyo  
       2016-07-17 21:45:44 +08:00
    @snsd 对啊,初一上一进来第一课就是对数换底公式。
    snsd
        40
    snsd  
       2016-07-23 00:27:13 +08:00
    @rushcheyo 你那是什么地方?讲得那么先进。我这到了高一才讲的对数
    rushcheyo
        41
    rushcheyo  
       2016-07-23 10:40:47 +08:00
    @snsd 安徽芜湖。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5385 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:01 · PVG 17:01 · LAX 02:01 · JFK 05:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.