数の各桁の平方和をとり続けると1か37が出てくることの証明

百科事典を読んでいたら次のような記事が載っていました（要約）。

自然数（10進数）の各桁の数字の2乗の和を作る。
この結果についてまた同様に各桁の2乗の和を作る。
この操作を繰り返すと
(1) 37→58→89→145→42→20→4→16→37→… で循環
(2) 1→1→… で循環
のどちらかになる。

自然数の各桁の平方和をとり続けると必ず1か37が出てくるというわけですが、この証明を知りたいです。
証明の載っているHP・書籍等ご存知でしたら教えてください。

No.2 ベストアンサー 回答者： arrysthmia 回答日時： 2008/04/12 03:38

エレファントな探索を続けてみます。

(a^2 + b^2 + c^2) - (100 a + 10 b + c)
= (a - 50)^2 + (b - 5)^2 + (c - 1/2)^2 - (2500 + 25 + 1/4)

100 a + 10 b + c が３桁の数であれば
　-49 ≦ a - 50 ≦ -41,
　-5 ≦ b - 5 ≦ 4,
　-1/2 ≦ c - 1/2 ≦ 17/2
だから、

(a^2 + b^2 + c^2) - (100 a + 10 b + c)
≦ 49^2 + 5^2 + (17/2)^2 - (2500 + 25 + 1/4) = -27 ＜ 0

３桁でも、操作の結果は値が減少する。

９９まで位なら、手計算でも…

この回答へのお礼

回答ありがとうございます。
ほんの一瞬歓喜しました。
エレファントのほうでしたか（笑）。
ともあれ、調べる範囲を2桁まで減らせるんですね。

お礼日時：2008/04/13 21:43

No.3 回答者： kabaokaba 回答日時： 2008/04/12 10:31

>９９まで位なら、手計算でも…

いやあ，手計算かなりしんどいですよ．
1から99まで，全部で279回の各桁の平方和を作ることになります．
それに途中で「同じ値」がきたら整理しないといけませんが
それもそこそこあるはずです．

エレファントに計算してみます．
1から99までのこの過程は以下のようになります．
1から99でこの計算を実行した結果が 1 :: の列，
その結果に対して実行したのが 2 :: の列となってます．
最終的に与えられた列に収束します．

1 :: 1 2 4 5 8 9 10 13 16 17 18 20 25 26 29 32 34 36 37 40 41 45 49 50 52 53 58 61 64 65 68 72 73 74 80 81 82 85 89 90 97 98 100 106 113 117 128 130 145 162
2 :: 1 4 10 11 13 16 17 25 29 34 37 40 41 42 45 50 51 52 53 58 61 64 65 68 69 81 85 89 97 100 130 145
3 :: 1 2 10 16 17 20 25 26 29 34 37 41 42 50 52 58 61 65 85 89 100 117 130 145
4 :: 1 4 10 17 20 25 29 37 40 42 50 51 58 61 85 89 145
5 :: 1 4 16 20 25 26 29 37 42 50 58 85 89 145
6 :: 1 4 16 20 25 29 37 40 42 58 85 89 145
7 :: 1 4 16 20 29 37 42 58 85 89 145
8 :: 1 4 16 20 37 42 58 85 89 145
9 :: 1 4 16 20 37 42 58 89 145

総当りじゃなくて理屈で攻めるのは
かなり厄介というか・・・そもそもできるんでしょうか？
コラッツと同種かもしれませんね．

この回答へのお礼

回答ありがとうございます。
やはり現状は、桁数を減らしてあとは力づくでやるしかないということのようですね。
まあ一応これはこれで証明済みの問題ですね。

お礼日時：2008/04/13 23:10

No.1 回答者： funoe 回答日時： 2008/04/12 00:04

>証明の載っているHP・書籍等ご存知でしたら

ご質問への回答にはなっていないですが...
もし、この命題が真であるのなら、


・４桁以上(１０００以上）の数にこの操作を施すと必ず値が減少する。
　→この操作の結果の値は、最大で、桁数＊８１だから。
・したがって９９９までの全ての数について示せばよい
　→実際に試して確認すればよい

というわけで、エレガントではないですが「証明」は容易かと。

この回答へのお礼

回答ありがとうございます。
うーむ、確かに証明にはなりますね……。

お礼日時：2008/04/13 21:37