定义在正整数集上的函数 $f\left( x \right)=\left\{ \begin{align}
& 1,x=1 \\
& x/10,x被10整除 \\
& x+1,其他 \\
\end{align} \right.$ 对于任意正整数 $x$，我们定义数列 $\left\{ {{x}_{n}} \right\}$
如下：${{x}_{1}}=x,{{x}_{n+1}}=f\left( {{x}_{n}} \right),n\in {{N}^{+}}$ 。定义 $d\left( x \right)$ 为满足 ${{x}_{n}}=1$ 的最小的 $n$ 。例如，$d\left( 100 \right)=3 d\left( 87 \right)=7$ 。设 $m$ 是满足 $d\left( x \right)=20$ 的正整数 $x$ 的个数，求 $m$ 的所有不同素因数之和。
& 1,x=1 \\
& x/10,x被10整除 \\
& x+1,其他 \\
\end{align} \right.$ 对于任意正整数 $x$，我们定义数列 $\left\{ {{x}_{n}} \right\}$
如下：${{x}_{1}}=x,{{x}_{n+1}}=f\left( {{x}_{n}} \right),n\in {{N}^{+}}$ 。定义 $d\left( x \right)$ 为满足 ${{x}_{n}}=1$ 的最小的 $n$ 。例如，$d\left( 100 \right)=3 d\left( 87 \right)=7$ 。设 $m$ 是满足 $d\left( x \right)=20$ 的正整数 $x$ 的个数，求 $m$ 的所有不同素因数之和。
【难度】
【出处】
2004年第22届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
511
【解析】
设 $x={{10}^{a}}\cdot b$，其中 $a,b\in Z$，$10\overset{}{\mathop{|}} b$ 那么易知 ${{x}_{a+1}}=b$ 。
若 $b=1$，则只有 $x={{10}^{19}}$，此时有一解，下面考虑 $b1$ 的情况。
设 $b$ 的十进制表示为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k}}}$，则 $b$ 经过 $\left( 10-{{b}_{k}} \right)$ 次操作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k-2}}\left( {{b}_{k-1}}+1 \right)0}$，再经过一次操作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots\left( {{b}_{k-1}}+1 \right)}$，再经过 $\left( 9-{{b}_{k-1}} \right)$ 次操作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k-3}}\left( {{b}_{k-2}}+1 \right)0}$，再经过一次操作作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k-3}}\left( {{b}_{k-2}}+1 \right)}$，以此类推。由于 ${{x}_{20}}=1$，故
$\displaystyle a+k+1+\sum\limits_{i=1}^{k}{\left(9-{{b}_{i}} \right)}=20$ 。
次即
$\displaystyle \sum\limits_{i=1}^{k}{\left(9-{{b}_{i}} \right)}=19-a$ 。
注意到 $10-{{b}_{1}}$ 和 $10-{{b}_{k}}$ 只能取 $1,2,\ldots,9$，而其他的 $10-{{b}_{i}}$，可以取 $1,2,\ldots,10$ 。
令 ${{S}_{i}}$ 表示满足 $d\left( x \right)=i$ 的整数 $x$ 的集合 $\left( i=1,2,\ldots \right)$，如 ${{S}_{1}}=\left\{ 1\right\}$，${{S}_{2}}=\left\{10 \right\}$，${{S}_{3}}=\left\{9,100 \right\}$，${{S}_{4}}=\left\{ 8,90,99,1000\right\}$，等等。对于每个 $k\in{{S}_{i+1}}$，必有 $k+1\in {{S}_{i}}$ 或 $\frac{k}{10}\in {{S}_{i}}$；对于每个 $m\in {{S}_{i}}$ 必有 $10m\in {{S}_{i+1}}$，而 $m-1\in {{S}_{I+1}}$ 当且仅当 $m-11$ 且 $f\left( m-1 \right)=m$，故当 $m\ne 2$ 且 $m$ 的末位不为 $1$ 时，$m$ 对应两个 ${{S}_{i+1}}$ 中的数，否则 $m$ 只对应一个 ${{S}_{i+1}}$ 中的数，即
$\left|{{S}_{i+1}} \right|=2\left| {{S}_{i}} \right|-\left| {{S}_{i}}\bigcap \left\{ 2\right\}\bigcup \left\{ 10t+1 \right. \right|t\in {{N}^{+}}\bigcup \left\{ 0\right\}\left. {} \right\}\left. {} \right|$ 。
注意到 $2\in {{S}_{10}}$，而当 $t\in {{N}^{+}}$ 时，$10t+1\in {{S}_{i}}$ 当且仅当 $10t+10\in {{S}_{i-9}}$，即 $t+1\in {{S}_{i-10}}$，即除了 $i=10$ 这个特例外，$2\left| {{S}_{i}}\right|-\left| {{S}_{i+1}} \right|$ 应等于 ${{S}_{i-10}}$ 中大于 $1$ 的元素个数。这样我们得到了 $\left| {{S}_{i}} \right|$ 的递推式如下：$\left| {{S}_{i}} \right|=1,\left| {{S}_{i}} \right|={{2}^{i-2}},i=2,3,\cdots,10,\left| {{S}_{11}} \right|={{2}^{9}}-1 \left| {{S}_{12}}\right|={{2}^{10}}-2 $
$\left|{{S}_{i+1}} \right|=2\left| {{S}_{i}} \right|-\left| {{S}_{i-10}} \right| ,i\geqslant 12$ 。
因此我们有
$\left| {{S}_{20}}\right|=2\left| {{S}_{19}} \right|-\left| {{S}_{9}} \right|=4\left| {{S}_{18}}\right|-2\left| {{S}_{8}} \right|-\left| {{S}_{9}} \right|=\ldots $
$\displaystyle ={{2}^{8}}\left| {{S}_{12}} \right|-\sum\limits_{i=2}^{9}{{{2}^{9-i}}}\left|{{S}_{i}} \right|=2\left( {{2}^{10}}-2\right)+\sum\limits_{i=2}^{9}{{{2}^{9-i}}}{{2}^{i-2}}$
$={{2}^{18}}-{{2}^{9}}-8\cdot{{2}^{7}}={{2}^{9}}\cdot 509$ 。
由于 $509$ 为素数，故 $m$ 的不同素因数和为 $2+509=511$
若 $b=1$，则只有 $x={{10}^{19}}$，此时有一解，下面考虑 $b1$ 的情况。
设 $b$ 的十进制表示为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k}}}$，则 $b$ 经过 $\left( 10-{{b}_{k}} \right)$ 次操作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k-2}}\left( {{b}_{k-1}}+1 \right)0}$，再经过一次操作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots\left( {{b}_{k-1}}+1 \right)}$，再经过 $\left( 9-{{b}_{k-1}} \right)$ 次操作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k-3}}\left( {{b}_{k-2}}+1 \right)0}$，再经过一次操作作变为 $\overline{{{b}_{1}}{{b}_{2}}\ldots{{b}_{k-3}}\left( {{b}_{k-2}}+1 \right)}$，以此类推。由于 ${{x}_{20}}=1$，故
$\displaystyle a+k+1+\sum\limits_{i=1}^{k}{\left(9-{{b}_{i}} \right)}=20$ 。
次即
$\displaystyle \sum\limits_{i=1}^{k}{\left(9-{{b}_{i}} \right)}=19-a$ 。
注意到 $10-{{b}_{1}}$ 和 $10-{{b}_{k}}$ 只能取 $1,2,\ldots,9$，而其他的 $10-{{b}_{i}}$，可以取 $1,2,\ldots,10$ 。
令 ${{S}_{i}}$ 表示满足 $d\left( x \right)=i$ 的整数 $x$ 的集合 $\left( i=1,2,\ldots \right)$，如 ${{S}_{1}}=\left\{ 1\right\}$，${{S}_{2}}=\left\{10 \right\}$，${{S}_{3}}=\left\{9,100 \right\}$，${{S}_{4}}=\left\{ 8,90,99,1000\right\}$，等等。对于每个 $k\in{{S}_{i+1}}$，必有 $k+1\in {{S}_{i}}$ 或 $\frac{k}{10}\in {{S}_{i}}$；对于每个 $m\in {{S}_{i}}$ 必有 $10m\in {{S}_{i+1}}$，而 $m-1\in {{S}_{I+1}}$ 当且仅当 $m-11$ 且 $f\left( m-1 \right)=m$，故当 $m\ne 2$ 且 $m$ 的末位不为 $1$ 时，$m$ 对应两个 ${{S}_{i+1}}$ 中的数，否则 $m$ 只对应一个 ${{S}_{i+1}}$ 中的数，即
$\left|{{S}_{i+1}} \right|=2\left| {{S}_{i}} \right|-\left| {{S}_{i}}\bigcap \left\{ 2\right\}\bigcup \left\{ 10t+1 \right. \right|t\in {{N}^{+}}\bigcup \left\{ 0\right\}\left. {} \right\}\left. {} \right|$ 。
注意到 $2\in {{S}_{10}}$，而当 $t\in {{N}^{+}}$ 时，$10t+1\in {{S}_{i}}$ 当且仅当 $10t+10\in {{S}_{i-9}}$，即 $t+1\in {{S}_{i-10}}$，即除了 $i=10$ 这个特例外，$2\left| {{S}_{i}}\right|-\left| {{S}_{i+1}} \right|$ 应等于 ${{S}_{i-10}}$ 中大于 $1$ 的元素个数。这样我们得到了 $\left| {{S}_{i}} \right|$ 的递推式如下：$\left| {{S}_{i}} \right|=1,\left| {{S}_{i}} \right|={{2}^{i-2}},i=2,3,\cdots,10,\left| {{S}_{11}} \right|={{2}^{9}}-1 \left| {{S}_{12}}\right|={{2}^{10}}-2 $
$\left|{{S}_{i+1}} \right|=2\left| {{S}_{i}} \right|-\left| {{S}_{i-10}} \right| ,i\geqslant 12$ 。
因此我们有
$\left| {{S}_{20}}\right|=2\left| {{S}_{19}} \right|-\left| {{S}_{9}} \right|=4\left| {{S}_{18}}\right|-2\left| {{S}_{8}} \right|-\left| {{S}_{9}} \right|=\ldots $
$\displaystyle ={{2}^{8}}\left| {{S}_{12}} \right|-\sum\limits_{i=2}^{9}{{{2}^{9-i}}}\left|{{S}_{i}} \right|=2\left( {{2}^{10}}-2\right)+\sum\limits_{i=2}^{9}{{{2}^{9-i}}}{{2}^{i-2}}$
$={{2}^{18}}-{{2}^{9}}-8\cdot{{2}^{7}}={{2}^{9}}\cdot 509$ 。
由于 $509$ 为素数，故 $m$ 的不同素因数和为 $2+509=511$
答案
解析
备注
