「f(n+1)=f(n)の各桁の二乗の和」という数列

某番組で次のような問題が出されていた。

次の○に入る数字は何か？
4→16→37→58→89→145→42→○→4

で、求め方はタイトルのとおりなのだが、任意の数字に対して数列を作ってみようと思い立って、次のようなプログラムを作成。

import java.util.ArrayList;
import java.util.List;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] ns = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, };
        for (int n : ns) {
            List<Integer> result = generateSequence(n);
            System.out.printf("%2d: %s%n", n, result);
        }
    }

    /**
     * 指定された数値から始まり、ある項に関数sumOfSquareOfEachDigitを
     * 適用した結果得られる数値が次の項となる数列を生成する。
     * @param n 任意の負でない整数。
     * @return
     */
    private static List<Integer> generateSequence(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                    "n must be non-negative number, but " + n + " is given.");
        }
        List<Integer> result = new ArrayList<Integer>();
        result.add(n);
        int nn = n;
        do {
            nn = sumOfSquareOfEachDigit(nn);
            result.add(nn);
        } while (result.indexOf(nn) == result.lastIndexOf(nn));
        return result;
    }

    /**
     * 指定された数値の各桁の二乗の和を計算する。
     * @param n 任意の整数。
     * @return
     */
    private static int sumOfSquareOfEachDigit(int n) {
        int res = 0;
        while (n != 0) {
            int r = n % 10;
            res += r * r;
            n /= 10;
        }
        return res;
    }
}

とりあえず0〜9まで。
実行結果は次のとおり。

 0: [0, 0]
 1: [1, 1]
 2: [2, 4, 16, 37, 58, 89, 145, 42, 20, 4]
 3: [3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37]
 4: [4, 16, 37, 58, 89, 145, 42, 20, 4]
 5: [5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
 6: [6, 36, 45, 41, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
 7: [7, 49, 97, 130, 10, 1, 1]
 8: [8, 64, 52, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
 9: [9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37]

この結果をよく見てみると、一桁の数値の中で再び同じ数値に戻ってくるのは、(0や1は別として)4しかないことが分かる。

起点となる数値をある範囲(例えばJavaのint型が取り得る非負の値、など)に絞り込むと、起点の数値以外に出現する数値はある程度限られてくる。なぜなら、例えば16と61はいずれも「 $1^2+6^2=37$ 」となるから。結局、どの数字を何個選んだかということによって、次項の数値が決定される。