小名开开

担心 TF 卡易损坏导致重新配置系统的麻烦，我准备定期使用 dd 对树莓派进行全卡备份：

1

sudo dd if=/dev/mmcblk0 of=/mnt/momoda/$(date +%Y-%m-%d)-sysbak.img

尽管使用的是 64GB 的 TF 卡，生成的镜像文件也是 64GB。然而，实际系统盘的数据占用并不多，大部分空间是空白。因此，我选择通过管道压缩备份数据的方式以节省存储空间，并测试了几种支持管道的压缩算法的性能。

测试环境：

系统存储被分为 /dev/mmcblk0p1 和 /dev/mmcblk0p2 两个分区，实际上是同一张 TF 卡，目前总空间使用率约为 10%。目标是定期对全盘进行备份以应对意外，同时通过压缩方式保存数据，减少备份所需的存储空间。由于备份操作在运行中的设备上进行，数据在此期间仍可能被读写，因此选择的压缩算法需要尽可能高效，以减少数据变动的影响。

全盘空间信息：

1
2
3
4
5
6
7
8
9

~ df ⮐
Filesystem          1K-blocks       Used  Available Use% Mounted on
udev                  3728364          0    3728364   0% /dev
tmpfs                  799744       3176     796568   1% /run
/dev/mmcblk0p2       59551920    5034336   51780988   9% /
tmpfs                 3998704          0    3998704   0% /dev/shm
tmpfs                    5120         16       5104   1% /run/lock
/dev/mmcblk0p1         522232      66728     455504  13% /boot/firmware
tmpfs                  799740          0     799740   0% /run/user/1000

首先生成一个未压缩的镜像文件：

1
2
3
4
5

~ sudo dd if=/dev/mmcblk0 of=/mnt/exDisk/sys.img bs=4M ⮐
14909+1 records in
14909+1 records out
62534975488 bytes (63 GB, 58 GiB) copied, 1459.15 s, 42.9 MB/s
# 如果压缩算法在树莓派的 CPU 上能达到 42.9 MB/s 的处理速度，就可以认为压缩完全不影响原备份速度。

由于大部分空间是空数据，如果以 63GB 为基数计算，压缩后的文件大小差异将显得微不足道。因此，下表中的百分比均以 zstd 默认压缩率的结果作为 100% 的基准进行比较。

同时，受限于树莓派的储存方式，该镜像放在了另一台 NAS 上，两台机器间的传输能力为千兆有线，纯传输时间最低约为 536 秒。

测试结果

• 总体来看，zstd 的性价比明显高于 xz 和 7z 等其它算法。
• lz4 的速度极快。尽管没有多线程参数，单核性能仍快于其它算法的双核表现。然而，其较低的压缩率不适合作为备份用途，更适合处理持续性超大量数据的场景。
• 使用 lz4 -fast 时，压缩算法的数据吞吐量已经超过数据传输的上限。这是硬盘的瓶颈，不是算法的处理上限。
• 由于 TF 卡的读取速度更低，因此对于本文的需求而言，压缩时间低于 1459.15 秒时，是算法在等待数据读取，此时时间消耗的差异不再有区别。
• 综合考虑数据分布和性能表现，zstd -T2 -10 是当前测试中最合适的选择。可以进一步测试 -8、-12 等参数，以在 TF 卡读取时间内达到最佳压缩率。由于 TF 卡和 CPU 性能的差异，最佳方案会有所不同，需根据具体情况选择。
• 在测试过程中，发现 xz -9 和 7z -mx=9 运行时的内存占用也高达 2GB 多，如果是小内存版本的树莓派也根本跑不起来。

142857

近期刷到了一个视频，说 142857 这串数字如何的神秘，与古埃及有如何如何的关系。由于它分别乘以 1~6 都还是这串数，所以叫什么走马灯数，如何如何。抛开神秘学话题，这就是简单的 1/7 循环节：

不过『走马灯数』这个概念还是有点意思的。它最显著的特征是循环节长度 = n-1，同时附带的性质是当乘以 $1, 2, 3, \cdots, n-1$ 时，循环节顺序和长度不变，只是起始位置换了一下。因此写了段程序简单搜索一下还有没有其它的 n 也有这个特征。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

const loop = (n) => {
    let a = 1
    let pool = new Set()
    
    while (true) {  
        let digi = (a / n) | 0
        a = a % n * 10 
        if (a == 0) { return "" }   // 除尽没有循环节
        if (pool.has(a)) {          // 当余数作为被除数曾出现过，新的循环节开始。
            let loop = [...pool]
            let index = loop.findIndex(i => i == ele)
            let str = loop.slice(index).map(e => e % 10).join('')
            return str
        } else {
            pool.add(ele)
        }
    }
}

let start = 7
while (start < 1000) {
    let str = loop(start)
    if (str.length == start - 1) { console.log(start, str) }
    start++
}

结果出人意料地多：

简化代码并扩大计算量搜索后，得到 100 万以内的走马灯数分布：

1
2
3
4
5
6
7
8

const n_devide_len = (n) => {
    let a = 1, pool = new Set()
    while (true) {
        a = a % n * 10
        if (a == 0) { return 0 }
        if (pool.has(a)) { return pool.size } else { pool.add(a) }
    }
}

有点意思。

研究原因

对于任意由 1/n 形成的循环小数，$\frac{1}{n} = 0.\overline{******}$，设循环节部分为 r，其长度为 l，都可以写成一个无穷级数之和：

$$\frac{1}{n} = \frac{r}{10^l}+\frac{r}{10^{2l}}+\cdots+\frac{r}{10^{kl}} +\cdots = \sum_{k=1}^\infty\frac{r}{10^{kl}}$$

对这个无穷等比数列重新求和，$S=1/n$，$10^l * S-S = r$，得到 $S = \frac{r}{10^l-1} = \frac{1}{n}$，所以 $n=\frac{10^l - 1}{r}$ ，或者写成 $r=\frac{\overbrace{999\cdots999}^l}{n}$，根据前面的推导过程，这里的 r 一定是整数。这个方法同时也是将循环小数化为分数的标准方法。

• 当 $n = 7, l = 6$ 时，也就得到了 $142857 = \frac{\overbrace{999999}^6}{7}$，所以 $1/7 = 0.\overline{142857}$

• 当 $n = 3, l = 2$ 时，得到 $r = \frac{99}{3} = 33$，所以 $1/3 = 0.\overline{33}$，逻辑上其实也是对的，只是一般来说小数循环时只考虑最小周期，所以正确的写法应该是 $1/3 = 0.\overline{3}$。

• 当 $n = 11, l= 10$ 时，得到 $r = \frac{9999999999}{11} = 0909090909$，要注意这是循环节的计算因此首位的 0 不能去掉，所以 $1/11 = 0.\overline{0909090909}$，正写为 $1/11=0.\overline{09}$

对于 $1/6 = 0.1\overline{6}$ 这类存在非循环小数部分的，可以通过乘 10 等操作，把非循环部分移到整数上并抛弃，即化为 $10/6 \rightarrow 4/6 = 2/3 = 0.\overline{6}$，考察 $0.\overline{6}$ 即可。

同余

在上述 $n=3, n=11$ 两个例子中，虽然得到了逻辑上可行的循环节，但不符合通常的习惯，所以在结果上进行了缩减，变为符合习惯的最小循环节。

• $10^k-1$ 本身就是 3 的倍数，所以循环节永远只有一位。

• 11 因其自身的特殊性质，11 = 10 + 1，天然地符合 10 为底的级数的结构，如果一个数字各位数值相同，那么奇数位数字对 11 都是同余的，偶数位也是。所以 $10^k-1 (mod\ 11)$ 只有两个结果 9 和 0。并且在两者间不断跳转。

可见，循环节长度即是最早出现同余时的 k 值，若要 1/n 的循环节长度为 n-1，需要 $10^k (mod\ n)$ 在 $k = 1, \cdots, n-1$ 时都不同余。

进制

从上可见，循环小数与进制密切相关。例如在 8 进制中，9（在 8 进制中也写为 11）的性质将和 10 进制中的 11 相似，也会出现奇位同余偶位同余的情况。所以 $1/11_{(8)} = 0.\overline{07}_{(8)}$，形式上完全一致。

而 $1/7_{(8)}$ 则变为了 $0.\overline{1}_{(8)}$，因为 $8^k-1_{(8)} = {\overbrace{77\dots7}^{k}}_{(8)}$ 各位恒为 7，也就不存在什么神秘数字循环了。

由于和进制本身高度相关，因此某个 1/n 是否有 n-1 位循环节，取决于它和进制 $R^k - 1$ 之间的相除结果，这个关系不知道数论中是否已有结论。

推论

• 由于 n-1 位循环节一定存在，只是未必最短。而在 n- 1 基础上的缩减不会破坏原有模式，因此最小循环节长度一定是 n-1 的因数。

• 只有当 n 为素数时，才有可能出现 n-1 位循环节。由于余数需要遍历 1 到 n-1 的所有数。若 n = pq，余数会在 q-1 与 p-1 的共同作用下循环，但 p-1 与 q-1 至少含有公因素 2，不可能产生所有 {0, p-1} 与 {0, q-1} 之间的全部两两组合。

• 一切循环节在若干次乘 10 排除不循环部分，整理为 $0.\overline{******}$ 形式后，都可以用 $a * 1/n$ 来表示。

• 如果 n 为素数，而其循环节长度 $l$ 不为 $n-1$，则必有互相不能抵达的 $\frac{n-1}{l}$ 套循环，进入哪套循环取决于分子 $a$ 的值。因为素数没有因数，$a/n (a=1, 2,\dots, n-1)$ 必然有 n-1 个不同余数。实例如 $1/3=0.\overline{3}$ 和 $2/3=0.\overline{6}$。

• 如果 n 为素数，则 1/n 的循环节必然形如 $0.\overline{******}$，从小数点后就开始，即使起始是若干个 0 也是循环节的一部分。

• 如果 n 是若干个不同素数乘积，则循环节长度是这些素数对应的循环节长度的最小公倍数。如果 n 是素数 p 的 k 次方，则循环节长度是 $l * p^{k-1}$，但如果 $p=3$，则为 $l * p^{k-2}$。以上两者可以结合。$p=3$ 的特例在于 $p^2=9$ 仍然小于 10，没有触发进退位，即当 p^k 仍小于对应进制单位时，不往上叠加循环节长度。在 8 进制下就是正常的 $l*p^{k-1}$ 了。

• 不存在比 n-1 更长的循环节。

• 不同进制下的走马灯数具体是不一样的，例如 7 在 10 进制下是走马灯数，但在 8 进制下则不是。2 在一切奇数进制下都是走马灯数，因为只需要循环节长度为 1 但不除尽即可。

• 除 2 以外，走马灯数的循环节长必度是偶数，将循环节的两段拆分后相加，一定是 $999\cdots$。例如 $1/7 = 0.\overline{142857}$，则 $142 + 857 = 999$。上述结论在其它进制下也成立，例如 8 进制下为 $777\cdots_{(8)}$。

  证明：设一个循环小数 $\frac{1}{p}$ 的循环节两段分别为 $\overline{r_1r_2}$，则其既可以表达为

  \begin{align*} \frac{1}{p} = \frac{r_1r_2}{10^{2n}} + \frac{r_1r_2}{10^{4n}} + \cdots + \frac{r_1r_2}{10^{kn}}+\cdots = \frac{r_1r_2}{10^{2n}-1} &&(1) \end{align*}

  也可以表示为：

  \begin{align*} \frac{1}{p} =\frac{r_1}{10^n} + \frac{r_2r_1}{10^{3n}} + \cdots + \frac{r_2r_1}{10^{(k+1)n}}+\cdots &&(2) \end{align*}

  $(2)$ 式乘以 $10^n$ 再加 $(1)$ 式，得到：

  \begin{align*} \frac{(10^n+1)}{p} = r_1 + \frac{(r_1+r_2)(10^n+1)}{10^{2n}-1} = r_1 +\frac{r_1+r_2}{10^n-1} &&(3) \end{align*}

  再将 $(1)$ 式分子分母同除 $10^n+1$ 得到：

  \begin{align*}
  &&\frac{1}{p} = \frac{r_1r_2}{10^{2n}-1} = \frac{r_1r_2/(10^n+1)}{(10^{2n}-1)(10^n+1)} = \frac{\frac{r_1r_2}{10^n+1}}{10^n-1} &&(4) \\
  \Rightarrow &&\frac{r_1r_2 * p}{10^n+1} = 10^n-1 &&(5)
  \end{align*}

  $r_1r_2 / (10^n+1)$ 不可能为整数，否则 $(4)$ 直接可以化简：

  \begin{align*} \frac{1}{p} = \frac{\frac{r_1r_2}{10^n+1}}{10^n-1} = \frac{r_x}{10^n-1} &&(6) \end{align*}

  循环节直接可以减少一半，这与之前的假设不符。因此在 $(5)$ 式中，$p$ 与 $(10^n+1)$ 必然存在公因数。而 p 为素数，则 $(10^n+1)$ 为 $p$ 的倍数。即 $(3)$ 式中 $\frac{(10^n+1)}{p}$ 为整数。

  因此，$r_1 + \frac{r_1+r_2}{10^n-1}$ 为整数。$r_1$ 本来就是提出来的整数部分，而 $\frac{r_1+r_2}{10^n-1}$ 是由两个小数部分加和得到，要求其为整数只可能是 1。所以 $r_1+r_2 = 10^n-1 = 999\cdots$

  得证。其它进制只需要将 10 底替换为对应进制即可。

计算程序

走马灯数搜索程序在得到以上结论后可以提升一些效率：

• 使用 欧拉筛法，只在素数堆里进行验证。
• 如果循环节小于 n-1，由于推论 1，则其至多 $\frac{n-1}{2}$，因此当计算到第 $\frac{n+1}{2}$ 项时，便可得出结论而不必计算后半段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

