人民邮电出版社图灵公司的图灵新知丛书是很好的科普读物,其中的《数学万花筒(修订版)》中有一篇:

奇偶赛马

每个整数都可以通过将适当的质数相乘而得到。如果需要偶数个质数相乘,则我们说那个数是偶类型。如果需要奇数个质数相乘,则我们就说那个数是奇类型。例如,
              96 = 2×2×2×2×2×3
用到了六个质数,所以 96 是偶类型。另一方面,
              105 = 3×5×7
用到了三个质数,所以 105 是奇类型。根据约定,1 是偶类型。

对于 1 到 10 的前十个整数,它们的类型分别是:
              奇类型           2   3         5       7   8
              偶类型       1             4       6             9   10
从中我们可以发现一个相当惊人的事实:一般而言,奇类型的出现频率至少与偶类型的相当。不妨设想有“奇”和“偶”两匹马赛跑。让它们一开始时处在同一起跑线上,然后按顺序念出整数:1, 2, 3, ... 在每一步,如果下一个数是奇类型,则奇马前移一格;如果下一个数是偶类型,则偶马前移一格。因此:
              第 1 步后,偶马领先;
              第 2 步后,奇马和偶马并排;
              第 3 步后,奇马领先;
              第 4 步后,奇马和偶马并排;
              第 5 步后,奇马领先;
              第 6 步后,奇马和偶马并排;
              第 7 步后,奇马领先;
              第 8 步后,奇马领先;
              第 9 步后,奇马领先;
              第 10 步后,奇马和偶马并排。
奇马似乎总是能并排或者领先。1919 年,乔治·波利亚猜想,除了在最开始的第 1 步,奇马永远不会落后于偶马。计算表明,前一百万步确实如此。鉴于这沉甸甸的有利证据,可以确定任何数目的步数都会如此吗?

如果不借助计算机,你可能会浪费大量时间在这个问题上,所以我将告诉你答案。波利亚了!1958 年,布赖恩·哈泽尔格罗夫证明了,在某一(未知)步,奇马落后于偶马。随着更快计算机的出现,人们可以验证更大数目。1960 年,罗伯特·莱曼发现,在第 906,180,359 步偶马领先于奇马。1980 年,田中实证明了,偶马在第 906,150,257 步首次领先。

这样的事情使得数学家在没有得到证明之前不敢轻易下结论。它也表明,甚至像 906,150,257 这样的数也可以非常有趣和不同寻常。

我们可以使用以下 C 语言程序来计算偶马在什么时候首次领先:

 1: #include <stdio.h>
 2:
 3: const long n = (long)1e9;
 4: const int n2 = (int)3.17e4; // n2 > sqrt(n + n2)
 5:
 6: void factor(long i0, char a[], const char c[])
 7: {
 8:   static long t[n2];
 9:   for (int i = 0; i < n2; ++i) t[i] = 1, a[i] = 0;
10:   for (int p = 2; (long)p * p < i0 + n2; p++)
11:     if (!c[p])
12:       for (long q = p; q < i0 + n2; q *= p)
13:         for (long i = q - 1 - (i0 - 1) % q; i < n2; i += q)
14:           t[i] *= p, ++a[i];
15:   for (int i = 0; i < n2; ++i) if (i + i0 != t[i]) ++a[i];
16: }
17:
18: int main()
19: {
20:   static char a[n2], c[n2];
21:   for (int i = 2; i * i < n2; ++i)
22:     if (!c[i]) for (int j = i * i; j < n2; j += i) c[j] = 1;
23:   for (long z = -1, i0 = -n2, i = 2; i <= n; ++i) {
24:     if (i >= i0 + n2) factor(i0 = i, a, c);
25:     if (a[i - i0] & 1) ++z; else --z;
26:     if (z < 0) { printf("%ld\n", i); break; }
27:   }
28: }

简要说明:

  • 第 21 至 22 行(使用筛法)标记出所有小于 n2 的合数。
  • 第 6 至 16 行的 factor 函数对 i0 至 i0 + n2 范围内的整数(使用筛法)分解质因数,以得到质因数的个数。
  • 第 23 至 27 行的主循环计算奇马领先偶马的步数 z,当 z 首次小于 0 时就结束程序。

这个程序运行 12 秒后,给出答案 906,150,257,即偶马在此时首次领先,当然,肯定只领先 1 步。对这个程序稍做修改,可以得到:

  • 在第 906,180,359 步偶马领先奇马 1 步。
  • 在此之前,偶马和奇马领先对方的最多步数是:
    • 在第 712,638,284 步奇马领先偶马 29,736 步
    • 在第 906,150,493 步偶马领先奇马 31 步

这个程序只使用大约 320KB 的内存,我想,在 1980 年田中实应该是使用类似的程序。就算那时的计算机比现在慢 1000 倍,也只需运行 3 小时 20 分钟就行了。