背景信息

我们知道任意正整数 $a \in \Z^+$ 可以通过质因分解式表达成质数序列 $\gamma_1=2$，$\gamma_2=3$，$\gamma_3=5$……的自然数幂：

$$ a = \prod_{i=1}^{\infty} \gamma_i^{\alpha_i}, \quad \forall i \in \N^+, \, \alpha_i \in \N $$

指数序列构成有限支撑 (finite support) 的自然数序列，即序列属于 $\N^{(\infty)}$：

$$ \N^{(\infty)} := \{ (\alpha_i)_{i \ge 1} \mid \alpha_i \in \N, \, {\rm 且只有有限个} \, \alpha_i \neq 0 \} $$

其中，「只有有限个 $\alpha_i \neq 0$」的条件就是所谓的「有限支撑的 (finite support)」。

容易证明这是一个 $a \in \Z^+$ 到 $(\alpha_i){i \ge 1} \in \N^{(\infty)}$ 之间的双射。因而 $(\alpha_i){i \ge 1}$ 也被称为 $a$ 的「指数向量」。

指数向量（有限支撑自然数列）的枚举

问题：要如何枚举指数向量，能够兼顾向量的长度（最大质数索引）、L1 模长，或甚至是对应的正整数域的值的大小（但我当然不希望大量进行因数分解）？

潜在思路：采用类似于嵌套 Cantor 配对函数的枚举方法？

解答：使用类似于 zig-zag 的方法，先枚举「长度 + L1 模长」综合量，再将综合量分配给长度和模长，然后再分配模长给各个维度（注意最后一个维度需要特殊对待，因为它不能是 0）。见下。

from itertools import combinations, count

def weak_compositions(s, k):
    """
    所有 k 元弱组合：a_i >= 0 且 sum a_i = s
    stars and bars: 选 k-1 个隔板位置
    """
    for bars in combinations(range(s + k - 1), k - 1):
        bars = (-1,) + bars + (s + k - 1,)
        parts = tuple(bars[i+1] - bars[i] - 1 for i in range(k))
        yield parts

def enum_alpha_by_len_l1():
    """
    产出有限元组 alpha=(α1,...,αk)；其余分量默认 0
    顺序：按 t = len + L1 对角线增长
    """
    yield ()  # 全 0，表示 1
    for t in count(1):                 # t = length + L1
        for k in range(1, t + 1):      # k = length
            s = t - k                  # s = L1
            if s < 1:
                continue               # length>0 时必须 L1>=1
            for ak in range(1, s + 1): # ak 即 alpha_k, 强制枚举这一项的大小使其 >0
                for prefix in weak_compositions(s - ak, k - 1):
                    yield prefix + (ak,)

def first_primes(n):
    ps = []
    x = 2
    while len(ps) < n:
        ok = True
        for p in ps:
            if p*p > x: break
            if x % p == 0:
                ok = False; break
        if ok: ps.append(x)
        x += 1 if x == 2 else 2
    return ps

def alpha_to_int(alpha):
    ps = first_primes(len(alpha))
    a = 1
    for p, e in zip(ps, alpha):
        a *= pow(p, e)
    return a

兼容加法运算的混合表示

问题：如果在计算机中用指数向量表达正整数，我们知道计算整数域乘法只需要对向量进行相加即可，但计算整数域加法将变得异常困难，一般的做法是从指数向量返回正整数域再进行四则运算，再重新计算结果的指数向量（涉及进行质因分解）。如果确实想要在指数向量表达的基础上，大量地计算两个数或者三个数之间的整数域加法，工程上比较现实的方案有哪些？

潜在思路：涉及 cache、多线程并行的方案？展望 gpu 上的并行计算方案？

思路如下。

两段式混合表示

乘法