function searchCarousel(n) {

    let primes = [];
    let eularboard = new Array(n + 1).fill(true);
    let carousels = []

    const isCarousel = (p, radix = 10) => {
        let a = 1, pool = new Set(), end = (p + 1) / 2
        while (pool.size < end) {
            a = a % p * radix
            if (a == 0) { return false }
            if (pool.has(a)) { return false } else { pool.add(a) }
        }
        return true
    }

    for (let i = 2; i <= n; i++) {
        if (eularboard[i]) {
            primes.push(i);
            if (isCarousel(i)) { carousels.push(i) }
        }
        for (let j = 0; j < primes.length; j++) {
            if (i * primes[j] > n) break;           // 上限判断
            eularboard[i * primes[j]] = false;
            if (i % primes[j] === 0) break;         // 跳过本轮后续筛选
        }
    }

    return carousels
}

console.log(searchCarousel(1000))
// [7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233,  257, 263,
// 269, 313, 337, 367, 379, 383, 389, 419,  433, 461, 487, 491, 499, 503, 509, 541, 571, 577,  593, 619,
// 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983]

其它进制

根据前文继续厘清思路，在其它进制下：

• 循环节长度的度量和进制数无关，表述形式不改变数值大小，在 10 进制下若为 16，在 8 进制下就写为 20，但都指的是同一个值。
• 但循环节的生成和进制有关，在当前位下不满足该进制条件下的整除，产生余数，就会退到下一位。
• 在其它进制下，$r = \frac{R^{n-1}-1}{n}$ 仍然成立，这是循环小数定义公式的变形。
• 仍然只需要在素数表中搜索走马灯数，因为 r 需要由 $\frac{k}{n},k=1,2,\dots,n-1$ 来确保循环长度上限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/* 计算各进制下的走马灯数 */
function searchCarousel(n) {
    let primes = [];
    let eularboard = new Array(n + 1).fill(true);
    for (let i = 2; i <= n; i++) {
        if (eularboard[i]) { primes.push(i) }
        for (let j = 0; j < primes.length; j++) {
            if (i * primes[j] > n) break;           // 上限判断
            eularboard[i * primes[j]] = false;
            if (i % primes[j] === 0) break;         // 跳过本轮后续筛选
        }
    }

    const isCarousel = (p, radix = 10) => {
        if (p === 2 && radix % 2 !== 0) return true // 2 在奇数进制下必然是 1 位循环
        let a = 1, pool = new Set(), end = (p + 1) / 2
        while (pool.size < end) {
            a = a % p * radix
            if (a == 0) { return false }
            if (pool.has(a)) { return false } else { pool.add(a) }
        }
        return true
    }

    for (thisRadix = 2; thisRadix < 100; thisRadix++) {
        let carousels = []
        for (let i = 0; i < primes.length; i++) {
            if (isCarousel(primes[i], thisRadix)) { carousels.push(primes[i]) }
        }
        console.log(thisRadix, carousels.length)
    }
}
searchCarousel(10000)

搜索在各不同进制下， 10000 以内的走马灯数的数量，结果如下：

这里最有特点的是当进制为偶数的完全平方时，没有走马灯数，当进制为奇数的完全平方时，只有唯一一个走马灯数 2，循环节长度为 1。

特殊进制 $R=s^2$

无论在哪种进制下，循环节公式 $r = \frac{R^{n-1}-1}{n}$ 都仍然是成立的。其中 $R$ 为指定的进制数，$n$ 为测试数字， $r$ 为对应的循环节。根据前文所述，在一些情况下循环节会缩减。即当 r 的数字序列内部出现重复时，需要用更短的循环节代替。前文 $\frac{1}{11} = 0.\overline{0909090909} = 0.\overline{09}$ 便是例子。

而当 $R$ 为完全平方数 $s^2$ 时，将循环节公式展开为；

$$ r_{(R)} = \frac{(s^2)^{n-1}-1}{n} = \frac{(s^{n-1}+1)(s^{n-1}-1)}{n} = (s^{n-1}+1) \cdot \frac{s^{n-1}-1}{n}$$

因为 $s$ 是整数，注意到 $\frac{s^{n-1}-1}{n}$ 实际上是在 $s$ 进制下的 $\frac{1}{n}$ 的循环节表达式 $r_{s(s)}$，必定是有整数解的，并且在 $s$ 进制下的长度至多为 $n-1$ 。

现在将 $r_{s}$ 的数值从 $s$ 进制转到 $R$ 进制。因为$R=s^2$，$R$ 进制下一位数值可以容纳 $s$ 进制下两位。其长度在转换后正好一半 $\frac{n-1}{2}$，n 为素数。则：

$$r_{(R)} =(s^{n-1} + 1) * r_{s(s)} \overset{s\rightarrow R}{=\!=\!=} (R^{\frac{n-1}{2}} + 1) * r_{s(R)}$$

除 2 以外的 n 都是素数，所以 $\frac{n-1}{2}$ 是整数，$(R^{\frac{n-1}{2}} + 1)$ 是形如 $\overbrace{100\cdots01}^{(n+1)/2}$ 的整数，长度上正好使 $r_{s(R)}$ 重复两遍，而不会有叠加进位。

因此当进制 $R$ 为完全平方数时，任意 $n$ 的 $r_{(R)} = \frac{R^{n-1}-1}{n}$ 数字序列至少会内部重复一次，所以长度一定小于 $n-1$，也就不存在跑马灯数。

推论：当进制 $R=s^{(2^n)}$ 时，对应的最长循环节为 $\frac{n-1}{2^n}$ 向上取整。

费马小定律

在前文中数次使用 $r=(R^{n-1}-1)/n$，并且认定它是整数，是因为该式是从循环节的级数表示法计算出来的，而循环节本身一定是 n-1 位的整数，所以认为是整数。这个推论是单薄的，不能证明任意 $(R^{n-1}-1)/n$ 一定是整数。但其实关于这一点的正向证明早就在三百多年前就被书空白写不下学家完成了：

$(R^{n-1}-1)/n$ 为整数，其实本身就是 费马小定理 的一部分，即：

• 假如 $a$ 是整数，$p$ 是素数，那么 $a^p \equiv a (mod\ p)$
• 如果 $a$ 不是 $p$ 的倍数，则 $a^{p-1} \equiv 1 (mod\ p)$，这其实就是我们用的循环节公式。
• 如果 $a$ 是 $p$ 的倍数，则 $a^{p-1} \equiv 0 (mod\ p)$，这时就除尽不构成循环节了。

我们之前提到，进制的转换会影响循环节数字序列的变化，但不影响素数、整除等基于数本身的性质，因此这里的 R 在整除判定上反而和进制本身没什么关系，就是一个单纯的幂底数。

简述

直接用浏览器打开 VMWare 的 CDS 地址：

https://softwareupdate.vmware.com/cds/vmw-desktop/

其中

fusion 目录是 MacOS 下的 VM Fusion，x86 和 M1 的 MacOS 都能用。
ws 目录是 VM Workstation。有 Windows 和 Linux 版。

一路点进去，选完版本号编译号系统版本后就可以下载 tar 包。用 7zip 等软件可以解压出 VMWare 的安装包。

比如发文时 ws 的最新版本号是 17.5.2，下载链接就是
https://softwareupdate.vmware.com/cds/vmw-desktop/ws/17.5.2/23775571/windows/core/VMware-workstation-17.5.2-23775571.exe.tar

记

自从被博通收购以后，VMWare 对个人用户免费了。虽然以前满地都是序列号，个人用户实质也是随便用的，但现在毕竟有官方直接授权了。但博通的帮助系统是真难用，找了半天找不到下载链接。然后想起 vmware 自带的更新是走一个 cds 的，尝试搜索了一下还在，这比在帮助系统里找方便多了。

记录一下。

记 II

遇到了 VMWare 17.5.1 跑 Windows XP 黑屏的 bug，搜索得知 VMWare 一直在不断地删减功能，未来甚至要把底层技术换成 KVM/HyperV，自己只做套皮。

又一个新版本不如老版本的软件。所以挖了一下把 CDS 上现有的老版本下载链接都提了出来。

1
2
3
4
5

wget -r -np -nd -e robots=off \
    --spider --wait=1 -l inf \
    https://softwareupdate.vmware.com/cds/vmw-desktop/ \
    2>&1 | grep -E '^--'  \
    | awk '{ print $3 }' >> links.txt

整理结果：

质数，也叫素数，是对 Prime Number 的不同翻译。素数的叫法大概率来自日语，素在日语里引申出了根本，源头以及不可再分割的意思，这一点古汉语里是没有的。因此诞生出了一大批和制词汇，比如元素，素材，要素等等，其中最有名的要数那个味之素了。而 Prime Number正好符合这个特性，叫素数再合适不过了。现代汉语由于引入了上面这些和制词汇，所以素也开始有了上述意思。至于港台地区保留了这个叫法也是因为延袭了民国时期的翻译习惯，没有做变更而已。

《为什么叫素数》 来源：Spenser Sheng 链接：https://www.zhihu.com/question/22456389/answer/967574484
至此，质数这个名词就在中国成了官方认可的科学术语，并一直没用至今。但是，素数这个说法并没有因此退出历史舞台。同时代的秀多著作，还是用了这个名词，比如华罗庚先生于1940年出版的《堆垒素数论》等。这直接影响了后来更多数学家在著书立说时没用素数这个名词（可能因为要考虑与他人表述的统一性），如陈景润研究“哥德巴赫猜想”也是讲素数。……在中小学教材上，目前是统一使用质数这个名词，但是标明了“质数，又叫素数”
《梳理源流，叩问本质——对质数、合数名词的考证与思考》顾志能 https://www.doc88.com/p-1478574668277.html

如何计算 N 以内的素数，或者判断 n 为素数，在编程领域是孪生的两个问题，也是很多编程语言的入门题目。这个题目优点在于有相当多的解法和优化空间，尤其适合用来练习算法和程序优化。这里我们就来逐步优化一个素数计算程序。

基础实现

我们从最简单的开始，先写一个函数 isPrime(n) 判断 n 是否为素数，这个判断函数严格按素数的定义实现：

除了 1 和 n 之外，没有其他整数能整除 n

也就是说，将 2 ~ n-1 之间的每个整数都试一遍，看看是否能整除 n。再用 isPrime(n) 逐个找出 <N 的所有素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function isPrime(n) {                   // 判断 n 是否为素数
    for (let i = 2; i < n; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

function calcPrimes(n) {                // 找出 <N 的所有素数
    let primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime(i)) { prime.push(i) }
    }
    return primes;
}

console.log(calcPrimes(100));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

※ 本文演示代码为 JavaScript，方便在浏览器控制台内测试。但考虑到与正文内容保持一致，并未使用 JavaScript 内置的 .map(), .forEach(), .filter() 等遍历函数，而只用普通的 for loop if else 等代码。

简单优化

显然上面的代码是有很多无效的计算的，一些简单的数学知识就可以大幅地优化计算效率：

1. 所有的偶数都不是素数，除了 2。

1
2
3
4
5
6
7

function calcPrimes(n) {
    let primes = [2];                        // for 循环从 3 开始，因此直接把特例 2 加入
    for (let i = 3; i <= n; i=i+2) {         // 从 i++ 优化为 i=i+2
        if ( isPrime(i) ){ prime.push(i) }
    }
    return primes;
}

2. 同上，所有 3 的倍数都不是素数，除了 3。因此，我们可以只检查 6k ± 1 的数。

1
2
3
4
5
6
7
8

function calcPrimes(n) {
    let primes = [2,3];
    for (let i = 6; i <= n; i=i+6) {            // 计算 6k
        if ( isPrime(i-1) ){ prime.push(i-1) }  // 判断 6k-1
        if ( isPrime(i+1) ){ prime.push(i+1) }  // 判断 6k+1
    }
    return primes;
}

※ 理论上我们可以继续讨论 5 的倍数，但这会使 for 循环需要处理 30k ± a，且 a 有 1,7,13 等多个值。代码变得复杂，而优化效果一般。过于复杂的代码会让你不幸福。

3. 判断素数时，只需要检查到 sqrt(n) 即可。如果 n 有一个大于 sqrt(n) 的因子，必然对应一个小于 sqrt(n) 的因子，则之前的循环中已经判断过了。

1
2
3
4
5
6
7

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i*i <= n; i++) {     // 从 i < n 优化为 i*i <= n
        if (n % i === 0) return false;
    }
    return true;
}

更多优化

进一步思考 isPrime 函数，我们发现，不必让所有小于 sqrt(n) 的数都试一遍，只需要用之前已经计算出来的素数尝试即可。但我们需要整体调整代码，使 isPrime() 函数可以调用 primes 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function calcPrimes(n) {
    
    let primes = [2, 3];

    function isPrime(n) {
        for (let i = 0; primes[i] ** 2 < n; i++) {  // 在 isPrime 函数中可以直接使用 primes 数组
            if (n % primes[i] === 0) return false
        }
        return true;
    }
    
    for (let i = 6; i <= n; i=i+6) {
        if ( isPrime(i-1) ){ prime.push(i-1) }
        if ( isPrime(i+1) ){ prime.push(i+1) }
    }
    
    return primes
}

console.log(calcPrimes(100))
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

筛法

以上的方法都是用较小的数字去尝试整除 N 以判断 N 是否为素数，这种方法称为试除法。从直观考虑，每个 N 都会被 2,3,5 ... 等数字都除一遍，比如 49 和 77 都会在 2, 3, 5 上各浪费三次计算。如果可以绕过无效除法，只用 7 去尝试 49，而 2,3,5 则不去浪费时间，耗时会大幅会降低。事实上这种方法是存在的，并且非常简单，称为『筛法』。

简单到解释起来只需要两句话：

• 从 2 开始，将所有 2 的倍数都划掉；从 3 开始，将所有 3 的倍数都划掉；从 5 开始，将所有 5 的倍数都划掉；
• 以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function calcPrimes(n) {

    let primes = [];
    let numboard = new Array(n+1).fill(true);

    for (let i = 2; i < n; i++) {
        if ( numboard[i] ) {
            primes.push(i);                         // 将素数加入 primes 数组
            for (let j = i * 2 ; j < n; j += i) {   // 将 i 的倍数都划掉
                numboard[j] = false;
            }
        }
    }

    return primes;
}
console.log(calcPrimes(100))
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

