301

** 取石子游戏 **

取石子游戏是用数堆石子进行的游戏，由两名玩家轮流从任意一堆中取走任意数量的石子，直到石子全部取完为止。

我们考虑按如下方式进行的三堆经典取石子游戏：

• 游戏开始时有三堆石子。
• 每名玩家在轮到自己时从任意一堆中取走任意正数枚石子。
• 轮到时已无石子可取的玩家输掉游戏。

如果用 (n1,n2,n3) 表示游戏目前的三堆石子分别有 n1、n2 和 n3 枚，那么存在一个简单函数 X(n1,n2,n3)——你可以查询相关知识或自己推理得出——其函数值为：

• 零，如果在双方都采取最优策略的情况下即将取石子的玩家最终会输掉游戏；或者
• 非零，如果在双方都采取最优策略的情况下即将取石子的玩家最终会赢得游戏。

例如，X(1,2,3) = 0，因为无论当前玩家如何操作，他的对手都能够给他留下两堆同样规模的石子并不断仿照他的操作直到石子全部取完；因此当前玩家必定会输掉游戏。举例来说：

• 当前玩家取完后留下 (1,2,1)
• 对手玩家取完后留下 (1,0,1)
• 当前玩家取完后留下 (0,0,1)
• 对手玩家取完后留下 (0,0,0)，对手玩家获胜。

有多少个正整数 n ≤ 230 使得 X(n,2n,3n) = 0？

302

** 强阿喀琉斯数 **

我们称正整数 n 是 ** 强大的（似幂的）**，如果对于 n 的每一个质因数 p，p2 都是 n 的约数。

我们称正整数 n 是 ** 完美的（完全幂的）**，如果 n 可以表达成另一个正整数的幂。

我们称正整数 n 是 ** 阿喀琉斯数 **，如果 n 是强大的但不是完美的。例如，864 和 1800 都是阿喀琉斯数：864 = 25·33，而 1800 = 23·32·52。

我们称正整数 S 是强阿喀琉斯数，如果 S 和φ(S) 都是阿喀琉斯数。1 例如，864 是强阿喀琉斯数：φ(864) = 288 = 25·32。然而，1800 不是强阿喀琉斯数：φ(1800) = 480 = 25·31·51。

一共有 7 个小于 104 的强阿喀琉斯数，656 个小于 108 的强阿喀琉斯数。

有多少个小于 1018 的强阿喀琉斯数？

1 φ表示 ** 欧拉总计函数 **。

303

** 数字较小的倍数 **

正整数 n 的有些正倍数在十进制下所有数字均≤ 2，记其中最小的为 f(n)。

因此 f(2)=2，f(3)=12，f(7)=21，f(42)=210，f(89)=1121222。

此外，已知∑n=1100f(n)n=11363107。

求∑n=110000f(n)n。

304 ** 素斐波那契数 **

对于任意正整数 n，函数 next_prime(n) 给出满足 p>n 的最小素数 p。

序列 a(n) 按如下方式定义： a(1)=next_prime(1014)；对于 n>1，a(n)=next_prime(a(n-1))。

斐波那契数列 f(n) 按如下方式定义：f(0)=0，f(1)=1；对于 n>1，f(n)=f(n-1)+f(n-2)。

序列 b(n) 的定义为 f(a(n))。

对于 1≤n≤100 000，求∑b(n)。将你的答案模 1234567891011 取余。 305 ** 自反位置 **

我们将十进制下的连续正整数（从 1 开始）拼接起来，构造出（无限长的）字符串 S。 也即是说，S = 1234567891011121314151617181920212223242…

很容易看出，任何数都会在 S 中出现无限多次。

我们称 f(n) 是 n 在 S 中第 n 次出现时的起始位置。 例如，f(1)=1，f(5)=81，f(12)=271，以及 f(7780)=111111365。

对于 1≤k≤13，求∑f(3k)。 306 ** 纸条游戏 **

以下游戏是组合博弈论中的一个经典例子：

