卡拉兹(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时程序停止，下面我们用代码来实现下。

# _*_ 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：

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

参考资料：

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