如何计算3、9构成的有序序列中第N个数的位数

序列规则：仅使用数字3、9生成，按数值升序排列为3, 9, 33, 39, 93, 99, 333...，已知示例：第4个数位数为2，第7个数位数为3，本次计算目标为N=1000000时对应的位数。

你已经观察到的长度分布规律完全正确，顺着等比数列求和的思路往下推导即可得到可行方案：

核心推导逻辑 #

• k位长度的符合要求的数，总数是2^k个：每一位都有3、9两种选择，由乘法原理可直接得出
• 所有长度小于等于m位的数的总个数，是首项为2、公比为2的等比数列前m项和：
  S(m) = 2^1 + 2^2 + ... + 2^m = 2*(2^m -1)/(2-1) = 2^(m+1) - 2
  我们要找的位数k，就是满足S(m) >= N的最小正整数m，也就是找到最小的m，让前m位的总个数刚好覆盖到第N个数。
  对不等式做整理：2^(m+1) - 2 >= N 等价于 2^(m+1) >= N + 2，两边取以2为底的对数可得m+1 >= log2(N+2)，最终m就是对log2(N+2)向上取整后减1。

计算结果 #

代入N=1000000计算：

• N+2 = 1000002
• 计算2的幂次可得：2^19 = 524288，2^20 = 1048576，满足2^t >= 1000002的最小t值为20
• 因此位数m = 20 -1 = 19
  即第1000000个数的位数是19。

示例校验 #

代入已知样例验证公式正确性：

• N=4：N+2=6，满足2^3=8>=6，m=3-1=2，和示例结果一致
• N=7：N+2=9，满足2^4=16>=9，m=4-1=3，和示例结果一致
• N=2：N+2=4，满足2^2=4>=4，m=2-1=1，对应第二个数9，位数为1，结果正确
• N=6：N+2=8，满足2^3=8>=8，m=3-1=2，对应第六个数99，位数为2，结果正确

内容的提问来源于stack exchange，提问作者hari