这个筛法也被称为埃拉托斯特尼筛法，是为了纪念古希腊数学家埃拉托斯特尼而命名的。这个方法看似很简单，实际也确实很简单，是一种朴素的空间换时间方案。算法改除法为乘法，同时避免互质两数相遇，避免了很多无效运算。虽然当 N 非常大时，numboard 数组会占用很多内存，但时间优势更为明显。

※ 由于这个方法如此简单，普通人也能想到，不值得特地冠名。我猜测这个名字只是为了纪念历史名人，不能说明是他最早发明了这个方法。

同样，上述代码也有一些优化空间，比如：

• 划掉倍数时，可以从 j = i*i 开始，因为 2i, 3i ... (i-1)i 在对应的 2, 3 ... i-1(或其因数)那一轮时已经被划掉了。
• 当划到 i > sqrt(N) 时，则剩余未标记数也都是素数。假设有任意合数 m 满足 sqrt(N) < m < N，则 m 的素因数 p1,p2 ... 中最小的一个 p 也必然小于 sqrt(N)。而我们已经找到所有小时 sqrt(N) 的素数，并划掉其倍数了，所以找到 p 时必定已经划掉 m。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function calcPrimes(n) {

    let primes = [];
    let numboard = new Array(n + 1).fill(true);
    let sqrt_n = Math.sqrt(n);

    for (let i = 2; i <= n; i++) {
        if (numboard[i]) {
            if (i > sqrt_n) break                   // 根据上文证明，剩余未标记数也都是素数
            for (let j = i * i; j < n; j += i) {    // j = i * 2 -> j = i * i
                numboard[j] = false;
            }
        }
    }

    for (let j = 2; j <= n; j++) { 
        if (numboard[j]) { primes.push(j) }      // 清点未标记数
    }

    return primes;
}

console.log(calcPrimes(100))
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

在算法进入筛法层次后，isPrime() 函数与 calcPrimes() 函数的功能区别也就不再明显。为了判断 N 是否为素数，需要至少计算到 sqrt(N) 的素数，而上文又证明剩余的未标记数也都是素数。差别只是最后判断一下 N 是否在 primes 数组中而已。

另外，在埃氏筛法中，6k ± 1 等手段不再有优化作用。构造一个『只有奇数的筛盘』是可以的，但后续的划除操作需要大量的脚标奇偶运算，反而会增加计算量。

位运算

在埃氏筛法中，内存占用是一个问题，尤其在筛法本身就是为了计算大 N 而生的。在实际应用中，有时也需要在有限的内存空间内尽量优化。注意到 numboard 数组只是用来标记是否为素数，只需要 0,1 两个状态，因此可以用位运算来减少内存占用。这使得内存的占用降为原来的 1/8。但此时算法的实现与编程语言也开始耦合，不是每种编程语言都支持直接的位运算，例如 JavaScript 的位运算就只是某种『模拟』，效率并不高。Javascript 也不支持直接修改某个 bit 位，而要经过多次字节操作来实现。尽管如此，我们仍可以编写一个 setBitFalse() 函数来模拟这个操作：

1
2
3

function setBitFalse(arr, i) {
    arr[i >> 5] &= ~(1 << (i & 31));
}

代码解释：

• JavaScript 里数值默认 32 位，通过 i >> 5 相当于 i/32 取整，可以得到对应的数组下标，即具体操作哪个元素。
• i & 31 将 i 与 31 (00001111) 进行按位与操作，相当于对 32 取余，得到具体操作该元素的第几个 bit 位。
• 1 << (i & 31) 将 1 左移 i & 31 位，得到一个只有第 i & 31 位为 1 的数，即只有指定 bit 位是 1 其它都是 0 的掩码。
• ~( ... ) 按位取反以后就得到了 1111....0...111 的反掩码，只有指定 bit 位为 0。
• &= 是按位与且赋值，将数组指定元素与反掩码进行按位与运算，其它位与 1 后值不变，指定 bit 位则变为 0。目标达成。

然后，我们需要写一个 isBitTrue() 函数来判断某个位是否为 1：

1
2
3

function isBitTrue(arr, i) {
    return (arr[i >> 5] & (1 << (i & 31))) !== 0;
}

类似地，函数计算数组下标和 bit 位置，生成一个只有指定 bit 位是 1 的掩码，将其与数组元素进行按位与操作。因为按位与操作遇 0 必 0，所以其它位都会被掩码数值置为 0。如果结果不为 0，则说明数组元素与掩码在该 bit 位上都是 1。

最后，我们还需要写一个 bitsToNums() 函数，将位运算后的结果数组转换为素数数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function bitsToNums(arr,n) {
    let primes = [];
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < 32; j++) {
            if (arr[i] & (1 << j)) {           
                primes.push(i * 32 + j);
            }
        }
    }

    let real_primes = [];
    for (let j = 2; j <= n; j++) {
        real_primes.push(primes[j])   
    }
    // 因为是字节位长的整倍数，位运算可能会多一些数字，因此要二次筛选一下
    let real_primes = [];
    for (let j = 2; j <= n; j++) {  
        if (primes[j] <= n) real_primes.push(primes[j]) else break;
    }

    return real_primes;
}

将几个函数代入原程序中的对应位置，我们可以得到一个位运算版本的埃拉托斯特尼筛选算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function calcPrimes(n) {
    let bitboard = new Array((n >> 5)+1).fill(-1);  // 位运算数组
    let sqrt_n = Math.sqrt(n);

    for (let i = 2; i <= n; i++) {
        if ( isBitTrue(bitboard, i) ) {
            if (i > sqrt_n) break;
            for (let j = i * i; j <= n; j += i) {
                setBitFalse(bitboard, j);
            }
        }
    }

    return bitsToNums(bitboard);
}

console.log(calcPrimes(100))
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

可以看到，位运算版本的代码更为复杂，原本只是根据下标取数组元素并判断 true/false 的操作，现在需要生成掩码，计算偏移量，转换位数等多次计算。只有在 N 极大，以至于必须减少内存占用的情况下，才需要使用位运算。在一般情况下并不值得作此妥协。

同时，对于 JavaScript / Python / java 等高级语言，位运算的效率并不高。即使实际情况确实拮据，也必须先考虑更换编程语言。比如在 C++ 中，std::bitset 这种数据结构，就特别适合于埃氏筛法结合位运算计算素数表。

分段筛法

说到内存不足，很容易就能想到另一种解决方案：分段筛法。在筛选过程中，我们把素数放进了单独的 primes 数组，而 numboard 数组则只是用来筛除合数。当 primes 找到大小为 p 的素数，就意味着 p*p 之前的 numboard 数据已经没有用了，如果我们能把这部分内存释放掉，就能大幅减少内存占用。

因此从逻辑上讲，当求 N 以内的素数时，我们只需要保留 sqrt(N) 以内的素数，并将整个 N 范围划为若干块，对每一块使用 primes 数组进行筛选。如果不考虑分块本身的内存分配回收时间，单只考虑数值与操作量的话，分段筛法的时间复杂度与原始筛法是相同的。对于每一个被筛选的元素，都会被其每一个独特的素因数筛选一次，无论是在全局 numboard 中，还是在局部 numboard_i 中，都一样。

基于前文的铺垫，似乎分块大小设置为 sqrt(N) 是直觉上合理的方案。但实践中，分块大小更多与内存大小有关。比如 nodejs 的默认内存上限为 2GB，尽管可以通过 --max-old-space-size 参数调整，但在个人电脑环境下再提升其实也并不会有什么质变。只要确保 primes 数组空间的前提下仍有足够的内存，就是合理的块大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// JavaScript 数值默认 4Byte，1GB 内存可以存储 2^28 个数值。约 2.68 * 10^8 个。
const BOARD_SIZE = 10                              // 分块大小，基于演示目的设置为 10

function calcPrimes(n) {
    let primes = [];

    function cleanBoard(s, e) {                    // 分块筛选区间 [s, e] 素数的子函数
        let board = new Array(e - s + 1).fill(true);
        let sqrt_e = Math.sqrt(e);

        for (let i = 0; i < primes.length; i++) {  // 用先前得到的素数筛选本区间
            let p = primes[i];
            let start = Math.ceil(s / p) * p
            for (let j = start; j <= e; j += p) {
                board[j - s] = false;
            }
        }

        for (let i = 0; i < board.length; i++) {    // 本区间埃筛
            if (board[i]) {
                let p = i + s;
                if (p > sqrt_e) break;
                for (let j = p * p; j <= e; j += p) {
                    board[j - s] = false;
                }
            }
        }

        for (let i = 0; i < board.length; i++) {    // 清点本区间的素数
            if (board[i]) {
                primes.push(i + s);
            }
        }

    }

    cleanBoard(2, Math.min(BOARD_SIZE - 1, n)); // 第一个区间特殊处理，去掉 0 和 1
    for (let i = 1; i < Math.ceil(n / BOARD_SIZE); i++) {
        cleanBoard(i * BOARD_SIZE, Math.min((i + 1) * BOARD_SIZE - 1, n));
    }

    return primes;
}

console.log(calcPrimes(100))
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

欧拉筛法

在埃氏筛法中，我们注意到，数字 6 会被 2, 3 划掉两次，30 会被 2, 3, 5 划掉三次。所有合数都会被其不同的素因数重复操作若干次，浪费还是有不少。但我们并不能去判断筛盘上某个具体的数是否已经划掉，因为『读取与判断』的时间本身可能比直接划掉时间还长。

进一步用力注意到，筛法的本质是从『验证素数』变成了『排除合数』，而且是有规律的排除合数。考察一个合数 6 = 2 x 3，我们希望在算法中，2 x 3 只发生一次，而不是在 2 与 3 的循环中各发生一次。对于 12 也一样，尽管它有 2 x 2 x 3, 4 x 3, 6 x 2 这三种分解方式，但我们希望只有其中一种发生，其它的被跳过。

仿佛一头雾水但哪里又有一些灵感，这好像是可能的，只要足够聪明合理地安排合数生成，好像可以做到？

事实确实如此。欧拉筛法就是为了解决这个问题而生的。具体操作是这样的：

1. 有一个自增的数字 i，从 2 开始。
2. 有一个数组 primes，存放已经找到的素数。
3. 如果筛板上 i 还没被划掉，则 i 是素数，将其加入 primes 数组。
4. 用每一个 i 乘以当前所有 primes 中的素数，得到的数都是合数，在筛板将它们标记为 false 划掉。
5. 如果 i 是 primes 中某个素数的位数，那么 i * p 这个数会被标记 false，但后续直接跳过，进到 i+1 轮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function calcPrimes(n) {

    let primes = [];
    let eularboard = new Array(n + 1).fill(true);

    for (let i = 2; i <= n; i++) {
        if (eularboard[i]) {
            primes.push(i);
        }
        for (let j = 0; j < primes.length; j++) {
            if (i * primes[j] > n) break;           // 上限判断
            eularboard[i * primes[j]] = false;
            if (i % primes[j] === 0) break;         // 跳过本轮后续筛选
        }
    }

    return primes;
}

console.log(calcPrimes(100))
// [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

在欧拉筛中，我们通过 i * primes[j] 的方式来划除合数，且当 i 本身为 primes[j] 的倍数时，跳过 i 与后续素数的计算环节。比如在 i = 4 时，原本应该划掉 4 x 2 与 4 x 3 两个数字，但我们其实可以跳过 4 x 3，因为它一定会被后续的 6 x 2 划掉。在 i = 35 时，先会划掉 35x5，而后的 35x7 会在 i = 49 时被 5 划掉，此时也可以跳过。一般来说，如果 i=k * primes[j]，则接下来要划掉的 s = i * primces[j+1] = k * primes[j] * primces[j+1] = (k * primes[j+1]) * primces[j] 未来在 i' = k * primes[j+1] 轮次时会被 primes[j] 划掉，所以此时可以先跳过。

可以看到，在欧拉筛法中，由于 primes 是从小到大排列的，因此每个合数只在其最小素因数 m 对应的 i = n / m 轮次时，才会被划掉。

在这个算法中，合数的分解是唯一且有序的，因此欧拉筛与埃筛内存占用一样，但算法复杂度优化到了大约 O(n)。——严格来说，因为一些必须的额外判断，实际是 $O(nlog_2log_2n)$。

※ 数学先师的伟业至今仍被人传颂，作为一个在计算机远没有出现的 18 世纪数学家，有一个算法以他的名字命名。

素数的分布

有了高效的素数筛选算法，我们可以开始搜索大范围的素数了。计算 1 亿以内的素数，并每 10 万分为一组，统计每组的数量。可以看到，虽然有波动，但整体是逐渐减少的，并且这个图好像有点眼熟？

事实上，确实有一个 素数渐近分布定理，大致描述了素数的分布规律：

设不大于 n 的所有素数的个数为 π(n)，则 π(n) ≈ n / ln(n)

具体举例来说，当 n = 1 亿时，使用前文的程序计算出素数具体有 5761455 个，而 $n/ln(n)\approx 5428681$，两者比例为 1.061，较为近似。而当 n→∞ 时，值趋近于 1。

另外也可以得到一个推论，在 n 附近随机取一个数字，它是素数的概率是 $P(n)\approx 1/ln(n)$。函数下降不算快，就算 n = 1亿，概率也有 1/18.42，5.43%。

这个定理已经被证明，但这个值本身只是一个渐近值。也就是说，虽然 $\lim\limits_{x \rightarrow 0}\frac{\pi(n)}{ n / ln(n)} = 1$，但 $\lim\limits_{x \rightarrow 0} [\pi(n) - n / ln(n)]$ 却是越来越大的。从函数图像上而言，两者只是越来越接近于平行，但距离却越来越远。

素数的分布规律是数论的一个重要研究方向。后来数学家又提出了几个更精确的估算公式，这一方向的顶点便是著名的黎曼猜想。

梅森素数与 Lucas-Lehmer 检验。

