趣味问题《寻人启事》的Python程序解决

偷懒了很久，今天我终于又来更新博客了~

最近，我看到了一个趣味问题，或者说是数学游戏：《寻人启事》。

在表述这个问题前，我们需要了解一下“冰雹猜想”：

对于任意一个正整数x，重复作如下变换：

• 如果x是偶数，则变为x/2；
• 如果x是奇数，则变为3x+1；

在若干次变换后，x一定会陷入4-2-1这样的循环。

对于冰雹猜想的证明，在此不多加阐述。

而《寻人启事》这个问题，就来源于知乎用户“诗人白言”（一下简称“白言”）于2019年提出的冰雹猜想的变化规律——白言规则（LiKe”s rule）：

• 任意一个不是2的幂次的正整数，经过若干次变换以后都会变为一个可以表示为3ⁿ-1（n∈N₊）^{[注：为防止有未读过高中的读者，特在此说明：n∈N₊意思是n是正整数]}的形式的数；
• 任意一个不是8（3²-1）的能表示为3ⁿ-1（n∈N₊）形式的数，在经过若干次变化后都会变为另一个这样的数；
• 经过若干次第二条的变化后，3ⁿ-1最终会变为3²-1，然后经过除以2的变化陷入4-2-1的循环；

其中集合{3ⁿ-1|n∈N₊}被称为“LiKe第二数列”。

当然，此规则白言虽给出了证明，但其证明是否正确仍众说纷纭。不知是谁，在基于白言规则的基础上提出了这样一个问题：

在任意3^(2n-1)-1和 3²ⁿ-1（n≥2，n∈Z）所变化出的3ⁿ-1（n∈N₊）形式的数中，都会有一个（如果只有一个，那一定是8也就是3²-1）或多个相同的3^m-1（m∈N₊），在这些3^m-1中最大的就称为3^(2n-1)-1和 3²ⁿ-1的孩子，3^(2n-1)-1和 3²ⁿ-1就是他的父母。寻找3^(2n-1)-1和 3²ⁿ-1的孩子的过程，就叫做寻找失踪的孩子，或者叫做《寻人启事》。

此问题的提出者们发现，像这样逐组计算下去，第五组（3¹¹-1和 3¹²-1）孩子的大小就达到了2186（ 3⁷-1 ），而至少在前一百组中，孩子都没有超过这个值。因此，网友们玩起了寻找比这更大的孩子的游戏。

而本文的目标是，通过一个程序逐个寻找那些“失踪的孩子”，并从已得到的孩子中中找出最大的孩子。

首先我们要讨论，如何处理巨大的数字。

由于n是指数，所以随着n的增大数字会增大地异常迅速，而不论是Python的乘方运算“**”还是math的“pow”函数，都无法处理较大结果的乘方。“**”会因此给出一个错误值，而“pow”则会报错。

同时，除法也同样不靠谱。除法会输出一个浮点数，而Python浮点数的整数部分是有大小限制的，超过一定大小也会报错。

这两点如何解决呢？

首先是乘方的解决。由于本程序所需的只有3的乘方，因此我们可以记录以3为底数的几个幂次的值（如：3¹，3²，3³……）在需要时调用。而如果遇到没有记录的幂次，可以从幂次库中取出一个较小的幂次，通过几次乘法运算（事实上在本程序中每次都只需乘一个3），得到更大在需要时调用。而如果遇到没有记录的幂次，可以从幂次库中取出一个较小的幂次，通过几次乘法运算（事实上在本程序中每次都只需乘一个3），得到更大的幂次，并在输出前将其记录下来。

当然，为方便考虑在本程序中我记录的是3ⁿ-1而不是3ⁿ。

本处的程序代码：

a={"3^1-1":2,"3^2-1":8}
def suan(x):
    global a
    try:
        return a["3^{}-1".format(x)]
    except:
        b=3*(suan(x-1)+1)-1
        a["3^{}-1".format(x)]=b
        return(b)