数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

プロジェクトオイラー555. ~ McCarthy 91 function ~


スポンサードリンク

No.555 McCarthy 91 function.

プロジェクトオイラーの555番です.

とりあえず問題を見てみましょう.



問題.

マッカーシーの91関数は以下のように定義される.
\begin{align*}
M_{91}(n) &= \left\{\begin{array}{ll}n-10 & \mathrm{if}\,n>100\\
M_{91}(M_{91}(n+11)) & \mathrm{if}\,0\leq n\leq 100\end{array}\right.
\end{align*}この定義に含まれる定数を新しい変数に抽象化することで,この関数を一般化することを考える.
\begin{align*}
M_{m, k, s}(n) &= \left\{\begin{array}{ll}n-s & \mathrm{if}\,n>m\\
M_{m, k, s}(M_{m, k, s}(n+k)) & \mathrm{if}\,0\leq n\leq m\end{array}\right.
\end{align*}このとき, M_{91}=M_{100,11,10}となっている. F_{m, k, s} M_{m, k, s}の固定点の個数,すなわち,
\begin{align*}
F_{m, k, s}= \{n\in\mathbb{N}\mid M_{m, k, s}(n)=n\}
\end{align*}
とする.

例えば, M_{91}の場合は唯一の固定点が n=91なので, F_{100,11,10}=\{91\}となる.さらに, SF(m, k, s) F(m, k, s)の要素の和とし,
\begin{align*}
S(p, m) = \sum_{1\leq s < k \leq p} SF(m, k, s)
\end{align*}
とする.

例えば, S(10,10)=225, S(1000,1000)=208724467となる.

 S(10^6, 10^6) を求めよ.




考え方とプログラム例など(Python3)

マッカーシーの91関数というのは有名な再帰関数で,計算機科学者のジョン・マッカーシーが考案したものです.

ちなみにジョン・マッカーシープログラミング言語LISPの開発や,1956年のダートマス会議で「Artificial Intelligence:人工知能」という言葉を初めて用いた人物として知られています.



さて,この問題はマッカーシーの91関数を一般化したものの固定点を求める問題ですが,実際に M_{m, k, s}(n)の値をすべて再帰的に求めることは不可能なので,この関数がどのような値を取るのか調べてみます.


まずは M_{91}=M_{100,11,10} 0\leq n\leq 100の場合を調べてみます.


例えば, M_{91}(101)=91となることは分かっているので, 90\leq n\leq 100 の場合を考えると,

\begin{align*}
M_{91}(n) &= M_{91}(M_{91}(n+11))\\
&= M_{91}(n+1)
\end{align*}

となるので, M_{91}(90)=M_{91}(91)=\cdots=M_{91}(100)=91となります.


同様に調べていけば, n=1, 2, \ldots, 100について M_{91}(n)=91となることが確認できます.


次に,一般化した関数の場合を調べてみましょう.

 n > mに対しては M_{m, k, s}(n)=n-sで, m-k+1\leq n\leq mの場合を考えると,

\begin{align*}
M_{m, k, s}(n) &= M_{m, k, s}(M_{m, k, s}(n+k))\\
&= M(n+(k-s))
\end{align*}
となります.

 m-2k+1\leq n\leq m-kの場合

\begin{align*}
M_{m, k, s}(n) &= M_{m, k, s}(M_{m, k, s}(n+k))\\
&= M_{m, k, s}(M_{m, k, s}(M_{m, k, s}(n+2k)))\\
&= M_{m, k, s}(M_{m, k, s}(n+2k-s))\\
&= M_{m, k, s}(n+2k-2s)
\end{align*}


同様に, m-pk+1\leq n\leq m-(p-1)kの場合,( p\in\mathbb{N})

\begin{align*}
M_{m, k, s}(n) &= M_{m, k, s}(n+p(k-s))
\end{align*}

となり,このことから,ある自然数 x_nが存在して, M_{m, k, s}(n) = n+x_n(k-s)-sと書けることがわかります.



固定点 M_{m, k, s}(n)=nとなるためには, x_n(k-s)=s なので, k-s sの約数である必要がある.( k-s sの約数でない場合には F(m, k, s)=\emptysetとなる.)

 

このとき,

\begin{align*}
F(m, k, s) = \{m-s+1, m-s+2, \ldots, m-s+(k-s)\}
\end{align*}

となる.



したがって, k-s sの約数となるような k, sの組について

\begin{align*}
SF(m, k, s) &= (m-s+1)+(m-s+2) + \cdots+(m-s+(k-s))\\
&= \frac{1}{2}(k-s)(2m-2s+k-s+1)
\end{align*}

の和を求めれば良いことになります.



この先はプログラムを書く上でのテクニックですが, k, sの組をすべて調べて k-s sを割り切るとき,とやると時間がかかってしまうので, k-s aのとき s=a, 2a, \ldotsの場合を数え上げるという考え方をします.以下のプログラムでは k-sをksという変数で扱っています.

p = 10**6
m = 10**6
A = 0
for ks in range(1, p//2+1):
    s = ks
    while s + ks <= p:
        A = A + (2*m-2*s+ks+1)*ks/2
        s = s + ks
print(A)
#ks:=k-s