B - Happy Number 解説
by 
MMNMM
一回の操作で \(x\) が \(f(x)\) になるとします（つまり、\(f\) は引数の各桁の二乗和を返す関数です）。
この問題の操作を繰り返すことで、どの正整数も \(1\) もしくは \(4\) のどちらか一方に到達することが知られています。 ある程度の論証と探索を行うことでこの事実を示すことができます。
証明
まず、どのような \(x\) から操作を開始しても \(99\) 以下の値に到達することを示します。
正整数 \(x,y\) について、\(x\) が \(y\) より全桁大きいことを
- どの非負整数 \(d\) についても、\(x\) の \(10 ^ d\) の位が \(y\) の \(10 ^ d\) の位以上である
ことと定めます。
\(x\) が \(y\) より全桁大きいとき、明らかに \(f(x)\ge f(y)\) です。
どのような \(d\) 桁の整数 \(x\) に対しても、\(9\) を \(d\) 桁並べた数 \(N _ d\coloneqq10 ^ {1+\lfloor\log _ {10}x\rfloor}-1\) は \(x\) より全桁大きいです。
\(100\le x\) ならば \(f(x)\lt x\) が成り立つことを、\(x\) の値で場合分けを行って示します。
\(1000\le x\) のとき、\(d\ge3\) ならば \(81d\lt10 ^ d\) が成り立つことを \(d\) についての帰納法で示すことができるので、\(f(x)\le f(N _ d)=81d\lt10 ^ d\le x\) が成り立ちます。
\(244\le x\lt1000\) のとき同様に \(f(x)\le f(999)=243\lt x\) が成り立ちます。
\(167\le x\lt244\) のとき \(299\) は \(x\) より全桁大きく、\(f(x)\le f(299)=4+81+81=166\lt x\) が成り立ちます。
\(118\le x\lt167\) のとき \(169\) は \(x\) より全桁大きく、\(f(x)\le f(169)=1+36+81=118\lt x\) が成り立ちます。
\(100\le x\lt118\) のとき \(119\) は \(x\) より全桁大きく、\(f(x)\le f(118)=1+1+81=83\lt x\) が成り立ちます。
よって、\(100\le x\) を満たすすべての整数 \(x\) に対して \(f(x)\lt x\) が示されました。
以上から、\(100\) 以上の整数 \(x\) に対して少なくとも \(x-99\) 回操作を行うことで \(99\) 以下の値に到達することが示されました。
あとは、\(99\) 以下の整数からはじめて \(1\) もしくは \(4\) に到達することを確認すればよいです。 \(28\) と \(82\) など、桁を構成する数字の多重集合が等しいような整数は、それらのうち \(1\) つを調べればよい（\(1\) 回操作すると同じ値に合流する）ので、\(54\) 個の初期値を確認すれば十分です。
最も操作すべき回数が多いのは \(88\) で、\(88\rightarrow128\rightarrow69\rightarrow117\rightarrow51\rightarrow26\rightarrow40\rightarrow16\rightarrow37\rightarrow58\rightarrow89\rightarrow145\rightarrow42\rightarrow20\rightarrow4\) と \(14\) 回の操作で \(4\) に到達します。
実装例は以下のようになります。
#include <iostream>
using namespace std;
int main() {
// 操作の結果を得る関数
auto next = [](auto x){
int ret = 0;
do
ret += (x % 10) * (x % 10);
while (x /= 10);
return ret;
};
int N;
cin >> N;
// 1 か 4 に到達するまで操作して
while (N != 1 && N != 4)
N = next(N);
// 1 なら Yes 、4 なら No
cout << (N == 1 ? "Yes" : "No") << endl;
return 0;
}
投稿日時:
最終更新: