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

この記事の所要時間: 66

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という変数で扱っています.

答えはこの下にあります.
Ans : 208517717451208352

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加