🔢 mathematics

Exact Formulas for Coprime Representations of Even Integers Avoiding a Prime

该论文针对固定素数 $p \ge 5$ ，利用欧几里得算法导出了计算满足特定互质条件的偶数 $2n$ 的互质表示数 $g(2n,p)$ 的显式闭式公式，该公式仅需 $O(1)$ 时间复杂度即可高效计算，并已通过数值实验验证了其正确性。

原作者： Andres M. Salazar

发布于 2026-04-06

📖 1 分钟阅读🧠 深度阅读

原作者： Andres M. Salazar

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文就像是一位数学家在解决一个**“超级严格的配对游戏”，并找到了一种“作弊码”**（公式），让你不用一个个数就能瞬间知道答案。

我们可以把这篇论文的内容拆解成以下几个有趣的部分：

1. 游戏是什么？（核心问题）

想象你有一堆数字积木，你要把它们两两配对，让它们加起来等于一个偶数（比如 100）。
但是，这个配对游戏有三个极其苛刻的规则：

不能太小：两个数字都必须是正整数。
不能重复：为了公平，我们规定第一个数字必须小于或等于第二个数字（比如 3+97 算一种，97+3 不算新的）。
不能“沾亲带故”：这是最难的规则。这两个数字，绝对不能被 2、3 或者某个特定的大质数（比如 5、7、11...） 整除。

举个例子：
如果我们要凑成 20，且排除的质数是 5（即不能含因子 2, 3, 5）：

1 + 19 = 20？（1 和 19 都不含 2,3,5，通过！）
2 + 18 = 20？（2 含因子 2，淘汰！）
3 + 17 = 20？（3 含因子 3，淘汰！）
4 + 16 = 20？（4 含因子 2，淘汰！）
5 + 15 = 20？（5 含因子 5，淘汰！）
...以此类推。

作者想知道：对于任意一个偶数，到底有多少种合法的配对方法？这个数量记作 $g(2n, p)$ 。

2. 以前的做法 vs. 现在的做法

以前的做法（笨办法/暴力枚举）：
就像你要数清楚一个房间里有多少个红苹果。你得走进房间，拿起每一个苹果，检查它是不是红的，是不是被咬了一口。如果房间里有 100 万个苹果，你就得检查 100 万次。
- 缺点：太慢了！数字越大，算得越慢。
作者的新方法（魔法公式/作弊码）：
作者发现，这些数字的排列其实非常有规律，就像乐高积木一样，是按照特定的“轨道”运行的。
他发明了一个**“快速计算器”**。你只需要做两件事：
1. 准备工作：先花一点点时间（几乎可以忽略不计），算出两个关键的“密码”（数学上叫 $a(p)$ 和 $b(p)$ ）。这就像是你先画好了一张地图。
2. 瞬间计算：以后不管数字多大，只要把数字扔进公式里，**“咔嚓”**一下，立刻就能得到答案。
- 优点：不管数字是 100 还是 100 亿，计算时间都是一样的快（常数时间 $O(1)$ ）。

3. 这个“魔法”是怎么工作的？（核心原理）

作者用了一个很巧妙的**“余数过滤器”**。

第一步：分类
他先把所有数字分成三组（就像把人群按身高分成高、中、矮）：
- 除以 3 余 0 的。
- 除以 3 余 1 的。
- 除以 3 余 2 的。
  不同的组，配对的方式完全不同。
第二步：找“坏蛋”
规则说不能含因子 $p$ （比如 5）。作者发现，在数字的排列中，那些“含因子 5"的数字就像地雷，它们每隔一段距离就会出现一次。
作者通过一个古老的数学工具（欧几里得算法，就像分蛋糕一样不断切分），精准地找到了这些“地雷”第一次出现的位置。
第三步：直线运动
最神奇的是，作者发现，如果你把合法的配对数量画成图，它不是乱糟糟的曲线，而是一段一段的直线（分段线性）。
这就好比你在走楼梯，虽然台阶高度不一样，但每一段楼梯都是直的。只要知道你在哪一段楼梯上（由数字除以 3 和 $p$ 的余数决定），就能直接算出有多少级台阶，完全不用一级一级数。

