Question

一自然数的各位数字之和是1784.该自然数是什么？

Answer 1

2021-06-18 修改回答

找到了高效率的算法，直接计算出符合条件的自然数至少有多少个。

采用爬楼梯算法。把问题转换一下，一次可以爬1到9个台阶，爬上 1784 级台阶，一共有多少种方案？

递归公式，第n级的方案数量是f(n)，则：

 f(n)=f(n-9)+n(n-8)+n(n-7)+n(n-6)+n(n-5)+n(n-4)+n(n-3)+n(n-2)+n(n-1)

类似的讨论很多，证明就不列出了。这是斐波那契数列的一个扩展形式。

计算结果，不包含零的话，可以找到 9.46639556*10^535 个这样的自然数。

如果包含零，那就有无穷多个。

附：计算结果和fortran代码，结果是一个536位的大整数

2021-06-16 的回答

如果这个自然数的数字中可以包含0，那么就有无穷多个解。

如果这个自然数的数字中不包含0，那么：

它最少也要199位，也就是198个9和1个2的情形；最多可以是1784位的大整数，也就是都是1的情形。

没有现成的算法可以求解符合条件的大正整数的个数。可以估算一下达到何种规模。

123456789，九个数字的和是45。1784/45=39余29。

因此，可以用1到9重复使用45次，剩下的29分拆为3个9，1个2。

这样是：42个9，40个2，其它数字都是39个，一共是42+40+39*7=355位。

这个组合的全排列数量是：

355!/(39!)^7/42!/40! = 4.0217168934962448318747534923659980761*10^329

方案的数量达到了 10的330次方。极其巨大！

这还只是其中的一个组合的全排列情形。可以肯定，这个问题的解远不止这个规模。

供参考。