在了解素数的大致分布，并回顾欧拉筛法以后，我们发现即使是 O(n) 的算法也仍然有很大的局限性。内存限制是最初的现实问题，但也只是所有问题中最简单的一个，更大的限制仍然是来自于算法本身。我们要筛到至少 sqrt(N)，才能得到 N 是否为素数的结果。在 N 非常非常大时，O(n) 的算法仍然太慢了。

仔细思考发现，这是因为筛法天然地要求算法结果的素数是连续的，如果跳过某个数，那么后续的合数也可能被认为是素数，整体就会崩盘。那么是否存在『跳过一部分数，快速往更大的素数 N 前进』，以及在不知道小于 sqrt(N) 全部素数的情况下，判断 N 是否为素数的算法呢？

两者都是存在的，并且有多种方法。典型的一个例子是梅森素数和配套的 Lucas-Lehmer 算法。

梅森素数是形如 $2^p - 1$ 的素数，并且简单可以证明，当 $2^p - 1$为素数时，p 也是素数。

当 p 是合数时，令 p = ab，有：
$2^p-1= (2^a)^b - 1 \overset{ x=2^a}{=\!=\!=} (x - 1)\cdot[x^{b-1}+x^{b-2}+\cdots+x+1]$ 为合数。

尽管反过来并不一定成立，当 p 是素数时，$2^p - 1$ 仍可能是合数，比如 2^11 - 1 = 2047 = 23 x 89。但即使如此，梅森素数依然有很多优点，比如：

• 比普通的序列增长得更快，可以跳过很多中间的数，尽快找到更大的素数。
• $2^p - 1$ 中包含素数的比例比全体自然中要高，因此更容易找到素数。
• 否定性验证很容易，只需要验证 p 是否为素数。正向验证难度也比一般的低。

Lucas-Lehmer 算法是验证梅森素数的一种方法。它构造了一个递推公式：

\begin{equation*}
s_i=\begin{cases} 4, & i=0 \\ (s_{i-1}^2-2) \mod (2^p-1), & i>0 \end{cases}
\end{equation*}

则当 $s_{p-2} \equiv 0 \pmod{2^p-1}$ 时，$2^p - 1$ 为素数。其算法复杂度为 $O((log\underset{2}{}n)^2)$。

※ 在大数环境下的计算需要编程语言和专门的数学包支持，代码就不放了

由于梅森素数拥有的诸多优点，目前已知的最大素数都是梅森素数，也有专门的 互联网协作项目 GIMPS 来众算更大的梅森素数。该项目前段时间正好确认了 M(57885161) 是一个新发现的素数。

质性检验

从梅森素数我们得到启发，在合理添加一些额外的限制条件后，素数的出现概率会提高，检验手段也可以针对性设计而变得简单，这对大素数的搜索非常有帮助。

在这个层次上，calcPrimes() 基本就不再是人们的目标，而 isPrime() 则不断地发展，成为专门的『质性测试』算法。这些算法的目标是尽可能快地判断一个数是否为素数，而不是找到所有素数。在这个领域，有很多经典的算法，比如：

Lucas-Lehmer 检验

上文提到的梅森素数检验算法。仅适用于 $2^p - 1$ 形式的素数。

Pépin 检验

验证费马数 $2^{2^n} + 1$ 是否为素数的算法。但由于费马数目前只发现 n=0,1,2,3,4 五个，后面都是合数，甚至有猜想认为 n > 4 时皆为合数。因此 Pépin 检验的应用范围有限。

而欧拉和卢卡斯接力证明了费马数的素因数皆可表达为 $k^{2n+2} + 1$，为具体的因数分解也提供了不小的方便。

※ 感觉 Pépin 被费马坑了。

Miller-Rabin 素数测试算法

一个随机性的否定性算法。当测试结果为 false 则一定是合数，测试结果为 true 可能为素数。算法基于费马小定理和二次探测定理，在进行 n 次测试后，错误概率为 $1/4^n$。

费马小定理：如果 p 是一个素数，而 a 是任意不是 p 的倍数的整数，则 $a^{p-1} ≡ 1 (mod\ p)$。这意味着对于任意素数 p，选择一个不是 p 的倍数的整数 a，计算 $a^{p-1}\ \% \ p$，如果不等于 1，则 p 一定不是素数；等于 1，则 p 可能是素数 。
二次探测定理：假设 p 是一个素数，我们可以将 p-1 写为 $2^s * d$ 的形式，其中 d 是奇数。则对于任意整数 a，如果存在整数 x 满足：

1. $a^d ≡ 1 (mod\ p)$
2. 存在一个 i 满足 0 ≤ i < s，使得 $a^{2^i * d} ≡ -1 (mod\ p)$

以上两个条件之一，则 a 是一个模 p 的非平凡平方根，即 $a^2 ≡ x (mod\ p)$：

假设我们要测试数字 p = 17 是否为素数。

1. 选择不是 p 的倍数的整数 a，假设选择 a = 3。计算 $a^{p-1}\ \%\ p = 3^{16} \% 17 = 1$ 结果等于 1。根据费马小定理，17 可能是素数。

2. 根据二次探测定理，当 p = 17，有 $p-1=16=2^4*1$，因此 s = 4，d = 1。我们需验证任意整数 a，可以满足以下两个条件之一：

   • $a^d = a ≡ 1 (mod 17)$
   • 存在一个 i 满足 0 ≤ i < 4，使得 $a^{2^i} ≡ -1 (mod 17)$

   假若仍然选择 a=3，则 $3 \% 17 =3 \neq 1$，不满足条件一，继续检验条件二：

   • $i=0, 3^{2^0}\ \% 17 = 3$
   • $i=1, 3^{2^1}\ \% 17 = 9$
   • $i=2, 3^{2^2}\ \% 17 = 13$
   • $i=3, 3^{2^3}\ \% 17 = 16 = -1$，满足条件。因此 17 可能是素数。

继续类似地进行多轮测试，如果任意轮 a 的验证失败，则 p 一定是合数，反之可能是素数。

AKS 类质性测试

一个确定性的质性测试算法，复杂度为 $O(log^{6+\epsilon}n)$。AKS 是第一个被发表的一般的、多项式的、确定性的和无依赖的素数判定算法。算法基于一个简单定理：

当 $(x+a)^n\equiv(x^n+a)(\text{mod}\ n)$ 时，n 为素数。

后续 ASK 被不同科学家多次改进，因此有多个版本，统称为 AKS 类算法。AKS 类算法也是目前效率最高的确定性算法，只要算法给出 true 的结果就一定是素数。

※ ChatGPT 与 Copilot 对本文亦有贡献。

1. 不放回抽取

从一套充分洗匀的扑克中不放回地一直抽，直到抽到两张大小王都抽到，一共抽了多少张的期望值？

先说结论：

一般地，从 $n$ 张牌中不放回地抽取特定 $k$ 张，期望抽取次数是 $Exp = k \cdot (n+1)\ /\ (k+1)$

然后说证明：

首先，在充分洗匀的情况下，从牌堆顶部抽取和从牌堆中间任意位置抽取是等价的，所以可以假设牌堆是从左到右的展开一列，抽取动作等效于从左开始逐张提取卡片，直到所有目标牌都抽取到手里。想像 k 张目标牌已经排成一列，其顺序无关紧要因为最终都会被清空。这 k 张牌相隔包括左右外侧共产生 k+1 个空隙：

然后将 n-k 张非目标牌随机插入这 k+1 个空隙中，每个空隙插入的概率相等，所以期望张数是 $\frac{n-k}{k+1}$。

最后考察清点过程，显然最右侧外侧可以抛弃，所以需要抽取的期望张数是 $n - \frac{n-k}{k+1} = \frac{k \times (n+1)}{k+1}$。得证。

这类抽奖励在各类游戏中都有，其特点是：

• 奖池有限
• 不会抽到重复的奖品
• 通常玩家心仪的是奖池中的几个特定奖品，其它是无关紧要的

有些游戏会添加『升星级』的设置，某个抽卡人物 A 多次抽到后，会升级为 A+，A++ 等。这种情况完全可以视为若干个独立的 A 在奖池中，需要全部抽齐，计算时调整 n 与 k 的值即可。

—— 算下来『全部抽齐』确实是成本很高的目标。

2. 放回抽取

在数量为 n 的奖池中进行抽取，抽取结果是可重复的（抽完放回），抽完所有 n 件奖品的期望抽取次数是多少？

$$Exp= n \cdot (1 + 1/2 + 1/3 + \cdots + 1/n) = n \cdot \sum _{i=1}^n \frac{1}{i} = n \cdot H_n $$

$H_n$ 就是调和级数。

证明，从后往前考察抽取过程：

• 如果当前只剩最后一件奖品没抽到，则从 n 件奖品中抽取特定一件的几率是 1/n，期望抽取次数是 n。
• 如果剩最后两件奖品没抽到，只要从 n 件奖励中抽到这两件的任意一件，就会进入上一条的『只剩一件』状态。抽到这两件奖励之一的几率是 2/n，期望抽取次数是 n/2。
• 每抽到一件新的就会进入下一个状态。而在任意某个状态时，当前对应的期望抽取次数是总数 / 剩余新奖品数。
• 因此，总的期望抽取次数是所有状态的期望抽取次数之和。

调和级数是发散的，可以用 Excel 等工具计算期望值，也可以用近似公式 $H_n \approx \ln n + C + 1/2n$ 算。这里的 $C$ 就是欧拉常数，约为 0.5772156649。

进一步的，如果不需要抽完，而只是抽取其中的特定 k 件奖品，仍可以从最后一件倒数推算，其期望抽取次数是：

$$Exp = \frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{k-1} + \frac{n}{k} = n \cdot H_k$$

3. 放回抽取，不同概率

在各类游戏中，奖励物品往往有不同的『品质』等级，以及不同的出现概率。可以简单理解为

奖池分为 $m$ 个小奖池，每个小奖池进入概率分别为 $p_1, p_2, \cdots, p_m$，奖品数量分别为 $n_1, n_2, \cdots, n_m$。获得整个奖池全部奖励的期望抽取次数 $N$ 是多少？

对于每个小奖池，期望抽取次数是 $n_i \cdot H_{n_i}$，再除以小奖池本身的概率 $p_i$，即得 $N_i=n_i\cdot H_{n_i} \ /\ p_i$。但对于整个奖池，总期望抽取次数 $N$ 不是所有小奖池的次数之和，而是它们之中的最大值。因为当有 $n_i = p_i\cdot N$ 的抽取次数落到 $i$ 号小奖池时，也有对应的 $(1-p_i) N$ 溢出到其它小奖池。最大值保证溢出部分覆盖其它小奖池的期望抽取次数。随意举例如下：

总抽取次数 $N$ 会以 $0.01:0.09:0.3:0.6$ 的比例分配到四种品质中。观察表格，橙色传说所需的抽取次数最多，且溢出部分按比例仍可以覆盖其它所有奖池的有效抽取次数，也就是说抽到 2929 次时，期望可以让全部 10 件橙色传说抽取到手里。此时溢出的 2899 次已经完全覆盖了其它三种品质的有效期望抽取次数。所以 $$Exp = Max\left(n_i \cdot H_{n_i} \ /\ p_i\right)$$

进一步考虑发现，只要每个小奖池的期望有效抽取次数和设定的小奖池进入概率比例不一致，则一定会有一个小奖池的期望抽取次数最大。如果正好一致，也意味着每个都是最大值。这个结论是普适的。

4. 放回抽取，反还比例

在某些游戏中，抽取到重复奖品时，会通过『碎片』等给予一定的返还比例，若干个碎片可以合成需要的道具。先考虑单个奖池的情况：

假设奖池中有 n 件奖品，抽取概率相同。抽到重复奖品时，返还比例是 r(r<1)，那么抽取次数的期望值是多少？

没有傻逼会去合成已经存在的道具，所以返还可以视为抽取了 r 个新道具。同时由于 r <1，重复的价值仍是小于不重复的，因此在确保碎片可以合成奖池所有剩余奖品前，应当不合成任何奖励减少重复，使得整体收益最大化。再次从后往前考察抽取过程：

• 如果只差最后一件奖品没抽到，那么我仍需要从 n 件奖励中抽取，抽到这件奖励的几率是 1/n，期望抽取次数是 n。其中 1 次是有效抽取，n-1 次是重复抽取，返还 r(n-1) 碎片。
• 如果剩最后两件奖品没抽到，只要从 n 件奖励中抽到这两件的任意一件，就会进入『最后一件』状态，抽到这两件奖励的几率是 2/n，期望抽取次数是 n/2。其中 1 次是有效抽取，n/2-1 次是重复抽取，返还 r(n/2-1) 碎片。
• 以此类推，在 n 奖池中抽取到 t 个奖品时，对应的总抽取碎片为：

\begin{align*}
R(t) &= r\cdot(n-1) + r\cdot(\frac{n}{2}-1) + \cdots + r\cdot(\frac{n}{t-1}-1) +r\cdot(\frac{n}{t}-1) \\
&= r \cdot \sum_{i=1}^t \left( \frac{n}{i} - 1 \right) \\
&= r \cdot \left( nH_t - t \right) \\
\end{align*}

在某个节点 $t=k$ 时，获得的碎片就已经足够合成了所有剩余的奖品，即 $R(k) \geq n-k$。因为 $R$ 单调递增，$k$ 必然存在，此时对应的期望抽取次数即是 $n \cdot H_k$。$k$ 的通式求解超出了我的能力，但使用 Excel 或编程求解在有限的 n 范围内仍是方便的。

5. 放回抽取，反还比例，多个奖池

假设还是 $m$ 个分概率的小奖池，但返还的碎片是通用的，那么全部奖品的总抽取次数期望值是多少？

这里需要再添加一个参数，每个奖池的相对价格是不同的，设为 $c_i$。在 r 相同同，高价值奖池重复物品返回的碎片绝对数量更多。需要通过调整各奖池的 $c_i \cdot R(t)$，使各奖池的每抽价值归一化，后续就化为多个小奖池取最大值的已知问题了。即：