4. 为什么这很重要？

速度极快：以前算大数字可能需要几小时甚至几天，现在用这个公式，电脑眨眼间就能算出来。
结构清晰：它揭示了数字背后隐藏的秩序。以前我们只知道大概有多少（估算），现在能知道精确是多少，而且知道了它们为什么长这样。
验证完美：作者用电脑把从 2 到 10 万的所有偶数都算了一遍，结果和“笨办法”数出来的完全一致，一个都不差。

总结

这就好比你要统计一个巨大迷宫里有多少条路。

普通人：走进迷宫，每条路都走一遍，数一遍。
作者：站在迷宫入口，看一眼地图，发现迷宫的墙壁是按照特定的数学规律排列的。他直接写下一个公式，告诉你：“只要你的入口编号是 X，你就有 Y 条路可走。”

这篇论文就是把这个**“看地图算路”**的公式给彻底推导出来了，让数学家们以后遇到这类问题，再也不用“数蚂蚁”了，直接“看地图”就行。

以下是基于论文《Exact Formulas for Coprime Representations of Even Integers Avoiding a Prime》（避免素数的偶数互质表示的精确公式）的详细技术总结：

1. 问题背景 (Problem Statement)

该论文研究的是加性数论中的一个经典计数问题：计算将一个固定的偶数 $2n$ 表示为两个正整数之和 $h+k=2n$ （满足 $h \le k$ ）的方法数，且这两个加数 $h$ 和 $k$ 必须与 $6p$ 互质（即 $\gcd(h, 6p) = \gcd(k, 6p) = 1$ ）。

约束条件： $p \ge 5$ 是一个固定的素数。这意味着 $h$ 和 $k$ 不能是 2、3 或 $p$ 的倍数。
目标函数：定义 $g(2n, p)$ 为满足上述条件的有序对 $(h, k)$ 的数量。
现有挑战：虽然通过筛法（Sieve methods）和 Möbius 反演可以得到该函数的渐近估计，或者通过容斥原理得到模 $6p$ 周期性的分段表达式，但这些方法通常涉及复杂的交错求和，无法直接揭示计数函数在算术级数上的仿射结构（Affine Structure），且计算效率较低（直接枚举需 $O(n)$ 时间）。

2. 方法论 (Methodology)

作者提出了一种基于余数算子（Remainder Operator）和欧几里得算法的显式构造方法，将问题转化为求解线性同余方程的最小解问题。

核心工具

规范余数算子 $\delta_k(x)$ ：
定义为 $\delta_k(x) = x - k\lfloor x/k \rfloor$ ，即 $x$ 模 $k$ 的标准代表元（取值范围 $0 $到$ k-1$）。该算子具有加法和乘法的兼容性，允许在整数域内直接处理同余约束。
线性余数方程的最小解：
利用扩展欧几里得算法，推导出了方程 $\delta_k(a_0 x) = b_0$ （其中 $\gcd(a_0, k)=1$ ）在 $\{0, \dots, k-1\}$ 中唯一解的闭式公式。该公式完全由余数算子和序列递归定义，避免了传统的逆元计算，直接给出了最小解的表达式。
互质分解的分类讨论：
由于 $\gcd(h, 6)=1$ $g cd (h, 6) = 1$ ，整数 $h$ $h$ 模 6 只能余 1 或 5。根据 $n \pmod 3$ $n (mod 3)$ 的不同， $2n$ $2 n$ 分解为两个互质数的形式分为三类：
- $n \equiv 1 \pmod 3$ ：两个加数均形如 $6x+1$ 。
- $n \equiv 2 \pmod 3$ ：两个加数均形如 $6x+5$ 。
- $n \equiv 0 \pmod 3$ ：一个加数形如 $6x+1$ ，另一个形如 $6y+5$ 。

关键步骤

