当前位置：卡卷网 / 每日看点 / 正文

2的多少次方的最高位是9？

作者：卡卷网发布时间：2025-05-08 23:20浏览数量：6次评论数量：0次

已经有不少回答给出了答案：2 的 53 次方，首位初次出现 9。

我们现在来探究一下此类问题的通法：给定一个底数和一个前缀，那么使得以开头的最小的自然数是多少？

问题的抽象

我们放到对数域中来研究：一个数 2的多少次方的最高位是9？第1张的开头几位是哪些数字，其实蕴含在的小数部分里面。用 $2的多少次方的最高位是9？第8张$ 表示的小数部分，则「以开头」这个条件，可以表示成： $2的多少次方的最高位是9？第12张$ 这里面，左右两个端点可以进一步抽象成一个区间 2的多少次方的最高位是9？第1张，而中间的 $2的多少次方的最高位是9？第14张$ 可以进一步抽象成 $2的多少次方的最高位是9？第15张$ ，其中 $2的多少次方的最高位是9？第16张$ 是一个常数。也就是说，我们的问题转化为：给定一个常数和一个区间，使得 $2的多少次方的最高位是9？第19张$ 的最小的是多少？

在原始问题中，各个参数的取值为： 2的多少次方的最高位是9？第1张。

画图观察

我们以编号 2的多少次方的最高位是9？第1张为横坐标， $2的多少次方的最高位是9？第23张$ 为纵坐标，画出范围内所有的点。其中 $2的多少次方的最高位是9？第25张$ 的区域用蓝色背景标出，落在此区域内的第一个点的编号就是我们要的答案。

2的多少次方的最高位是9？第26张

图 1：前 100 个点

可以看到，这些点似乎形成一条条向右下延伸的斜线，这些斜线在纵轴上的截距分别为 2的多少次方的最高位是9？第1张。形成这种现象的原因在于。能不能利用这些斜线按图索骥，找到哪些点会落在目标区域里呢？似乎不太行——每条斜线上的点的间距太大了，以至于许多斜线直接「跨过」了目标区域，我们没法预知哪条斜线上会有点落在目标区域里。

我们再多画一些点，把 2的多少次方的最高位是9？第1张的点全都画出来：

2的多少次方的最高位是9？第30张

图 2：前 1000 个点

这回，我们看到了另一种斜线模式：它们向右上延伸，在纵轴上的截距分别为 2的多少次方的最高位是9？第1张。形成这种模式的原因在于，其分母为 10。原来那些向右下延伸的斜线其实依然存在，只不过在图 2 的尺度下，它们的点间距太大，导致它们不如向右上延伸的斜线显著。向右上延伸的这些斜线上的点足够密了，以至于随便选取一条斜线，它们都能够在目标区域里留下足迹。我们只需要找起点离目标区域最近的那条斜线（从 0.9 出发的那条），然后找到它落在目标区域里的第一个点即可。

丢番图逼近

我们发现，常数 2的多少次方的最高位是9？第1张的每一个分数形式的近似值（例如），都会在某种尺度下形成比较显著的斜线模式。把纵轴看成循环的，则这样的斜线一共有条。它们与纵轴的交点（下面称为「起点」）的纵坐标都是的形式，其中 2的多少次方的最高位是9？第1张称为斜线的编号。斜线上相邻两个点的编号相差，在纵向的距离是。这个纵向距离可以作为对的逼近误差的一种量度。我们希望找到一个足够好的近似，使得误差不超过目标区间的宽度，即 2的多少次方的最高位是9？第1张，这样就能保证每条斜线上都有点落在目标区域里。同时，这个近似的分母也不用太大，够用就行。

丢番图逼近的理论告诉我们，可以把 2的多少次方的最高位是9？第1张写成连分数的形式：把这个连分数在任意位置截断，都可以得到的一个近似值，称为「丢番图逼近」。例如，的前几个丢番图逼近为：。这些丢番图逼近，正是的「第二类最佳逼近」：按 2的多少次方的最高位是9？第1张定义的误差，在所有分母不超过的分数中是最小的。

