关于《计算机程序设计艺术》第一卷“习题注记”中的一道练习

Question

在TAOCP卷1的“练习注记”中有一个问题，大意如下：

“证明 13^3 = 2197。推广你的答案。（这是一种可怕的问题，作者试图避免）。”

问题：

1. 你会如何证明这个问题？（直接相乘是一种方式，另一种方式可以使用(a+b)^3的公式）。解决方案需要使用一些方法来实现某种形式的概括吗？

2. 这里的推广是什么？

3. 为什么这是一种可怕的问题？

4. 你知道的其他类似可怕问题有哪些？

非常感谢任何回答。

P.S. 如果上面的问题陈述让它看起来像作业问题，我深表歉意，但它不是作业问题。请求大家不要将其标记为作业问题，这样更多的人就可以给出答案。

- vshenoy

---

在这个上下文之外，这是一个计算，不需要任何证明。 - Kobi

这里有与编程相���的问题吗？ - kloucks

我猜想，考虑到所讨论的书是《计算机程序设计艺术》，它至少有些相关性 - 但我认为这更多是Knuth想要明确告知其他数学人员哪些内容被认为超出了范围。 - garethm

Answer 1

我猜他可能是在暗示从Peano公理开始证明它的方法。然后构造整数，并继续正式证明13^3 = 2197是指数定义的自然、逻辑结论。

我们可以将其推广，证明对于给定的a和b，存在一个整数c，即a^b。

这是一种可怕的问题，因为大多数人觉得它不太有趣。

类似的问题可以在分析课程中找到（以及一些更有趣的问题）。

- garethm

---

嗨，garethm，我有疑问。如果上述问题需要使用Peano公理，那么它的难度至少是M30或HM30，而我认为这个问题的难度不到15。可能期望的问题是这样的（例如）： 证明1 + 2 + 3 +…+ 10 = 55。概括你的答案。 答案可能是这样的： (1 + 10) + (2 + 9) +…+ (5 + 6) = 5 x 11 = (10 x 11) / 2 显然概括是 1 + 2 + 3 +…+ n = (n x (n + 1)) / 2（至少对于高斯如此）。 如果是这样，那么13的三次方等于2197中隐藏了什么样的等式？ - vshenoy

Answer 2

我最初的想法如下：
n³ = n * n * n
log_n(n³) = log_n(n*n*n)
log_n(n³) = log_n(n) + log_n(n) + log_n(n)
3 = 1 + 1 + 1
3 = 3

这种运用对数恒等式的方法似乎有些循环，但考虑到我的算法研究方向，这种感觉却是令人安心的。

- Stuart Thiel

Answer 3

我遇到了同样的练习而且用这种方式“解决”了它： a^b = mult(i=1 to b) a

经过一番思考，我得出结论这是一个质因数分解（13和3都是质数）。搜索费马小定理。

（我知道这是一个旧帖子，但也许这会对正在寻找答案的人有所帮助。）

- user3060129