题目

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 .
Let be the set of fixed points of . That is,

For example, the only fixed point of is . In other words, .
Now, define as the sum of the elements in and let .

For example, and .
Find .

分析

的几个典型值进行简单计算后,我们发现, 对于正整数 , 当且仅当 时,
.
利用等差数列的求和公式,得到:
.
现在,我们令 ,再次利用等差数列的求和公式,得到:
.
最终,我们得到: .
注意,在这个和式中,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 秒。

参考资料

  1. Wikipedia: McCarthy 91 function
  2. Wikipedia: Arithmetic progression