顺便提一下，逼近误差还可以定义成。如果一个近似值使得这种误差在所有分母不超过的分数中最小，则称为的「第一类最佳逼近」。「第二类最佳逼近」是「第一类最佳逼近」的充分非必要条件，也就是说，丢番图逼近只是一部分「第一类最佳逼近」。

我们在所有的「第二类最佳逼近」中，选取第一个满足误差 2的多少次方的最高位是9？第1张的近似值。对于来说，这个近似值是，它的误差约为，小于目标区间的宽度（约为）。

选定了 2的多少次方的最高位是9？第1张的一个近似值后，我们来看看第一个落在目标区域里的点，有希望落在哪些斜线上。起点本来就在目标区域里（即 $2的多少次方的最高位是9？第65张$ ）的斜线，自然是有戏的。除此之外，若斜线是上升的，那么起点刚好低于目标区域的那条斜线也有戏；若斜线是下降的，那么起点刚好高于目标区域的那条斜线也有戏。我们可以在这些斜线上寻找答案的候补：

对于起点本来就是目标区域里的斜线，我们要找到它上面的第一个点。当然，这个点有可能已经跑到了目标区域之外，所以需要检验。
对于起点刚好在目标区域之外的斜线，我们要找到它上面第一个落在目标区域里的点。为此，我们要首先找到斜线上的第一个点，然后按向量去推出余下的点的坐标，并算出第一个落在目标区域里的点是谁。

总之，现在我们面临的一个问题是：如何求出 2的多少次方的最高位是9？第1张号斜线上第一个点的编号？

裴蜀等式与数论倒数

不难发现， 2的多少次方的最高位是9？第1张号点位于号斜线上。于是，号斜线上的第一个点的编号，就是使得的最小的。这个方程也可以写成，称为「裴蜀等式」，其中是已知数，是未知数。它的解可以利用扩展欧几里得算法求出。特别地，我们可以先求出 2的多少次方的最高位是9？第1张时的解，这样就能很方便地得到取任意值时的解。这里，称为在模下的数论倒数。

对于 2的多少次方的最高位是9？第1张来说，由于，所以 3 在模 10 下的数论倒数为 7。

由于没有任意一条斜线的起点位于目标区域内，而斜线是上升的，所以我们考虑起点刚好低于目标区域的 9 号斜线。它上面的第一个点的编号是 2的多少次方的最高位是9？第1张，纵坐标是 $2的多少次方的最高位是9？第86张$ ，到目标区域的距离是。在这条斜线上，每往后推一个点，编号增加 10，纵坐标增加。于是，往后推个点后，就会落在目标区域里，而这个点的编号就是 53。

Show Me the Code

可以把上面的整套流程总结成程序：

