自然数数字幂和的周期性

摘要:本文探讨的问题源自数学小游戏“一个数的数字平方和”:即计算任意十进制自然数的各位数字的平方和,并对结果反复计算,形成的序列都会出现循环。通过分析序列单调性及运用抽屉原理,本文证明了序列出现循环节的必然性,并将平方和推广到任意次幂和。本文还探讨了此类周期性现象的本质原因。

关键词:数字幂和 周期性 自然数变换 抽屉原则

 

1 问题描述

文献1有介绍数学游戏“一个数的数字平方和”:我们从任何一个正整数开始,比如9246,求出他的各位数字的平方和(81+4+16+36=137)。再对这个数做同样的事情(137给出1+9+49=59),并且对每次所得结果重复这一步骤,这样便得到一个整数序列。对于我们的例子,这个序列是9246,137,59,106,37,58,89,145,42,20,…

那么,不论开始是人们选取什么整数,所得到的序列,要么出现数1(而在1之后显然就永远重复这个数字),要么出现数4(而在4之后就一直循环地出现4,16,37,58,89,145,42,20)。

对上述是问题稍作推广有一般的自然数数字幂和问题

:对位十进制自然数

次数字幂和为 定义其复合 则序列一定会出现周期循环,即对任意充分大的t,存在周期T,使得。而且循环节的种类是有限的。

“一个数的数字平方和”描述的即为问题

2 P2的证明

2.1 N充分大时的序列单调性分析

通过观察不难做直观上的猜测:充分大时,的数字平方和比小。即 下面分析得到一个下界,对于位数,令,则此时必有。于是我们得到一个下界

于是对于充分大的N,序列的前面一些项是递减的,直至出现小于的项,且

2.2 验证性证明

由前述分析,对于任意N,序列会一定出现小于的项,因此我们有如下引理

: 如果时,成立,则对于任意成立。

用计算机程序甚至手动筛除都不难验证,对于1~999的自然数,成立。出现的循环节共有两种,不动点{1}和{4,16,37,58,89,145,42,20}。于是对于任意成立。至此我们得到了的完整证明,注意到我们逐一验证了的自然数,这是一个平凡的做法。

3 Pk的证明

3.1 N充分大时的序列单调性分析

类似2.1,我们可以找到一个下界,使得。对于位数有,令是线性函数,是指数函数,故不等式必有解。总能找到下界。如时,取

于是对于充分大的,序列的前面一些项是递减的,直至出现小于的项$S_k^{(t_0)}(N)$,且$t_0<N$。

3.2 Pk的构造性证明

类似2.2,我们有如下引理

:如果时,成立,则对于任意成立。

对于具体的值,我们依然可以用2.2中的方法:先可以找到下界,然后验证所有小于的自然数成立。

如对,验证1~9999的自然数,发现成立,于是对于任意成立。出现的循环节有如下9种:

{1},{153},{370},{371},{407},{55,250,133},{136,244},{160,217,352},{919,1459}。

但对于一般的,我们要证明循环节的存在性,不能去一一验证。下面用抽屉原则给出一个构造性证明。

首先换个角度理解循环节的存在,即序列中出现重复项。我们有如下引理

:对于任意,若序列中出现重复项,则成立。下面我们证明对于中必然出现重复项。

我们称为震荡域,反之为下降域。序列前后两项,可能由震荡域进入下降域,但由3.1的分析知,序列经过有限的长度,一定会再进入震荡域。于是序列在震荡域取值可达次(实际上是无穷次),而震荡域的不同值小于,由抽屉原则知,必有两次取值相同,序列中必然出现重复项。另外循环节种类小于,一定是有限的。至此由引理可知得证。

4 进一步的思考

对于问题中的循环节也有相关研究,比如中的$k$位不动点被称为回归数,如$k$取3时共有4个回归数153、370、371、407。2

证明过程本质上与进制关系不大,事实上对于任意进制,自然数数字幂和都有周期性,这里也不再赘述。

自然数数字幂和是一种定义域与值域都是自然数的函数,不妨称这种函数为自然数变换。

对于自然数反复施用自然数变换S,得到序列,由的证明不难理解序列出现循环的充要条件是重复大时,。序列会逐渐减小直至到达一个有限的震荡域出现循环。这里就不再给出具体的证明了。

 

参考文献:

  1. 数学中的智巧. R.亨斯贝尔格 著. 李忠 译. 北京大学出版社. pp76, 1985. 

  2. Pickover, C. A. “The Latest Gossip on Narcissistic Numbers.” Ch. 88 in Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning.Oxford, England: Oxford University Press, pp. 204-205, 2001.