TCO 2016 Round 1B Easy. ExploringNumbers

問題概要

数列 A[n] は以下のように定義される。

• A[1]=n
• A[k+1]=A[k] を 10 進表記したときの各桁の数字を二乗してから足し合わせたもの

この数列ではじめて素数が現れるのは何項目だろうか。もし現れないのであれば -1 と答えよ。

解法

各桁の二乗和は n=999999999 のとき 729 で、これが最大である。つまり A[2] 以降は 729 以下の整数しか現れない。

鳩ノ巣原理よりこの数列のループの長さは高々 729 だとわかるので、ループするまで調べていけばいい。

TCO 2016 Round 1B Easy. ExploringNumbers

桁和が結構小さい値であることと数列がループすることに気付けば簡単。