求计算n元恒等索引n进制对应值的简洁函数

问题定义 #

给定长度为n的递增恒等索引序列 [0, 1, …, n-1]，将其视为n进制数（保留前导0），按从右到左对应n的幂次（序列第i个元素对应n的(n-1-i)次幂）计算十进制值。示例如下：

2 -> [0,1] -> 0×2¹ + 1×2⁰ = 1
3 -> [0,1,2] -> 0×3² + 1×3¹ + 2×3⁰ = 5
4 -> [0,1,2,3] -> 0×4³ + 1×4² + 2×4¹ + 3×4⁰ = 27
5 -> [0,1,2,3,4] -> 0×5⁴ + 1×5³ + 2×5² + 3×5¹ + 4×5⁰ = 194
6 -> [0,1,2,3,4,5] -> 0×6⁵ + 1×6⁴ + 2×6³ + 3×6² + 4×6¹ + 5×6⁰ = 1865

简洁函数实现 #

闭合公式推导 #

观察求和式：
$$ S(n) = \sum_{k=1}^{n-1} k \times n^{(n-1)-k} $$
通过等差乘等比数列求和公式推导，可得到无需循环的闭合公式：
$$ S(n) = \frac{n^n - n^2 + n - 1}{(n-1)^2} $$

代码实现（Python示例） #

def compute_sequence_value(n):
    if n == 1:
        return 0  # 特殊情况：序列[0]对应值为0
    numerator = n ** n - n ** 2 + n - 1
    denominator = (n - 1) ** 2
    return numerator // denominator

验证结果完全匹配示例，且计算效率远高于暴力求和或循环累加。

序列值在区间内的分布分析 #

目标区间为 [0, nⁿ - 1]，对应所有n位n进制数（含前导0）的十进制范围：

1. 相对占比：随着n增大，$S(n)$ 与区间最大值 $nⁿ-1$ 的比值趋近于 $\frac{1}{(n-1)^2}$，占比逐渐减小并趋近于0。比如n=5时占比约6.2%，n=10时占比约1.23%。
2. 增长特性：$S(n)$ 的增长速度为 $O(n^n / n²)$，远慢于区间最大值的 $O(n^n)$，因此n较大时，该值会落在区间中相对靠近0的区域，但绝对数值仍呈指数级增长。

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