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

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

>>> 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

>>> 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

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