Fork me on GitHub

卡拉兹(Callatz)猜想(3n+1)Python实现

前段时间在另一个博客中了解到了这个卡拉兹猜想,感觉有点意思,于是用想着用python实现看看。

卡拉兹(Callatz)猜想:对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。

卡拉兹在1950年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员,拼命想证明这个貌似很傻很天真的命题,结果闹得学生们无心学业,一心只证(3n+1),以至于有人说这是一个阴谋,卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

上述是这个猜想的故事背景,要实现这个猜想,就需要理解这个猜想。从字面意思来看,就是给定一个自然数,然后进行数学计算,如果是偶数,那么就直接砍掉一半,用数学公式来表达就是,设一个自然数n,当n为偶数时:n = n / 2;当n为奇数时:n = (3*n+1) / 2 ;然后按照这个逻辑一直往下执行,执行到n=1时候为止,也就是说一定会有一个n = 1的时刻,当n = 1时程序停止,下面我们用代码来实现下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# _*_ coding:utf-8 _*_

def main():
n = int(input(">>>请输入一个自然数n:")) # 构造一个自然数n
i = 0 # 计数器,保存步数,初始化为0
len_n = []

while n != 1:
print("-" * 20)
print(f"现在n的值为{int(n)}")
len_n.append(int(n))
print(f"len_n的长度为{len(len_n)}")
print(f"len_n的值为{len_n}")

# 通过%来进行整除,余数为0则说明能够整除
if n % 2 == 0:
print(f"n % 2的值为{int(n % 2)},当前n为偶数")
n = n / 2

else:
print(f"当前n为奇数,所以执行了3n+1:{int((3 * n + 1) / 2)}")
n = (3 * n + 1) / 2

i = i + 1

print("-" * 20)
print(f"共{i}步")

if __name__ == "__main__":
main()

可以看出,我们通过input函数输入一个自然数,然后转化为整数,然后开始循环,加入我输入的值为10,我们先通过口算下几步可以得到n = 1。

  • n = 10:偶数,n = 10 / 2 = 5;
  • n = 5:奇数,n = (3 * 5 + 1) / 2 = 8;
  • n = 8:偶数,n = 8 / 2 = 4;
  • n = 4:偶数,n = 4 / 2 = 2;
  • n = 2:偶数, n = 2 / 2 = 1;
  • n = 1

通过上面的口算我们可以得出,我们只需要5步就可以计算出n = 1了,从而也就证明了卡拉兹的猜想。

下面执行下python脚本,我们设定一个自然数:20000,看需要多少步实现n = 1:

Fb5TXT.md.png

通过计算得出,只需要24步,我们可将自然数20000实现成n = 1;

参考资料:

1001 害死人不偿命的(3n+1)猜想 (15)(15 分)(PAT:C与Python)