Задача 555
Фкнуция Маккарти 91

Фкнуция Маккарти 91 задается следующим образом:$$M_{91}(n) = \begin{cases} n - 10 & \text{если } n > 100 \\ M_{91}(M_{91}(n+11)) & \text{если } 0 \leq n \leq 100 \end{cases}$$

Мы можем обобщить это определение функции, заменив константы на новые переменные:$$M_{m,k,s}(n) = \begin{cases} n - s & \text{если } n > m \\ M_{m,k,s}(M_{m,k,s}(n+k)) & \text{если } 0 \leq n \leq m \end{cases}$$

Таким образом, получим $M_{91} = M_{100,11,10}$.

Пусть $F_{m,k,s}$ будет множеством неподвижных точек $M_{m,k,s}$. То есть, $$F_{m,k,s}= \left\{ n \in \mathbb{N} \, | \, M_{m,k,s}(n) = n \right\}$$

Например, единственной неподвижной точкой $M_{91}$ является $n = 91$. Другими словами, $F_{100,11,10}= \{91\}$.

Теперь, определим $SF(m,k,s)$ как сумму элементов в $F_{m,k,s}$, и пусть $S(p,m) = \displaystyle \sum_{1 \leq s < k \leq p}{SF(m,k,s)}$.

Например, $S(10, 10) = 225$ и $S(1000, 1000)=208724467$.

Найдите $S(10^6, 10^6)$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net