前言

在刷Leetcode的时候,接触到了数根的概念(258. Add Digits)。 但只是粗略地浏览了一下相应的条目,知道了计算数根的公式,但对于数根的其他方面还不了解。为了更深入地理解数根,我对数根的 Wikipedia 部分内容进行了翻译,遂有了此文。

翻译正文

单个非负整数的数根(也叫做重复的数字和)的值是通过一个迭代的数字求和的过程来获得的,在每个迭代的过程中使用前一个迭代过程的结果来计算数字和。 这个过程会一直持续,直到求出一个个位数的结果。

例如,65536的数根是7,因为 6 + 5 + 5 + 3 + 6 = 25,2 + 5 = 7

数根可以通过模数运算中的同余运算来计算出,而不一定非要通过求出所有数字的和来计算。模数运算的方法在计算非常大的整数的时候能够节省很多时间。

数根能够用来做一种校验和,去检查求和运算是否被正确地执行。如果执行正确,那么给定数字的和的数根将等于给定数字的数根的和的数根。这个检查仅仅涉及单个数字的计算,却能够在计算中发现许多的错误。

数根也在西方的数秘术中被使用,但是某些被认为拥有隐匿含义的数字(比如11和22)并没有完全被降低成单个数字。

一个整数被计算成为数字和的过程中,求和的次数叫做数字的附加韧性;在上面的例子中,65536的附加韧性为2。

数根的意义和计算方法

一个正整数的数根有助于看到比它小的最大的是9的倍数的整数的位置。例如,11的数根是2,它表示11是9(译者注:这里也可以是9的倍数)之后的第二个数字。同样的,2035的数根是1,它意味着2035 - 1是9的倍数。如果一个数字的数根是9的话,那么这个数字就是9的倍数。

有了这一想法,一个正整数的数根就可以通过地板除函数$ \lfloor x\rfloor $来定义,如下所示: $$ dr(n) = n-9 \left\lfloor\frac{n-1}{9}\right\rfloor $$

数根的抽象乘法

下表展示了数根产生的和十进制系统中相似的乘法表。

dr 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9
2 2 4 6 8 1 3 5 7 9
3 3 6 9 3 6 9 3 6 9
4 4 8 3 7 2 6 1 5 9
5 5 1 6 2 7 3 8 4 9
6 6 3 9 6 3 9 6 3 9
7 7 5 3 1 8 6 4 2 9
8 8 7 6 5 4 3 2 1 9
9 9 9 9 9 9 9 9 9 9

上面这张表展示了Vedic square中许多有趣的模式对称

正式定义

我们让$S(n)$来表示整数n的所有数字的和,同时让$S(n)$按照下面的方式来构造:

$$ {\displaystyle S^{1}(n)=S(n), S^{m}(n)=S\left(S^{m-1}(n)\right),\ { m \ge 2.}} $$

最终序列$ S^1(n),S^2(n),S^3(n),\dotsb $变成了只有一位的整数,让我们用$ {S^{*}(n)} $(n的数字和)来表示这个只有一位的整数。

示例

让我们来寻找1853的数字和。

$$ S(1853) = 17 $$ $$ S(17) = 8 $$

因此,

$$ S^2(1853)=8.$$

最终可以简化成下面这样:

$$ {\displaystyle S^{*}(1853)=dr(1853)=8.} $$

证明一个常数的存在

我们如何知道序列 $S^1(n),S^2(n),S^3(n),\dotsb$最终一定会成为一个只有一位的整数呢?下面是证明过程:

我们让$ n = d_1 + 10d_2 + \dotsb + 10^m-1d_m $,所有的$i,d_i$都是一个大于等于0且小于10的整数。因此,$ S(n) = d_1 + d_2 + \dotsb + d_m$。这里意味着只有在$ d_2, d_3, \dotsb, d_m = 0 $的情况下,$ S(n) \lt n $,在这种情况下$n$是一个一位的整数。因此,重复地使用$S(n)$函数将会使$n$至少减少1,直到$n$变成了一个一位的整数,此时它将会保持不变,成为$ S(d_1) = d_1$

同余公式

公式是:

Picture miss

或者

$$ dr(n) = 1 + ((n - 1) \pmod 9) $$

要将数根的概念推广到其他进制$b$,只需要简单地将公式中的9改成$b - 1$即可。

(sequence A010888 in the OEIS)

数根是模9的值,因为$10 \equiv 1 \pmod 9$,因此$10^k \equiv 1^k \equiv 1 \pmod 9$,所以无论位置是什么,模9的值都相等,$ a * 100 \equiv a * 10 \equiv a \pmod 9$,这就是为什么数字可以有意义地加,具体来说,比如一个三位数的整数:

$$ dr(abc) = a * 10^2 + b * 10 + c * 1 \equiv a * 1 + b * 1 + c * 1 \equiv a + b + c \pmod 9 $$