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

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

目前累计服务客户近1000家,积累了丰富的产品开发及服务经验。以网站设计水平和技术实力,树立企业形象,为客户提供成都做网站、网站设计、外贸营销网站建设、网站策划、网页设计、网络营销、VI设计、网站改版、漏洞修补等服务。创新互联建站始终以务实、诚信为根本,不断创新和提高建站品质,通过对领先技术的掌握、对创意设计的研究、对客户形象的视觉传递、对应用系统的结合,为客户提供更好的一站式互联网解决方案,携手广大客户,共同发展进步。

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

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

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

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

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

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

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

  • 任意一个不是2的幂次的正整数,经过若干次变换以后都会变为一个可以表示为3n-1(n∈N+[注:为防止有未读过高中的读者,特在此说明:n∈N+意思是n是正整数]的形式的数;
  • 任意一个不是8(32-1)的能表示为3n-1(n∈N+)形式的数,在经过若干次变化后都会变为另一个这样的数;
  • 经过若干次第二条的变化后,3n-1最终会变为32-1,然后经过除以2的变化陷入4-2-1的循环;

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

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

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

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

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

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

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

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

这两点如何解决呢?

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

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

本处的程序代码:

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)

当前文章:趣味问题《寻人启事》的Python程序解决
地址分享:http://scyanting.com/article/dsogipi.html