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)

贵州体育彩票11选5