import math import sys def cont_frac(x, max_levels=10): """ 求 x 的连分数表示，最多 max_levels 层。例如：cont_frac(math.log10(2)) = [0, 3, 3, 9, 2, 2, 4, 6, 2, 1]。 """ result = [] while len(result) < max_levels: if abs(x - round(x)) < 1e-9: # 若当前层的值足够接近整数，那就认为是整数 result.append(round(x)) break result.append(int(x)) x = 1 / (x % 1) return result def fold_cont_frac(cont_frac): """ 把连分数化成分数。例如：fold_cont_frac([0, 3, 3]) = (3, 10)，代表 0 + 1 / (3 + 1 / 3) = 3/10。 """ n, d = cont_frac[-1], 1 for a in cont_frac[-2::-1]: n, d = a * n + d, n return n, d def mod_inv(p, q): """ 用扩展欧几里得算法求 p 在模 q 下的数论倒数。例如：mod_inv(3, 10) = 7。 """ old_r, r = p, q old_s, s = 1, 0 while r != 0: q = old_r // r old_r, r = r, old_r - q * r old_s, s = s, old_s - q * s return old_s def min_power(base, target): """ 求最小的自然数 n，使得 base ** n 以 target 开头。例如：min_power(2, 3) = 5，因为 2 ** 5 = 32 以 3 开头。 base 可以是任意正实数，target 可以是任意多位正整数。 """ # 求对数域下的目标区间 [s,t) # 因为该区间左闭右开，故将两端均减去一个微小的值， # 以确保与区间端点进行比较时，s 落在区间内，t 落在区间外 c = math.log10(base) % 1 s, t = math.log10(target), math.log10(target + 1) offset = math.floor(s) + 1e-12 s, t = s - offset, t - offset # 求 c 的丢番图逼近，使得误差 err 的绝对值不超过 t - s cf = cont_frac(c) for levels in range(2, len(cf) + 1): p, q = fold_cont_frac(cf[:levels]) err = q * c - p if abs(err) <= t - s: break else: raise ValueError("找不到足够好的丢番图逼近") # 求 p 在模 q 下的数论倒数 n1 n1 = mod_inv(p, q) # 编号从 min_k 至 max_k 的斜线，起点在目标区间内。 # 若这些斜线上的第一个点也在目标区间内，则可作为答案的候补。 min_k, max_k = math.ceil(s * q), math.ceil(t * q) - 1 min_n = float("inf") for k in range(min_k, max_k + 1): n = (n1 * k) % q # 斜线上第一个点的编号 y = (n * c) % 1 # 斜线上第一个点的纵坐标 if s <= y < t and n < min_n: min_n = n # 若斜线向上，则答案也可能在 min_k 下面一条斜线上 if err > 0 and s > 0: k = min_k - 1 n = (n1 * k) % q # 斜线上第一个点的编号 y = (n * c) % 1 # 斜线上第一个点的纵坐标 n += q * math.ceil((s - y) / err) # 目标区域内第一个点的编号 if n < min_n: min_n = n # 若斜线向下，则答案也可能在 max_k 上面一条斜线上 elif err < 0: k = max_k + 1 n = (n1 * k) % q # 由于斜线向下，故对于 0 号点，认为其纵坐标为 1 而非 0 y = (n * c) % 1 or 1 n += q * (math.floor((y - t) / (-err)) + 1) if n < min_n: min_n = n # 返回落在目标区间内的点的最小编号 return min_n

来试验一下，2 的几次方的初次以 1 ~ 9 开头：

>>> for i in range(1, 10): ... n = min_power(2, i) ... print(f"2 ** {n} == {2 ** n}") 2 ** 0 == 1 2 ** 1 == 2 2 ** 5 == 32 2 ** 2 == 4 2 ** 9 == 512 2 ** 6 == 64 2 ** 46 == 70368744177664 2 ** 3 == 8 2 ** 53 == 9007199254740992

果然印证了原题的答案： 2的多少次方的最高位是9？第1张初次以 9 开头。

还可以试验一下 2 的几次方初次以 10 ~ 99 开头。注意对于 10，程序给出的结果是 2的多少次方的最高位是9？第1张，因为 1（即 1.0）也可以认为是以 10 开头。20、40、80 同理。