游戏开始时，有一张划成 n 个白格的纸条，两名玩家轮流进行操作。 每一轮，一名玩家选择相邻的两个白格，并将它们涂成黑色。 首先无法进行操作的玩家输掉游戏。

• 如果 n = 1，不存在合法操作，先手玩家自动输掉游戏。
• 如果 n = 2，只有一种合法操作，在此之后后手玩家输掉游戏。
• 如果 n = 3，有两种合法操作，但在此之后后手玩家均输掉游戏。
• 如果 n = 4，有三种合法操作，先手玩家只需将中间两个白格涂成黑色即可赢得游戏。
• 如果 n = 5，有四种合法操作（如下图红色所示）；但无论先手玩家如何操作，后手玩家（蓝色所示）都将赢得游戏。

因此，对于 1 ≤ n ≤ 5，共有 3 种 n 值使得先手玩家必胜。 同样地，对于 1 ≤ n ≤ 50，共有 40 种 n 值使得先手玩家必胜。

对于 1 ≤ n ≤ 1 000 000，共有多少种 n 值使得先手玩家必胜？ 307 ** 电路瑕疵 **

在一个工厂生产的 n 块集成电路上随机分布有 k 个瑕疵（一块集成电路上可能有任意数量的瑕疵，瑕疵之间相互独立）。

记 p(k,n) 为存在一块集成电路上面有至少 3 个瑕疵的概率。 例如，p(3,7) ≈ 0.0204081633。

求 p(20 000, 1 000 000)，并将你的答案四舍五入到 10 位小数，即形式为 0.abcdefghij。 308 ** 神奇的素数生成自动机 **

用编程语言 Fractran 所写的程序由一个分数序列组成。

Fractran 虚拟机的内部状态为一个正整数，初始化时被设定为某个种子值。在 Fractran 程序每次迭代时，找到序列中第一个与状态整数相乘得到整数的分数，并更新状态整数为新得到的整数。

例如，约翰 · 何顿 · 康威所写的一个用于素数生成的 Fractran 程序由下列 14 个分数组成：

1791, 7885, 1951, 2338, 2933, 7729, 9523, 7719, 117, 1113, 1311, 152, 17, 551.

从种子值 2 开始，这个程序的连续迭代生成了如下的序列： 15, 825, 725, 1925, 2275, 425, …, 68, 4, 30, …, 136, 8, 60, …, 544, 32, 240, …

在这个序列中出现的 2 的幂为 22, 23, 25, … 可以看出所有出现在序列中的 2 的幂，其指数均为素数，而且所有素数恰好按顺序作为 2 的指数出现！

如果有人用上述 Fractran 程序来解决欧拉计划第 7 题（找出第 10001 个素数），需要迭代多少步才能生成 2 第 10001 个素数? 309 ** 整数梯子 **

在经典问题 “穿越梯子” 中，我们已知两架长度分别为 x 和 y 的梯子相对靠在一条狭长、水平街道的两侧墙上。我们还知道两架梯子相交处的高度为 h，最终目标是求街道的宽度(w)。 在这个问题中，我们只关心所有四个变量均为正整数的情况。 例如，如果 x = 70，y = 119，h = 30，我们可以计算出 w = 56。

事实上，若 x、y、h 均取正整数，且 0 <x < y < 200，只有五个三元组 (x,y,h) 能解出 w 为整数： (70, 119, 30)、(74, 182, 21)、(87, 105, 35)、(100, 116, 35) 和 (119, 175, 40)。

若 x、y、h 均取正整数，且 0 <x < y < 1 000 000，有多少个三元组 (x,y,h) 能解出 w 为整数？ 310

** 取平方数石子 **

爱丽丝和鲍勃正在玩取平方数石子的游戏。 取平方数石子游戏和通常玩的三堆经典取石子游戏基本一致，只是玩家每次从堆中只能取走平方数枚石子。 三堆中的石子数目用有序三元组 (a,b,c) 表示。 如果 0≤a≤b≤c≤29，将要取石子的玩家必败的状态有 1160 种。

如果 0≤a≤b≤c≤100 000，求将要取石子的玩家必败的状态数目。