题目

Problem 555: McCarthy 91 function

The McCarthy 91 function is defined as follows:

We can generalize this definition by abstracting away the constants into new variables:

This way, we have $M_{91}=M_{100,11,10}$ .
Let $F_{m,k,s}$ be the set of fixed points of $M_{m,k,s}$ . That is,
$F_{m,k,s}=\{n\in\mathbb{N}|M_{m,k,s}(n)=n\}$
For example, the only fixed point of $M_{91}$ is $n=91$ . In other words, $F_{100,11,10}=\{91\}$ .
Now, define $SF(m,k,s)$ as the sum of the elements in $F_{m,k,s}$ and let $S(p,m)=\sum_{1\le s<k\le p}SF(m,k,s)$ .

For example, $S(10,10)=225$ and $S(1000,1000)=208724467$ .
Find $S(10^6,10^6)$ .

分析

对 $M_{m,k,s}(n)$ 的几个典型值进行简单计算后，我们发现，对于正整数 $b,c$ ，当且仅当 $k=b(c+1),s=bc,(1\le{s}<k\le{p})$ 时，
$F_{m,k,s}=\{m-bc+i|1\le{i}\le{b}\}$ .
利用等差数列的求和公式，得到：
$SF(m,k,s)=bm+\frac{b(b+1)}{2}-b^2c$ .
现在，我们令 $a=\lfloor\frac{p}{b}\rfloor-1$ ，再次利用等差数列的求和公式，得到：
$\sum_{c=1}^{a}SF(m,k,s)=\frac{(1+2m-ab)ab}{2}$ .
最终，我们得到： $S(p,m)=\frac{1}{2}\sum_{b\ge{1}}(1+2m-ab)ab$ .
注意，在这个和式中，a 不是自由变量，而是 p 和 b 的函数。而且这个和式也不是无限和，求和进行到 a = 0 为止。

解答

根据以上分析，我们有以下 Haskell 程序：

main = let p = 10^6; m = p in print $ (flip div 2) $ sum $
  takeWhile (>0) [(1+2*m-z)*z | b <- [1..], let z = b * (div p b - 1)]

简要说明：

div p b - 1 就是上面的分析中提到的 a
z 就是 ab

这个程序的运行时间是 0.267 秒。

555. McCarthy 91 函数

题目

分析

解答

参考资料

黄志斌

Wir müssen wissen, wir werden wissen.

相关图书

哈代数论（第6版）