>>> for i in range(10, 100): ... n = min_power(2, i) ... print(f"2 ** {n} == {2 ** n}") 2 ** 0 == 1 2 ** 50 == 1125899906842624 2 ** 7 == 128 2 ** 17 == 131072 2 ** 47 == 140737488355328 2 ** 77 == 151115727451828646838272 2 ** 4 == 16 2 ** 34 == 17179869184 2 ** 54 == 18014398509481984 2 ** 84 == 19342813113834066795298816 2 ** 1 == 2 2 ** 31 == 2147483648 2 ** 51 == 2251799813685248 2 ** 61 == 2305843009213693952 2 ** 81 == 2417851639229258349412352 2 ** 8 == 256 2 ** 18 == 262144 2 ** 38 == 274877906944 2 ** 48 == 281474976710656 2 ** 68 == 295147905179352825856 2 ** 78 == 302231454903657293676544 2 ** 98 == 316912650057057350374175801344 2 ** 5 == 32 2 ** 25 == 33554432 2 ** 35 == 34359738368 2 ** 45 == 35184372088832 2 ** 55 == 36028797018963968 2 ** 75 == 37778931862957161709568 2 ** 85 == 38685626227668133590597632 2 ** 95 == 39614081257132168796771975168 2 ** 2 == 4 2 ** 22 == 4194304 2 ** 32 == 4294967296 2 ** 42 == 4398046511104 2 ** 145 == 44601490397061246283071436545296723011960832 2 ** 52 == 4503599627370496 2 ** 62 == 4611686018427387904 2 ** 72 == 4722366482869645213696 2 ** 82 == 4835703278458516698824704 2 ** 92 == 4951760157141521099596496896 2 ** 102 == 5070602400912917605986812821504 2 ** 9 == 512 2 ** 19 == 524288 2 ** 29 == 536870912 2 ** 39 == 549755813888 2 ** 142 == 5575186299632655785383929568162090376495104 2 ** 49 == 562949953421312 2 ** 59 == 576460752303423488 2 ** 162 == 5846006549323611672814739330865132078623730171904 2 ** 69 == 590295810358705651712 2 ** 79 == 604462909807314587353088 2 ** 89 == 618970019642690137449562112 2 ** 192 == 6277101735386680763835789423207666416102355444464034512896 2 ** 99 == 633825300114114700748351602688 2 ** 6 == 64 2 ** 16 == 65536 2 ** 119 == 664613997892457936451903530140172288 2 ** 26 == 67108864 2 ** 36 == 68719476736 2 ** 139 == 696898287454081973172991196020261297061888 2 ** 46 == 70368744177664 2 ** 149 == 713623846352979940529142984724747568191373312 2 ** 56 == 72057594037927936 2 ** 66 == 73786976294838206464 2 ** 169 == 748288838313422294120286634350736906063837462003712 2 ** 76 == 75557863725914323419136 2 ** 179 == 766247770432944429179173513575154591809369561091801088 2 ** 86 == 77371252455336267181195264 2 ** 189 == 784637716923335095479473677900958302012794430558004314112 2 ** 96 == 79228162514264337593543950336 2 ** 3 == 8 2 ** 13 == 8192 2 ** 209 == 822752278660603021077484591278675252491367932816789931674304512 2 ** 23 == 8388608 2 ** 219 == 842498333348457493583344221469363458551160763204392890034487820288 2 ** 33 == 8589934592 2 ** 229 == 862718293348820473429344482784628181556388621521298319395315527974912 2 ** 43 == 8796093022208 2 ** 239 == 883423532389192164791648750371459257913741948437809479060803100646309888 2 ** 146 == 89202980794122492566142873090593446023921664 2 ** 53 == 9007199254740992 2 ** 156 == 91343852333181432387730302044767688728495783936 2 ** 63 == 9223372036854775808 2 ** 166 == 93536104789177786765035829293842113257979682750464 2 ** 73 == 9444732965739290427392 2 ** 176 == 95780971304118053647396689196894323976171195136475136 2 ** 83 == 9671406556917033397649408 2 ** 279 == 971334446112864535459730953411759453321203419526069760625906204869452142602604249088 2 ** 186 == 98079714615416886934934209737619787751599303819750539264 2 ** 93 == 9903520314283042199192993792

可以看到，输出的前半段像一棵圣诞树一样错落有致，每一个三角形中，指数的个位数都相同，十位数基本上是依次递增，偶尔会跳过一个数。这背后的原因，就在于 2的多少次方的最高位是9？第1张非常接近 10 的整数次幂。在输出的后半段，「指数依次加 10」的模式开始显出一些漏洞，被等指数更大的幂填充；到了最后，漏洞多到填充它们的幂的指数也显示出了「依次加 10」的规律（例如 2的多少次方的最高位是9？第1张到）。

还可以换一些数字来玩：

>>> min_power(math.pi, 520) 275 >>> min_power(666, 888) 2000 >>> min_power(114514, 1919810) 1947860

可以验证，确实有：

$2的多少次方的最高位是9？第96张$