数字が入れ替わっても次は同じです。例えば23 -> 22 + 32 = 13、32 -> 32 + 22 = 13です。こういうときは重複組合せですね。なのですが、場合の数を計算しやすいように、
1 1 1 2 2 3 4
とするところを、
(1, 3) (2, 2) (3, 1) (4, 1)
としました。
また、89に帰着する数の方が圧倒的に多いので、1に帰着する方を数えたほうが速いです。
107で15ms、1019で17秒でした。
数字が入れ替わっても次は同じです。例えば23 -> 22 + 32 = 13、32 -> 32 + 22 = 13です。こういうときは重複組合せですね。なのですが、場合の数を計算しやすいように、
1 1 1 2 2 3 4
とするところを、
(1, 3) (2, 2) (3, 1) (4, 1)
としました。
また、89に帰着する数の方が圧倒的に多いので、1に帰着する方を数えたほうが速いです。
107で15ms、1019で17秒でした。