排除素数 $p$ 的倍数：
对于形如 $6x+1$ 和 $6x+5$ 的数，利用 $\delta_p(6x+1)=0$ 和 $\delta_p(6x+5)=0$ 确定需要排除的余数类。
最小解参数化：
定义两个关键参数 $a(p)$ $a (p)$ 和 $b(p)$ $b (p)$ ，分别是同余方程 $6x \equiv -1 \pmod p$ $6 x \equiv - 1 (mod p)$ 和 $6x \equiv -5 \pmod p$ $6 x \equiv - 5 (mod p)$ 在 $\{0, \dots, p-1\}$ ${0, \dots, p - 1}$ 中的最小解。
- 作者给出了 $a(p)$ 和 $b(p)$ 的显式公式，它们仅依赖于 $p \pmod 6$ 的值。
- 利用欧几里得算法，这两个参数可以在 $O(\log p)$ 时间内预计算。
计数向量的构建：
将问题转化为在特定余数类中统计满足 $s+t = \text{const}$ 的整数对数量。通过引入指示函数（Step functions）和向量点积，将“严格有序对”和“对角线对”的计数统一表达。

3. 主要贡献与结果 (Key Contributions & Results)

理论成果

定理 4.13 (Theorem 4.13)：
给出了 $g(2n, p)$ $g (2 n, p)$ 的完全显式闭式公式。
- 公式仅包含基本算术运算、取整函数（ $\lfloor \cdot \rfloor$ ）、余数算子（ $\delta_k$ ）和阶跃函数。
- 公式根据 $n \pmod 3$ 分为两种情况（ $Q(n, p)$ 和 $Q_0(n, p)$ ），每种情况都明确依赖于预计算的参数 $a(p)$ 和 $b(p)$ 。
结构揭示：
证明了 $g(2n, p)$ 沿着 $n$ 的算术级数呈现**分段仿射（Piecewise Affine）**结构。这种结构由模 3 和模 $p$ 的余数类决定，这在传统的容斥原理公式中是不透明的。

算法效率

时间复杂度优化：
- 直接枚举：需要遍历 $1 $到$ n $，复杂度为$ O(n)$。
- 新公式算法：
  1. 预计算 $a(p), b(p)$ ： $O(\log p)$ （仅需一次）。
  2. 单次评估 $g(2n, p)$ ： $O(1)$ （常数时间，仅涉及基本算术运算）。
- 这对于大 $n$ 值具有巨大的计算优势。

验证

论文在 $2n \le 10^5$ 且 $p \in \{5, 7, 11, 13, 17, 19, 23\}$ 的范围内进行了全面的数值验证。
将新公式的计算结果与暴力枚举（Brute-force oracle）进行对比，所有 350,000 个测试用例均完美吻合。
提供了可视化的图表（Figure 1），直观展示了 $g(2n, p)$ 随 $n$ 变化的分段线性特征。

4. 意义与影响 (Significance)

计算数论的突破：
该工作将原本需要 $O(n)$ 时间的计数问题降低到了 $O(1)$ 时间，为大规模计算互质表示数提供了高效的工具。
结构洞察：
揭示了加性数论中此类计数函数内在的“分段仿射”几何结构，表明这些函数并非随机波动，而是由模运算的余数类严格控制的线性片段组成。
方法论的推广性：
作者指出，该方法可以自然推广到排除任意有限素数集合 $\{2, 3, p_1, \dots, p_k\}$ 的情况。虽然随着素数数量增加，情况分类会变得更加复杂（由模 $6p_1\dots p_k$ 决定），但核心逻辑（利用余数算子和最小解）依然适用。
实际应用：
对于需要快速生成或查询特定互质分解数量的算法（如在密码学、随机数生成或组合数学模拟中），该公式提供了即时的解析解，无需迭代。

总结

Andrés M. Salazar 的这篇论文通过引入基于欧几里得算法的显式余数解公式，成功解决了偶数互质表示计数的精确公式化问题。其核心创新在于将复杂的容斥原理转化为简洁的分段仿射表达式，不仅极大地提高了计算效率（从线性降至常数级），还深刻揭示了该计数函数背后的算术结构。