• 设总抽取次数为 $N$，则对于每个小奖池会分得 $k_i = N \cdot p_i$ 次。
• 各小奖池 $i$ 各抽取 $k_i$ 次，得到 $t_i$ 个奖品，满足 $n_i \cdot H_{t_i} \leq k_i$，虽然计算期望可以取等号，但调和级数无法依此简化计算。
• 此时产生的碎片为 $r\cdot(k_i-t_i)$ 即 $R(t_i)$，剩余未抽取的奖品数量为 $n_i - t_i$。
• 当总碎片数量大于等于剩余奖品所须数量时，N 得解。整理得到：

\begin{array}{l}
{\left\{
\begin{aligned}
& k_i =N \times p_i, \\
&n_i \cdot H_{t_i} \leq k_i, \\
&\sum_{i=1}^m [R(t_i) \cdot c_i] \geq \sum_{i=1}^m [(n_i-t_i)\cdot c_i] \\
\end{aligned}
\right. } \\
\\
\Rightarrow \large{ N = Max\left( k_i / p_i \right) }
\end{array}

• $c_i$ 为不同奖池间的价值权重，与碎片兑换各级别奖品的相对数量有关，与 $r$ 无关。
• $p_i c_i$ 为定义数据，调和级数只有离散解，每个小奖池计算的全局期望 $N_i$ 仍可能不一致。

6. 概率提升

在某些游戏中，当抽取未能获得奖励时，会提升下一次抽取的概率，直到抽取到奖励后重置概率。则真实概率是多少？

先从一个简单例子入手：

• 事件 A 的发生概率是 1/2，事件 B 发生概率为另 1/2，当 A 未发生时，下一次发生事件 A 的概率提到 100%。那么在多次重复中，A 事件的真实概率是多少？

直觉可能会认为是 75%。但进一步思考发现，事件 B 的下一轮必定跟随事件 A，而事件 A 的下一轮 A 与 B 各有 50% 几率发生。将多轮过程展开后会发现这是 $A:BA=1:1$ 的序列。因此单看事件 A 发生的真实概率为 2/3。

推广到 A 事件 1/3 的情况，可以得到：

在足够长的序列中，三者以 $A:BA:BBA=\frac{1}{3}:\frac{4}{9}: \frac{2}{9}$ 的比例出现，序列总长度为 $L = \frac{1}{3}\cdot n + \frac{4}{9}\cdot 2n+ \frac{2}{9}\cdot 3n$，其中 A 在每个组合中都出现一次，因此 A 的真实概率是 $\frac{n}{L} = \frac{9}{17}$。

由此观察到一般规律，对于初始概率为 $a$，提升步长为 $p$，达到 100% 时的步数为 $k$，即 $a+kp\geq 1 \Rightarrow k\geq(1-a)/p$ 时，真实概率 $P(A)$ 是以下式子的解：

\begin{align*}
L &= p(A)+2\cdot p(BA)+3\cdot p(BBA)+ \cdots + k \cdot p(\underbrace{BBB \ldots B}_{k-1}A) + (k+1) \cdot p(\underbrace{BBB \ldots B}_{k}A) \\
&= a + 2(1-a)(a+p) + 3(1-a)^2(a+2p) + \cdots + k(1-a)^{k-1}(a+(k-1)p) +(k+1)(1-a)^k\cdot1 \\
&= \sum_{i=1}^k \left[i\cdot(1-a)^{i-1}(a+(i-1)\cdot p) \right] + (k+1)(1-a)^k \cdot 1 \\
P(A) &= k/L
\end{align*}

因为 $k$ 是有限的，所以式子不涉及无穷级数，但是计算仍然不方便，需要借助工具。

在 $a = p = 1/n$ 的特殊情况下，可以进一步简化为：

\begin{align*}
L &= \frac{1}{n} + \frac{n-1}{n}\cdot\frac{2}{n}\cdot2 + \frac{n-1}{n}\cdot\frac{n-2}{n}\cdot\frac{3}{n}\cdot3 + \cdots + \frac{n-1}{n}\cdot\frac{n-2}{n}\cdots\frac{1}{n}\cdot\frac{n}{n}\cdot n \\
& = \sum_{i=1}^n \left[\frac{i^2}{n^i} \cdot \prod_{j=1}^{i-1} (n-j) \right] \\
Q(n) &= 1/L \\
\end{align*}

手动计算几个较小值：
\begin{align*}
Q(2) &= \frac{1}{ \frac{1}{2} + \frac{2^2}{2^2}(2-1) } = \frac{2}{3} \\
Q(3) &= \frac{1}{ \frac{1}{3} + \frac{2^2}{3^2}(3-1) + \frac{3^2}{3^3}(3-1)(3-2) } = \frac{9}{17} \approx 0.5294 \\
Q(4) &= \frac{1}{ \frac{1}{4} + \frac{2^2}{4^2}(4-1) + \frac{3^2}{4^3}(4-1)(4-2) + \frac{4^2}{4^4}(4-1)(4-2)(4-3) } = 32/71\approx 0.4507 \\
Q(5) &= \frac{1}{ \frac{1}{5} + \frac{2^2}{5^2}\cdot4 + \frac{3^2}{5^3}\cdot4\cdot3 + \frac{4^2}{5^4}\cdot4\cdot3\cdot2 + \frac{5^2}{5^5}\cdot4\cdot3\cdot2\cdot1 } = 625/1569\approx 0.3983 \\
Q(6) &= \frac{1}{ \frac{1}{6} + \frac{2^2}{6^2}\cdot5 + \frac{3^2}{6^3}\cdot5\cdot4 + \frac{4^2}{6^4}\cdot5\cdot4\cdot3 + \frac{5^2}{6^5}\cdot5\cdot4\cdot3\cdot2 + \frac{6^2}{6^6}\cdot5\cdot4\cdot3\cdot2\cdot1 } = 324/899 \approx 0.3604 \\
Q(7) &= 117649/355081 \approx 0.3313, \\
Q(8) &= 131072/425331 \approx 0.3082, \\
Q(9) &= 4782969/16541017 \approx 0.2892, \\
Q(10)&= 1562500/5719087 \approx 0.2732,
\end{align*}

来个大的：

\begin{align*}
Q(100)&=\frac{\tiny{10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}}{\tiny{129277986730885202106151856642773382549665465071825090615034369359178917814747670780594211447306244001059786961886915926297133393516168977984471526892507817}} \\
&\approx 0.0819
\end{align*}

再来个图：

7. 保底

在某些游戏中，抽取到一定次数后，会有保底机制，即抽取次数超过一定值后，会直接给予某个奖励。

如果只是每 n 次固定给予一个奖励，就是简单的在原期望上加 1/n：$Exp_{(e)} = Exp + 1/n$。

但实际上，在引入保底机制的情况下，讨论概率和期望并没有意义，它已经被『规则』所取代了。当游戏运营方明确表示为概率添加规则时，这个抽奖系统本身就变得不可信了。带保底的抽奖系统一定会和你帐号中的某些变量挂钩，你的抽取与获奖可能性就并非是由某个全系统一致的随机发生器决定，而更可能是与你的帐号历史、充值、活跃度等相关。这个系统运行的不再是概率，而是对你容忍底线的反复试探。

PT 站大多使用了 nexusPHP 的方案，因此其 Seeding Bonus，通常称为魔力点数，基本也使用了相同的公式进行计算：

\begin{align*}
&A = \sum_i\left( 1-10^{ -\frac{T_i}{T_0} } \right) \cdot S_i \cdot \left( 1+\sqrt2 \cdot 10^{ -\frac{N_i-1}{N_0-1} } \right) \\
&B = B_0 \cdot \frac{2}{\pi}arctan\left( \frac{A}{L} \right) \\
\end{align*}

其中：

• 积分每小时计算并发放一次，后文不再赘述。
• $S_i$ 为第 i 个种子的大小，单位是GB
• $T_i$ 为第 i 个种子发布起到现在经过的时间，单位为周，$T_0$ 为参数，$T_0 = 4$
• $N_i$ 为第 i 个种子当前的做种人数，$N_0$ 为参数，$N_0 = 7$
• $L$ 为参数，$L = 300$，$B_0$ 为参数，$B_0 = 50$，不同站点有时会在 $B_0$ 和 $L$ 上有所调整。
• $B$ 为每小时用户获得的点数，由于 $arctan$ 函数值有上限，因此 $B$ 恒小于 $B_0$

可以看到，对于 A，实质上是对每个种子的体积进行了加权求和，两个系数分别与时间和做种人数有关，实质上还是某种『有效做种体积』。因此先分析第二段公式，使用 Geogebra 绘制函数 $\frac{2}{\pi} \cdot arctan\left( \frac{A}{L} \right)$ 图像并取若干个样点：

函数图像是个有上限、增幅递减的增函数，在有效做种体积为 200GB 时，可以得到 $0.37B_0$ 的魔力值，在 1000GB 时为 $0.81B_0$。以下列举一些计算结果：

如果要达到特定的目标上限比，几个档位如下：

200 GB 以下大致可视为线性增长，2 TB 时可以达到 90% 上限分数，更高的分值需要极大的硬盘空间，逐渐不甚合理了。$L$ 参数的变化会等比例地影响上表中的加权体积数值。

下面来研究两个系数的影响，这两个系数实现了『实际做种体积』$\rightarrow$『有效做种体积』之间的换算。首先是时间系数，$f(T_i) = \left(1-10^{ -\frac{T_i}{T_0}}\right)$，由于 nexusPHP 本身对该分值是基于小数的，且『周』的展示不甚直观，这里直接改用『天』作为单位，换算 $T_0 = 28$，其图像为：

显然这也是和 arctan 一样的有上限、增幅递减的增函数，但增幅比 arctan 要大得多，靠近上限十分容易，也就是说到达 0.999 或更高值是个可行的目标。以下列举一些计算结果：

因为是 10 的幂运算，计算分段明显。每 28 天小数点后多一位 9，在寻找 free 种子攒积分时，选时间大于三个月 (>0.999) 的就行，『实际做种体积』与『有效做种体积』几乎一致。

最后是做种人数系数，$f(N_i) = \left(1+\sqrt2 \cdot 10^{ -\frac{N_i-1}{N_0-1}}\right)$，在其定义域内这是个有上下限的减函数，其图像为：

与前两个系数不同，$N_i$ 做种人数只能取正整数，因此其图像是离散的。以下列举一些计算结果：

可以看到，只有 8 人以下的种子才有可能达到 >1.1 的系数，而 20 人以上的种子，该系数的增益已经完全可以忽略了。由于做种人数是不可控的，因此可以简单划为两类，20 人以下有加成， 20 人以上无。又因为人数会变动，因此若要从这个系数上获得稳定收益，必须考虑 $N_i<8$ 的种子，以容许一些浮动范围。

通过以上两个系数的分析，可以得到一个结论，我称为『三八原则』：

三八原则：在 PT 站做种赚取积分时，选择时间大于三个月，做种人数小于 8 人的种子。

原则展开如下：

• 做种人数足够少，可以使实际 1GB 的硬盘空间达成 2.4GB 的做种效果，但条件苛刻。
• 但再多的做种人数也不过是系数为 1，没有奖励，但不会有折损。
• 三个月以前的种子，做种效果几乎 1:1 且容易达成。而一个月以内则折损可观，不是没得选尽量避免保新种。
• 积分有上限，有效做种体积 1-2 TB 已经可以达到 80%-90% 的上限了。再增长 10% 到 99% 则需要近 20TB 有效保种，即使都是长寿孤种也需要 8TB，意义不大。
• 形势所迫必须新种，则放置一周有 44% 的有效做种体积，准备 4TB 硬盘也就够了。
• 孤种才有奖励，新种只有折损。

这样可以最大化体积系数，从而用相同的硬盘空间获取更大的做种收益。当然，既然是赚取积分，肯定是要选择 free 种子。种子时间可以挑选，但做种人数加成八成是不必指望了。

其它一些 Bonus：

各站点会根据自己的实际调整参数，或添加其它的奖励机制，例如：

1. 每个种子 0.7 基本分，最多 14 个。

   该数值上限 9.8，是直接作为基础值的，因此该站的积分上限为 $9.8+B_0$。这个条件几乎不存在代价，保种 1-2 TB 通常来说都会超过 14 个种子。

2. 用户等级奖励，每升一级 1% 的比例奖励。

   这个奖励是在基础值之外的奖励，计算公式为 $(1+1\%\times Level) * (9.8+B_0)$

   用户等级奖励其实存在很大的隐性的代价。PT 站往往要求上传量远大于下载量才能升级，而 1% 的奖励却聊胜于无。这就像在银行存一百万拿 2% 的利息，银行要求你再存一千万升 VIP，而 VIP 的待遇仅仅是利息多 1%，并不是 $2\%\rightarrow 3\%$ 的 1%，而是 $2\%\rightarrow 2.02\%$ 的 1%。如果上传本有余裕，自然升级也就罢了，刻意去为 1% 奖励而花大力气冲没什么意义。

3. 为官方种子做种的额外奖励，上限为 25%。

   百分比类型奖励都是平行的，也就是 $(1+1\%\times Level + 25\%) * (9.8+B_0)$。
   注：该站点程序有 bug，多个官种奖励叠加反而会导致总 bonus 下降，因此只保一个 +25% 官种即可。

4. 每 100 个种子做种 24 小时以上开始 5% 的比例奖励，无上限，每个种子需要大于 5MB。

   $$(1+1\%\times Level + 25\% + \mathop{SeedsQuantity}\limits_{\substack{seedsize>5\text{MB} \\ seedinghour>24}} / 100 \times 5\%) * (9.8+B_0)$$

   该规则鼓励大量小体积种子做种，理论上来说，以 2TB 的目标计算，若全部靠 5MB 的种子达成，至多可以使用 40 万个种子，单这项 bonus 就能达到 $200B_0$，这是一个巨大的增益。客观上受限于种子总量有限及大小各异，不可能达到这个数量，但成为一个万种大佬还是有可能的。此时的 bonus 为 $$(1+25\%+\frac{10000}{100}*5\%) \times (9.8+0.9\times B_0) = 6.25 \times (9.8+0.9\times B_0)$$ 若 $B_0=50$，则值为 $342.5$。在该规则下，保种策略是尽量地将大种子更替为小种子，在总量有限而不变的情况下，提升种子数量。

   但是我们需要进一步讨论。在没有 free 种子的前提下，更替小种虽有额外收益但也会产生额外的下载流量，需要靠魔力值兑换上传量来冲抵。一个种子的小时增益为 $5\% / 100 \times (9.8 + 0.9B_0) = 0.0274$，每天可以通过魔力值兑换的上传流量为 $0.0274 \times 24 \; / \; 425 \times 1024 = 1.5844$ MB，一个 5MB 的种子在 3.15 天回本，因为是独立计算，一百个 5MB 的种子也是 3.15 天回本。回本时间不受种子数量的影响，但与种子体积成正比，当种子体积到 50MB 时回本时间就超过一个月了。

   另一需要考虑的软性限制是 PT 与站点服务器的通讯。当做种数量足够多时，PT 客户端的 tracker update 操作变得十分频繁，甚至变相成为一种对服务器的 DOS 攻击。这也是热门大站往往 tracker update interval 很长的原因。大量种子对保种用户本身也是存在风险的，对同一地址的短时间频繁请求，在客户端到服务器的整条网络传输路径上的任何一个环节都有可能触发限制。服务器收不到 update 信息，用户就反而无法获得积分。

5. 使用 $250\times B_0$ 的价格购买 5% 比例的奖励徽章，可购买多个。

   同样是某种需要考虑投入产出的增益。该站点没有其它基础值奖励，以每小时 $0.9B_0$ 计算，购买后的增益为 $0.045B_0$，回本时间为 $250B_0 /0.045B_0 / 24 = 231.49$ 天。该站 50G 上传量为 $50B_0$，一个徽章相当于 250 GB 的上传量。从无穷长远来看，一切本金不会湮灭且无通胀环境下的投入都是值得的，算来第 232 天开始可就是净收益了。但是在合理的生命周期内，这个投入产出比是十分低的。因此这个徽章是一个『炫耀』的物品，而不是一个『赚钱』的物品。

   PT 站的生命周期是客观存在的，对于用户方，如果生活中发生了某些变化，帐号有时就冷落消失了。对于站点方，也有可能因为各种原因关闭跑路。

   相聚离开都有时候，没有什么会永垂不朽。

6. 后宫加成，每个下线 5%。

   这个奖励的 ROI 计算更为复杂，暂不清楚是否有复利加成，即我后宫的后宫是不是我的后宫。单从实践经验来看，$50B_0$ 兑换邀请和赠与新人 $62.5B_0$ 启动资金，换得的是下线的 5% 增益。如果下线足够给力，则可以得到和徽章奖励一致的 $0.045B_0$。回本周期为 105 天。考虑到下线需要积累一段时间才能达到 $0.9B_0$，实际周期在 150 天左右。比起奖章仍合算一些。如果不提供启动资金，回本周期为 47 天，但新人启动时间会长不少，相当于额外再增加一个 0-50G 的启动时间。

   如果考虑风险因素，ROI 就不好说了。下线的行为是不可控的，且会影响到自己的账号。$112.5B_0$ 的本金浪费是一方面，其它权利影响是则另一方面。除非有站点相关数据作为支撑，否则这些风险很难量化。

7. 从奖池中抽道具，部分道具增加 10% 基础魔力值奖励，每次抽取动作消耗 $2.5B_0$。

   从 n 个道具中抽取特定的 k 个道具，假设无重复时，全部抽齐的期望次数为 $\frac{k(n+1)}{k+1}$，则成本为 $\frac{k(n+1)}{k+1} \times 2.5B_0$，收益为 $k \times 10\% \times 0.9B_0$，回本周期为 $1.1574 \cdot \frac{n+1}{k+1}$ 天，取决于奖池 n 和 k 的比例。事实上哪怕是 1/100 的比例，也比上一条后宫加成更合算。

   进一步考虑，第一个道具在抽出后开始生效，其成本为 $\frac{n+1}{k+1}\times 2.5B_0$，收益为 $10\% \times 0.9B_0$，回本周期同样为 $1.1574 \cdot \frac{n+1}{k+1}$ 天。也就是说，在整个过程中，每个道具的奖励比例一致，则回本周期也都是一致的。

   当有重复时，情况则有不同，第一个的期望成本为 $n/k\times 2.5B_0$，回本周期为 $1.1574 n/k$ 天。所有奖品抽到的期望次数为 $n\cdot H_k$，其中 $H_k=\sum_{i=1}^n\frac{1}{i}$ 为调和级数。越往后面，即使奖励相同，但抽取成本变大也会导致回本周期变长。最后一个的成本是 $n\times 2.5B_0$，回本周期对应为 $1.1574 n$ 天。

   如果除 k 外的其它道具也有一定的奖励，或者总数 n 难以计算，则 ROI 的计算只能通过少量抽样下的贝叶斯推断来进行了。

8. 上传流量的奖励，每 1GB 上传流量奖励 0.1 魔力值。

   PT 站本身上传量就是货币，这个其实属于某种重复奖励，且没有可优化或者可选择的余地。不讨论。

末尾一些啰嗦：

$f(A) = B_0 \cdot \frac{2}{\pi} \cdot arctan\left( \frac{A}{L} \right)$ 的导数为 $f^{'}(A) = \frac{2B_0}{\pi L} \cdot \frac{1}{1+\left( \frac{A}{L} \right)^2}$，为 $\frac{1}{1+x^2}$ 的缩放。当前每增加 1GB 的有效做种体积对应多少魔力值增量，可以通过导数来计算。

通过计算 $Total\_Bonus = N_i \cdot \left(\sqrt2 \cdot 10^{ -\frac{N_i-1}{N_0-1}}\right)$ 发现，在 3 人及以下做种时，PT 站额外奖励了更多的体积系数分到所有的人，而人数更多时 Bonus 总增益开始下降，奖励总量反而逐渐减少。算法并非是将固定的 Bonus 分发给所有人，而确实是针对孤种的单独加成：

不同等级的歌曲在获得对应评价时获得的经验值：

• 同评价下不同等级的歌曲获得的经验值为等差增长数列；
• 同等级下不同评价的歌曲获得的经验值为交替增长数列；
• 各等级歌曲 Exc 的经验总是 E 的两倍，细分的小数点等级以取整计。

玩家各等级升级经验：

• 两等级间的经验差额 D_n=Exp_n+1-Exp_n 在 n≥2 时符合间隔为 7,7,6,7,7,6,7,6,7,6 的递增序列。
• 即 Exp_n+10-Exp_n=830+66n, n≥2。E₂~E₁₁ 为基准值。
• 可以进一步推测，Exp₁ 原本应为 53，但为了确保任何一个新玩家哪怕是最初级的玩家也能立刻体验到升级效果，单独修正为 44。

玩家等级与体力值：

スタミナ = プレーヤーレベル + 49，即 Stamina 体力 = Player Level 玩家等级 + 49，初始 1 级 50 点体力。

• 1-3 级歌曲，每次游玩消耗 20 点体力

• 4-6 级歌曲，每次游玩消耗 25 点体力

• 7-10 级歌曲，每次游玩消耗 30 点体力

• 每 3 分钟恢复 1 点体力，直到达到体力上限；

• 当用户升级时，会恢复体力上限等额的体力，此时可用体力会超过上限；

• 当前体力不足以游玩指定歌曲时，系统会提示用户观看广告获得 50 点体力，当上限小于 79 时，可用体力可能会超过上限；

• 观看广告获得 50 体力，这一行为本身有 1 小时的 CD，不影响其它情况下观看广告获得加成。

• 使用 1 个可乐道具，或 50 个 jBlock 道具可以换取 50 点体力，无 CD，道具通过各类任务获得，也可以直接付费购买；

• 使用 jBlock 在 plus 模式下购买的曲包可以无限次游玩，不消耗体力，但也不会获得经验值；

• 使用 Skip 券可以跳过指定谱面的实际游玩过程，直接按该谱面的历史最高分结算奖励，也会消耗体力。该谱面必须之前有过演奏记录。节约时间用。

尽快升级

• 由于体力上限与等级成正比，因此在游戏初期，尽快升级是提高游戏体验的要素之一。
• 由于歌曲难度等级对应体力消耗不同，且歌曲难度对 Rating 有影响，因此同体力最多 Exp 的升级路线要根据个人能力调整。
• 例如，都为 E 级，Lv.6 的 84/25 = 3.36 就大于 Lv.8 的 100/30 = 3.33。
• 如果所有歌都能打相同 Rating，优势顺序为 10 9 6 8 7 5 3 4 2 1。如果不是，就需要按下表排列：

这里有个重要的点位是 10E(3.87)。E 是最低评价，摆烂也能拿。也就是说，对于效率升级的目标，即以相同体力获得最多经验经验值来说，即使你 1 级歌能打 SS，都不如开 10 级歌放那里不动等 0 分结算快。

コイン (Coin)

• 1-3 级歌曲，每次游玩后奖励 3 个宝箱
• 4-6 级歌曲，每次游玩后奖励 4 个宝箱，其中 1 个为劣质宝箱
• 7-10 级歌曲，每次游玩后奖励 5 个宝箱，其中 2 个为劣质宝箱
• 宝箱可能开出 20, 30, 50, 100, 200, 1000, 10000 等数额的金币。
• 根据 Rating 不同，宝箱开出的金币数目不同，且有一定的随机性。
• 在 Rating = E 的情况下，宝箱开出的金币绝大部分为 20, 30 两种。
• 完成任务和日常签到也会获得金币、jBlock 和道具奖励，数额不等。

Hexo Next 开启 Mathjax

Hexo Next 主题默认支持 Mathjax 和 katex，以在博客文章中显示数学公式。其中，Mathjax 默认以『按需加载』的方式开着，只需要在 md 文件的头部区域添加 mathjax: true 即可激活该文的 Mathjax 支持。

1
2
3
4
5

---
layout: post
title: 'Latex 简单语法总结'
mathjax: true  # 开启 Mathjax
---

也可以在 _config.next.yml 配置文件中设置 math: ↴ every_page: true 为所有文章开启数学公式支持。

Latex 语法

Mathjax 不只支持 Latex，还支持 MathML 等语法。本着快速入门的实用主义角度，本文只记录一部分 Latex 语法。

Latex 的基本语法包括：

• 开头结尾与键盘字符。
• 格式控制，包括公式组合、上下标、分数、根式、矩阵等 。
• 转义字符，包括希腊字符、数学符号、运算符、箭头、修饰符等。
• 打印控制，包括字体、颜色、大小、对齐等。
• 宏定义与扩展包，包括自定义命令、环境等。

开头结尾与键盘字符

用 $ ... $ 包裹的内容会被 Mathjax 重新改写为 行内公式，比如 \$F=ma\$ 就会被自动渲染为 $F=ma$，行内公式后续文字会在同一行继续。用 $$ ... $$ 包裹的内容称为 行间公式 或者 块内公式，公式在文章中是独立的块，\$\$E=mc^2\$\$ 会被渲染为 $$E=mc^2$$ 文字将被断开换行并形成上下围绕。

对于英文字母以及一些键盘上的符号，Mathjax 也会适当地重新渲染，$+ - * / = > < ( ) [ ]$ 等均会被渲染为数学符号。因此像 F=ma 这样的公式，直接前后套上 $，变为 \$F=ma\$ 就是 Latex 表达式了。

格式控制：初步

从上面我们还注意到，c^2 经过 Mathjax 渲染后变成了 $c^2$。没错，^ 就是上标控制符，将紧随其后的字符变为上标。同理，_ 就是下标控制符。\$C_4^1 * C^2_4\$ 将渲染为 $C_4^1 * C^2_4$。上下标没有先后顺序，都会附着到前一个全高字符上。

当表达『24选4』时，\$C_24^4\$ 却被渲染为了 $C_24^4$。规则是严格执行的，但结果却不是我们想要的。这时候需要用到花括号 {} 来控制上下标的范围，用 \$C_{24}^4\$ 就能正确渲染为 $C_{24}^4$ 了。

{} 『分组符』不光能用于上下标，其用途如名字所言，是将若干 latex 表达式定义为一个组，以一个整体与表达式中其它部分作用。比如 \$1^{3^{5^{7^9}}}\$ $\Rightarrow$ $1^{3^{5^{7^9}}}$，就是先将 7^9 视为整体，作为 5 的上标，再以三者的组合作为整体，作为 3 的上标，以此类推直到完成这个叠幂公式。你甚至可以反过来，比如 \${{{1^3}^5}^7}^9\$ $\Rightarrow$ ${{{1^3}^5}^7}^9$。分组符的灵活应用是大型公式的基础之一。

注意看两种不同的叠幂公式的渲染效果，有什么不同？为什么？

$C_{24}^4$ 可以展开为 $(24 \cdot 23 \cdot 22 \cdot 21)/(1 \cdot 2 \cdot 3 \cdot 4)$。即通项公式 $C_n^k = \frac{1 \times 2 \times \dots \times k}{n (n-1) (n-2) (n-k+1)}$，其 Latex 表达式为 \$ C_n^k = \frac{1 \times 2 \times \dots \times k}{n (n-1) (n-2) (n-k+1)} \$。

从这里我们开始入门大型公式。上述分数的表达式是 $\frac{分子}{分母}$，在 \frac 后面，分子和分母的位置是固定的，分子在前，分母在后，与上下标有所不同。大括号 {} 则继续发挥分组的作用。在分子分母两组内部，我们又用了 \times 作为乘号，\dots 作为三点省略号。Mathjax 会自动识别空格，因此我们不必担心空格的问题，在源代码上添加空格可以使阅读与编辑更方便，有时也能避免一些 latex 的编译错误。

在初步掌握格式控制后，就可以展开阅读以下表格了：

* 为兼容源代码的可读性，Latex 会忽略普通空格。因此在公式中需要添加额外空格时要用 \quad。后续排版环节会介绍更多距离控制符。
* 在所属代码块内，以最大上下范围为准，自动调整括号大小。

转义字符与修饰符号

在数学中我们会用到很多字符，比如圆周率 π，积分符号 ∫，无穷大 ∞，等等。归功于 unicode 的普及，我们可以直接从输入法的特殊字符输入，或者其它查码表的方式来输入这些字符，Mathjax 也都是支持的。但 Latex 出身甚早，自身也提供了一套转义字符以输入这些特殊字符，显示效果也更好。

希腊字符

标红是因为 Mathjax 认为它是错误代码。标红错误代码有助于作者顺利进行排查，比如 $\fracc{k}{n(n-k)}$ 很容易便能看出来是 \frac 拼写错误。但为何 $\Alpha$ 是错误的呢？原因如下：

[引用] There is no uppercase Alpha, Beta etc. defined in LATEX2ε because it looks the same as a normal roman A, B.

由于历史原因，Latex 以『形状相似』为由，没有定义几个与英文相似的大写希腊字母，包括 Α Β Ε Ζ Τ 等，遇到就报错，建议你用英文字母代替这几个大写希腊字符。所以 Mathjax 也跟着报错了。仔细想来，只是用于公式排版倒也差不多说得过去。只是极端节省到这地步，我的心情如下述评论：

[引用] The fact that they actually bothered to make a capital tau symbol surprises me ...

这种情况下，如果有必要输入正确的大写希腊字符，例如某些可能会被复制的场合。可以直接用输入法的特殊字符输入，或者用 Latex 后续版本扩展出来的 \unicode{} 方法，例如 \$\unicode{x0391} \neq \text{A}\$ $\Rightarrow$ $\unicode{x0391}\neq \text{A}$。

数学符号

Latex 定义了大量的符号，下表只列出了一小部分。大部分符号用不到就是不需要，知识领域没覆盖那部分。这里 有一份号称完整的符号表，不过比起查书，问问 ChatGPT 也许更直接。

特殊转义符

我们使用 $ ... $ 和 $$ ... $$ 来包裹 Latex 表达式，用 {} 来分组包裹，用 ^_ 作为上下标。那么当我们需要在公式中直接显示这几个字符时，就需要额外添加转义符了。

* verb 是 verbatim 的简写，verbatim text 意为原始文本。\verb 的语法较为特殊，首先以 \verb 开头，然后紧接着一个界定符，这个界定符可以是 ! | # 等各种符号任选，只需要与正文不冲突即可，再继续输入正文，最后再以相同的界定符结尾。两个界定符之间的内容将被原样输出，不会被 Mathjax 渲染。界定符甚至可以是数字，比如 \$\verb03^30\$ 将输出 $\verb03^30$，前后两个 0 成为了首尾界定符，但唯独不能是字母，因为会和 verb 本身形成新的单词短语导致解析错误，\$\verba3^3a\$ $\Rightarrow$ $\verba3^3a$。

修饰符号

修饰符号的使用类似于函数，用 {} 将修饰对象包裹起来，修饰符号的位置总是相对于修饰对象进行调整，而与修饰对象在整个公式中的位置无关。

从大型运算符到修饰命令

我们在前面已经见到了 \sum \prod \int 等大型运算符，这些符号在公式中往往还配有上下限、积分定义域等算子与脚标。Mathjax 会自动根据行内或块内的场景来调整算子的大小和脚标的相对位置。比如 \$\sum_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6\$ 将渲染为 $\sum_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6$，而相同的公式在块内渲染为：

$$\sum_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6$$

可以看到，$_{i=1}$ 与 $^n$ 的位置随着不同的条件自动调整了。这种自动调整的机制在大型公式中非常有用，我们只需要关心公式的结构即可。但如果一定要坚持特定的格式，也可以用 \limits 和 \nolimits 来强制调整上下限的位置。比如 \$\sum\limits_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6\$ 将渲染为 $\sum\limits_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6$。而\$\$\sum\nolimits_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6\$\$ 将渲染为：

$$\sum\nolimits_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} 6$$

\limits 与 \nolimits 没有自己的符号，但可以修饰很多带脚标的大形运算符，强制调整其形式，且只能用在运算符上。如果你用在别处，Mathjax 会报错。比如： \$C\limits_4^2\$ $\Rightarrow$ $C\limits_4^2$，报错了。我们期望的是 4 出现在 C 的下方，正确的实现方式是用下面的 \underset 命令：

多行公式组：矩阵，表格及其它

equation 与 cases

经过前面的铺垫，我们可以开始对公式进行组合了。公式组的基本形式是：

1
2
3
4
5
6

\begin{equation}
    \begin{cases}
        x + y = 35 \\
        2x + 4y = 94
    \end{cases}
\end{equation}

效果如下：
\begin{equation}
\begin{cases}
x + y = 35 \\
2x + 4y = 94
\end{cases}
\end{equation}

• 多行公式组不需要以 $ ... $ 包裹，但需要以 \begin{env} \end{env} 单独的首尾声明作为公式起止。env 则是由 latex 预先定义的一些环境，比如上面的 equation 就是一个环境。
• equation 环境的作用是将包裹的所有内容视作一个公式全局自动编号，编号的位置在公式组的最右侧。而 cases 环境的作用是为包裹的所有内容添加左大括号，形成一个公式组。
• 公式组内部仍可以用其它的公式控制符，比如 \frac \sum \int 等。
• 公式组内部通常都有多行，需要用 \\ 来换行。Latex 源码的回车换行和空格一样会在渲染时忽略，多行 latext 公式组在源码上仍然可以只写成一行，\\begin{equation}\\begin{cases}x+y=35\\\\2x+4y=94\end{cases}\end{equation} 的效果是一样的，但合理书写可以让源码可读性及可编辑性更高。
• \begin{env} \end{env} 是可以嵌套的，在上面的例子中，我们用了两个环境，在 equation 环境内部嵌套了 cases 环境，效果是将鸡兔同笼的两个二元一次方程合并成组，并做了全局编号。

align 与 align*

align 的作用是将每一个包裹的公式对齐，比较适合于表现演算过程。要注意的是，align 并不会自动以 $=$ 对齐，而是要用 & 指定竖向对齐位置。比如：

1
2
3
4
5
6

\begin{align}
    f(x) &= x^4 + 4 \\
         &= x^4 + 4x^2 + 4 - 4x^2 \\
         &= (x^2 + 2)^2 - (2x)^2 \\
         &= (x^2 + 2x + 2)(x^2 - 2x + 2)
\end{align}

得到：
\begin{align}
f(x) &= x^4 + 4 \\
&= x^4 + 4x^2 + 4 - 4x^2 \\
&= (x^2 + 2)^2 - (2x)^2 \\
&= (x^2 + 2x + 2)(x^2 - 2x + 2)
\end{align}

可以看到，每个公式后面都加上了全局编号，如果不想要的话，可以用 align* 来代替 align，效果如下：

\begin{align*}
f(x) &= x^4 + 4 \\
&= x^4 + 4x^2 + 4 - 4x^2 \\
&= (x^2 + 2)^2 - (2x)^2 \\
&= (x^2 + 2x + 2)(x^2 - 2x + 2)
\end{align*}

同样的情况也适用于 equation，即无编号公式 equation*，不再演示。

matrix 矩阵与省略号

matrix 环境用于矩阵排版，例如：

1
2
3
4
5

\begin{matrix}
    a_1 & b_1 & c_1 \\
    a_2 & b_2 & c_2 \\
    a_3 & b_3 & c_3
\end{matrix}

\begin{matrix}
a_1 & b_1 & c_1 \\
a_2 & b_2 & c_2 \\
a_3 & b_3 & c_3
\end{matrix}
同样是用 & 来进行上下对齐。上述渲染结果相比于常见的矩阵缺少了左右 $[ ]$，可以使用上文的 \left[ \right] 命令来添加：

1
2
3
4
5
6
7

$$\left[    
\begin{matrix}
    a_1 & b_1 & c_1 \\
    a_2 & b_2 & c_2 \\
    a_3 & b_3 & c_3
\end{matrix}
\right]$$  % 当内容放在 \begin \end 之外时，需要用 $ 或 $$ 包裹

$$\left[
\begin{matrix}
a_1 & b_1 & c_1 \\
a_2 & b_2 & c_2 \\
a_3 & b_3 & c_3
\end{matrix}
\right]$$

也可以用 pmatrix bmatrix Bmatrix vmatrix Vmatrix 等环境来代替 matrix，效果如下：
$$ \text{pmatrix:}\begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \end{pmatrix}, \text{bmatrix:}\begin{bmatrix} a_1 & b_1 \\ a_2 & b_2 \end{bmatrix}, \text{Bmatrix:}\begin{Bmatrix} a_1 & b_1 \\ a_2 & b_2 \end{Bmatrix},\text{vmatrix:}\begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix}, \text{Vmatrix:}\begin{Vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{Vmatrix}$$

另外还有一个 smallmatrix 环境，用于在行内排版小矩阵，如下： \$\left(\\begin{smallmatrix}a_1&b_1\\\\a_2&b_2\end{smallmatrix}\right)\$ $\Rightarrow$ $\left(\begin{smallmatrix} a_1 & b_1 \\ a_2 & b_2 \end{smallmatrix}\right)$，但它没有 \smallBmatrix 等变化形式，需要括号时用普通的即可。

当矩阵很大时，会使用省略号来代替部分内容：

1
2
3
4
5
6

\begin{pmatrix}
    a_{11} & a_{12} & \cdots & a_{1n} \\
    a_{21} & a_{22} & \cdots & a_{2n} \\
    \vdots & \vdots & \ddots & \vdots \\
    a_{m1} & a_{m2} & \cdots & a_{mn}
\end{pmatrix}

\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{pmatrix}

我们上文用过 \dots，此处又使用了 \cdots \vdots \ddots 等命令来输出省略号，可以认为前缀字母 c = center，v = vertical，d = diagonal，分别表示水平、垂直、对角线方向。另外还有 \ldots，l = lower 表示靠近底线的省略号。因此也可以把前缀字母理解为类似于 \limits 的某种修饰符。

array

array 可以起到与 matrix 一致的效果，但可以容纳更多的修饰或控制符使得表现效果更丰富，当然也意味着更多的 latex 代码量和复杂度。因为可以添加横竖线作为表格边框，array 一般用来表现表格：

1
2
3
4
5
6
7

\begin{array}{c|lcr} 
    n & 左对齐 & 居中对齐                         & 右对齐 \\
    \hline    % 横线不占用行高，不必添加 \\ 换行
    1 & \pi   & rad                              & 355/113 \\
    2 & e     & {\left(1+\frac{1}{n}\right)}^n   & \ln x \\
    3 & i     & \sqrt{-1}                        & sin(\theta)+icos(\theta)
\end{array}

效果：
$$\begin{array}{c|lcr}
n & 左对齐 & 居中对齐 & 右对齐 \\
\hline
1 & \pi & rad & 355/113 \\
2 & e & {\left(1+\frac{1}{n}\right)}^n & \ln x \\
3 & i & \sqrt{-1} & sin(\theta)+icos(\theta)
\end{array}$$

代码首行 \begin{array}{c|lcr} 中的 {c|lcr} 部分是 array 环境的参数，用于指定每一列的对齐方式，c = center，l = left，r = right，| 表示添加竖线作为列分隔符，可以不添加也可以添加多条。在内容部分，用 & 来对齐各列，用 \\ 来换行。用 \hline 添加横线，会自动置入两行之间，不影响文本的行高，也不必添加 \ 换行。

{array}也同样可以配合 \left{ \right} 来构造方程组，一些形式上要求齐次对齐的方程组，使用 array 会比较方便：

1
2
3
4
5
6
7
8

$$\left\\{ 
    \begin{array}{lrrrrr}
        f_1(x) = &      &       &       & x   & +1 \\
        f_2(x) = &      &       & 8x^2  & +5x & +2 \\
        f_3(x) = &      & 3x^3  & +7x^2 & +2x & +9 \\
        f_4(x) = & 9x^4 & +3x^3 &       & +4x & +6
    \end{array} 
\right.$$ % 有 \left\{ 时，必须要有对应的右括号闭合。但可以用 \right. 放一个不显示内容的右括号。

$$\left\{
\begin{array}{lrrrrr}
f_1(x) = & & & & x & +1 \\
f_2(x) = & & & 8x^2 & +5x & +2 \\
f_3(x) = & & 3x^3 & +7x^2 & +2x & +9 \\
f_4(x) = & 9x^4 & +3x^3 & & +4x & +6
\end{array}
\right.$$

公式引用

\tag \label 与 \eqref

公式引用分为被引用，和引用别人的。虽然使用 \begin{equation} 等环境可以自动编号，但却无法直接根据该编号引用对应的公式。在 Latex 中引用公式，必须满足两个条件：

1. 被引用的公式必须是块公式，行内公式不能被引用。
2. 被引用的公式必须显式地声明一个 label，用于引用的锚点，语法为 \label{labelname}。

公式也可以用 \tag{equationname} 来修改默认的全局编号名，但并非必须。

1
2
3
4
5

\begin{equation}
    \label{ef}
    \tag{Euler's Formula}    % 自定义公式名，非必须
    e^{i\pi} + 1 = 0
\end{equation}

\begin{equation}
\label{ef}
\tag{Euler's Formula}
e^{i\pi} + 1 = 0
\end{equation}

在上面的例子中，我们为欧拉公式添加了一个 label ef。如果我们想要引用这个公式，可以使用 \eqref{ef} 命令，引用时则不限于是否是块公式，也不限于是否有 \tag{tagname}，例如：

\$e^{i\theta}\overset{\\eqref{ef}}{=}cos\theta+isin\theta\$ $\Rightarrow$ $e^{i\theta}\overset{\eqref{ef}}{=}cos\theta+isin\theta$。

可以看到，引用的锚点是 \label{labelname} $\Rightarrow$ \\eqref{ labelname}，而在 \eqref 处显示的则是由 \tag{equationname} 设定的公式名称。labelname 可以是几乎任意字符串，在各种教程中经常出现的 \label{eq:1} 主要是为了方便管理，取『equation No.1』之意。上面的 ef 也是 Euler's Formula 的缩写。使用 \label 的好处在于，当我们在后续编辑排版时，即使公式的编号变了，引用的地方也会自动更新，因为引用的锚点是固定的。这也是为什么要分别定义 \label 和 \tag 的原因。

\ref 与 \href

在完整的 latex 中，\ref 与 \eqref 稍有不同，后者是前者子集。但对于 Mathjax 这种限于网页展示的场合，两者并没有什么不同。根据 这里 的说明，\ref 还能引用外链，但我没有尝试成功，可能是 Mathjax 的限制。本来，在 Markdown 博客中引用外链有更简单的方式：[文字](链接地址)，但如果非得拧巴一下，也可以用 \href{链接地址}{文字} 来实现：

$\href{https://www.kaikai.men/mathjax-latex-syntax/}{本文地址}$ $\Rightarrow$ $\href{https://www.kaikai.men/mathjax-latex-syntax/}{本文地址}$

打印控制

Latex 会自动调整公式的大小和排版，但有时候我们也需要适当地调整一下字体字号、空隙间距等，以达到更好的排版效果。这里介绍一些常用的控制命令。

空格间距

行间距

公式组的多行之间通过 \\\\ 分隔，在分隔符后面可以添加下方行距，允许小数点，如下：

1
2
3
4
5

\begin{cases}
    x + y = 35 \\[15pt]
    2x + 4y = 94 \\[1.5em]
    x = 23, y = 12
\end{cases}

\begin{cases}
x + y = 35 \\[15pt]
2x + 4y = 94 \\[1.5em]
x = 23, y = 12
\end{cases}

字形字号

字体颜色

Mathjax 使用 \color{colorname} 命令来设置字体颜色，colorname 可以是预定义的颜色名，也可以是 RGB 值。比如 \$\color{red} E\$ $\Rightarrow$ $\color{red} E$。预定义的颜色名参考 这里，摘抄一部分如下：

$\color{aqua}{aqua}$ $\color{black}{black}$ $\color{blue}{blue}$ $\color{blueviolet}{blueviolet}$ $\color{brown}{brown}$ $\color{burlywood}{burlywood}$ $\color{cadetblue}{cadetblue}$ $\color{chocolate}{chocolate}$ $\color{coral}{coral}$ $\color{cornflowerblue}{cornflowerblue}$ $\color{crimson}{crimson}$ $\color{cyan}{cyan}$ $\color{darkblue}{darkblue}$ $\color{darkcyan}{darkcyan}$ $\color{darkgoldenrod}{darkgoldenrod}$ $\color{darkgray}{darkgray}$ $\color{darkgreen}{darkgreen}$ $\color{darkkhaki}{darkkhaki}$ $\color{deeppink}{deeppink}$ $\color{deepskyblue}{deepskyblue}$ $\color{dimgrey}{dimgrey}$ $\color{firebrick}{firebrick}$ $\color{forestgreen}{forestgreen}$ $\color{fuchsia}{fuchsia}$ $\color{gainsboro}{gainsboro}$ $\color{gold}{gold}$ $\color{goldenrod}{goldenrod}$ $\color{gray}{gray}$ $\color{green}{green}$ $\color{greenyellow}{greenyellow}$ $\color{grey}{grey}$ $\color{hotpink}{hotpink}$ $\color{indianred}{indianred}$ $\color{indigo}{indigo}$ $\color{lightblue}{lightblue}$ $\color{lightcoral}{lightcoral}$ $\color{lightsalmon}{lightsalmon}$ $\color{lightseagreen}{lightseagreen}$ $\color{lightskyblue}{lightskyblue}$ $\color{lime}{lime}$ $\color{limegreen}{limegreen}$ $\color{magenta}{magenta}$ $\color{maroon}{maroon}$ $\color{navy}{navy}$ $\color{olive}{olive}$ $\color{orange}{orange}$ $\color{orangered}{orangered}$ $\color{orchid}{orchid}$ $\color{peru}{peru}$ $\color{pink}{pink}$ $\color{plum}{plum}$ $\color{purple}{purple}$ $\color{red}{red}$ $\color{salmon}{salmon}$ $\color{silver}{silver}$ $\color{teal}{teal}$ $\color{thistle}{thistle}$ $\color{tomato}{tomato}$ $\color{turquoise}{turquoise}$ $\color{violet}{violet}$ $\color{yellow}{yellow}$ $\color{yellowgreen}{yellowgreen}$

如果使用 RGB，格式为 \color{#rrggbb} 或缩写的 \color{#rgb}，其中 rgb 为 0-f 的十六进制数。

这里有一个新的注意点，在下一节中介绍。

宏定义与扩展包

Mathjax 不支持这些。Latex 本身提供了很多扩展功能，但 Mathjax 仅仅是一个 JS 库，它并不是完整的 Latex。如果需要使用这些功能，需要在 Latex 编译器中进行。

在这里记一笔，是因为在搜索某个效果的 Latex 语法时，往往会遇到一些使用扩展功能的回答，Mathjax 其实并不支持，需要注意。

与 Markdown 和 Hexo 的冲突处理

这个博客是 Hexo 搭建，加载了 Hexo Next 主题。使用 Markdown 语法在文本文件中编写博客，由 Hexo 将其编译为 HTML 文件，而 Mathjax 则在 HTML 文件中渲染 Latex 公式。而 Hexo 本身也有自己的模板语法，这使得我们编写的内容，需要经过 Hexo 编译，Markdown 编译，再由 Mathjax 渲染，最后才能在浏览器中显示。这样的多重编译过程，使得我们在写文章时，需要额外考虑一些情况。

Hexo 处理

使用 {% raw %} ... {% endraw %} 避免 Hexo 模板语法带来的问题。所有 {% raw %} ... {% endraw %} 两者之间的内容都不会被 Hexo 进一步解释，而是进入 Markdown 解释器层进行下一步处理。

在使用 \color{#rrggbb} 语法时就会遇到相关问题，{# 会被 Hexo 识别，但又不属于合法的模板语法，导致 Hexo 编译失败报错。相似的情况还出现在 {} 的嵌套场景下，连续的 {{{ 也会被视为错误的 Hexo 模板语法。因此，我们需要用 {% raw %} ... {% endraw %} 来避免这些问题。

Markdown 处理

Markdown 语法中，\ 也是转义字符，用于输出特殊字符，比如 \# $\Rightarrow$ # ,\* $\Rightarrow$ * 等。因为 #、*、_ 等字符在 Markdown 中是有意义的（用于标题、列表、强调等），因此需要用 \ 转义。所以为了在 Markdown 处理完以后还能保留 \，我们在写文章时就需要有意地写成 \\\\。

此外，Markdown 本身也会有意地忽略多余的空格，因此如果需要将多个空格传递给 html，需要使用 &nbsp; 来转义。所幸 &nbsp; 只要隔开连续的空格，每个空格包括 &nbsp; 都会保留，因此可以与空格交替写来省点事。

Mathjax 处理

在经过 Markdown 编译后，原始文章已经变成了 HTML 文件。此时 Mathjax 会搜索全文中的 Latex 相关语法，将其渲染为对应的公式。但是由于 Mathjax 也将 \$ 等符号视作特殊字符，因此仍然会再进行一次转义。比如 HTML 中如果有一个『\\\$』，会被 Mathjax 认为是 \$ 符号的转义符，因此会消除 \\，单显示一个 $ 符号。

与此相似的，还有为了在 Mathjax 渲染后还能正常显示 \\\\ （两个反斜杠），我们在源文件中需要写成惊人的八条反斜杠：\\\\\\\\\\\\\\\\。在 Markdown 编译时，每两条 \\ 会被解释为一条有效的反斜杠，因此在 HTML 文件中会生成连续的四条反斜杠。而 Mathjax 会在 HTML 呈现的内容基础上再作渲染，再一次将每两条反斜杠编译为一条有效的反斜杠，因此最终显示的是两条反斜杠。

如果能及时注意到 Mathjax 是在页面的 HTML 上再次渲染，就能很好地理解这个过程。

其它信息

本文到这里就差不多尾声了。Mathjax 是为网页提供 latex 公式渲染的 JS 库，并不拥有 latex 的全部功能。Latex 有很多全页排版、宏定义与扩展包，包括自定义命令、环境等功能，在 Mathjax 里是没有的。

本文的目的是为了介绍 Mathjax 的基本语法，以及与 Markdown 和 Hexo 的冲突处理。如果需要更多的功能，可以参考下面的参考资料。

Mathjax 的官方文档：https://docs.mathjax.org/en/latest/index.html

Mathjax 的官方示例：https://docs.mathjax.org/en/latest/web/start.html#mathjax-cdn

Latex 编辑器：TEXMaker

MathJax basic tutorial and quick reference

LaTeX Grammar List @rollpie

在博客访问者无法直连 Disqus 时，有个 DisqusJS 的劣化替代方案可供博主使用。方案内置在 Hexo Next 主题中，在正确配置第三方反向代理后，博客可向游客展示评论，但游客无法参与讨论。

这种方案的效果如本文底部评论区所示。该方案需要在三个地方进行配置，分别是 Disqus 服务提供方（需科学上网）、代理端（本文为 Cloudflare 云函数），以及 Hexo Next 配置文件（本地），没有先后顺序。

Disqus

先 注册 Disqus 账号。注册后，点击首页的『GET STARTED』，并选择『I want to install Disqus on my site』选项。

下一页，只有 Shortname 会在后续的配置中用到，其余随便选。
下一页，付费页面下拉选择 Basic 免费计划。
下一页，出现 Installation 界面就可以关闭了，因为 Hexo Next 已经内置，不需要手动安装。左侧菜单其它的审核策略等选项都可以后续有需要再设置。

然后 注册 Disqus API 应用。
第一页，都随便填，Label 填个自己能看懂的名字，方便后续管理。网址格式要正确。填完以后点『Register my application』
下一页，Settings 下的 Domains 填上博客网址，不用加 http/https 协议前缀。Disqus 后续会用来匹配 referer。填完后点『Save Changes』
保存以后切换到『Details』页面，把 Public Key 的一长串字符复制下来，后续会用到。

Cloudflare

假设你已经有了 Cloudflare 账号，并且有一个由 Cloudflare 管理的域名。

登录 Cloudflare 云函数平台，Login。
下一页，点击右上角『Create a Worker』，下一页点击『创建 Worker』，下一页起个名 worker name 后续管理要用，点右下角部署。
下一页，『配置 Worker』。
下一页，右上角『快速编辑』，复制下面代码，粘贴后点右上角『保存并部署』。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

addEventListener('fetch', event => {
  event.respondWith(proxy(event));
});

async function proxy(event) {
  const getReqHeader = (key) => event.request.headers.get(key);

  let url = new URL(event.request.url);
  url.hostname = "disqus.com";

  let parameter = {
    headers: {
      'Host': 'disqus.com',
      'User-Agent': getReqHeader("User-Agent"),
      'Accept': getReqHeader("Accept"),
      'Accept-Language': getReqHeader("Accept-Language"),
      'Accept-Encoding': getReqHeader("Accept-Encoding"),
      'Connection': 'keep-alive',
      'Cache-Control': 'max-age=0'
    }
  };

  if (event.request.headers.has("Referer")) {
    parameter.headers.Referer = getReqHeader("Referer");
  }

  if (event.request.headers.has("Origin")) {
    parameter.headers.Origin = getReqHeader("Origin");
  }

  return fetch(new Request(url, event.request), parameter);
}
// 代码来自 [idawnlight](https://github.com/idawnlight/disqusjs-proxy-cloudflare-workers)

下一页，点击仪表上 『Custom Domains』下面 『0』右边的『查看』，随后点击右上角『添加自定义域』。
建议填入 disqus.<你自己拥有的域名>，点击『保存』。这是 cloudflare worker domain，后续会用到。
如果你没有自定义域名，也可以用默认的。默认的在仪表上『预览』位置处，格式为 <workername>.<你的cloudflare 帐号名>.worker.dev。

点击『添加自定义域』，Cloudflare 的配置完成。需要等几分钟生效。期间可以先配置 Hexo Next。

Hexo Next

编辑 _config.next.yml 文件，找到 comments disqus disqusjs 三个配置项，修改内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

comments:
    style: tabs
    active: disqusjs    # 这里用 disqusjs 代替了 disqus
    storage: true
    lazyload: false
    nav:
        disqusjs:       # 这里用 disqusjs 代替了 disqus
          text: Load DisqusJS
          order: -1
# Disqus
disqus:
    enable: false       # 这里改为 false，关闭原始的 Disqus
    shortname: 
    count: true
# DisqusJS
disqusjs:
    enable: true        # 这里改为 true，启用 DisqusJS
    api:  https://<cloudflare worker domain>/api/   # 这里填 Cloudflare 云函数的域名，注意还要加上 /api/ 后缀
    apikey:  <API key>                              # 这里填 Disqus 提供的 public key
    shortname: <shortname>                          # 这里填 Disqus 注册时的 shortname

验证

本地，或编译后在服务器端打开页面，都可以看到评论区。自行留言后断开科学上网，刷新页面看有没有更新即可。或者用 Cloudflare 的云函数计数是否增加也可以。

在 CPU 提升为 N200 后，Surface Go 4 似乎成为了一款不错的 Galgame 设备。当然现在还有另一个选择 Steamdeck，但是 Steamdeck 也有屏幕、风扇、系统兼容性等方面的劣势。尤其是在屏幕方面，差别非常大。总之先列举一下配置作参考。

Surface 系列

Steamdeck 系列

对比

两者还是有挺大区别的，前几代 Surface Go 的 CPU 性能基本已经脱离主流了，毕竟被动散热，上架就是同时代低端性能，跑 E-mote/Live2D 都存在一定性能问题。手头的 Surface Go 一代跑 Steam 客户端本身都显得很勉强。4 代的 N200 CPU 性能其实也是本代低端，但毕竟刚上市还过得去。

所以针对 Galgame，Surface 的主要且唯一巨大的优势就是屏幕，无风扇算个小优，系统优势不大，Deck 也可以装 Win 切换。

而 Steamdeck 毕竟是游戏机，能跑的都能跑，只是屏幕差距对 Galgame 来说是个硬伤，性能则显得相对冗余。