考拉兹猜想:
对自然数n执行如下操作:
+ 若n是偶数,用n除以2
+ 若n是奇数,用n乘以3后加1
如此循环操作的话,无论初始值是什么,最终都会得到1(会进入1-->4-->2-->1)的循环
考虑稍微修改一下以上迭代的规则。当初始状态是偶数的话,第一次也用n乘以3加1,其后迭代规则不变。
求在10000以内的偶数中总共有多少个数,经过以上修改的迭代规则能够回到初始状态的?
注意,由于原始考拉兹猜想是无论什么初始状态最后都将回到1,所以在改版考拉兹猜想中,无论初始值是什么最终也终将回到1.只不过有一些偶数会先回到初始状态然后再收敛到1.本题就是要找有多少这样的会回到初始状态的数。
这个题目实在没有什么好分析的。
循环迭代,不管是到达1还是回到初始状态都停止循环。到达1表明不是“会回到初始状态”的数,到达1之前先回到初始状态的数则是所寻找的对象。
- # -*- coding: utf-8 -*-
- """
- Created on Mon Aug 23 13:40:11 2021
-
- @author: chenxy
- """
-
- import sys
- import time
- import random
- from typing import List
- from queue import Queue
- from collections import deque
-
- class Solution:
- def numOfLoop(self, N: int) -> List:
- ans = []
-
- def modified_collatz(K):
- isFirst = True
- a = K
- while 1:
- if a%2 == 0:
- if isFirst:
- a = 3*a + 1
- isFirst = False
- else:
- a = a/2
- else:
- a = 3*a + 1
-
- if a == K:
- return True # Find one loop in modified collatz iteration
- if a == 1:
- return False # No loop found in modified collatz iteration
-
- for n in range(2,N,2):
- if modified_collatz(n):
- ans.append(n)
-
- return ans
-
- if __name__ == '__main__':
-
- sln = Solution()
-
- tStart = time.time()
- N = 1000000
- ans = sln.numOfLoop(N)
- tCost = time.time() - tStart
- print('N = {0}, numOfLoops = {1}, tCost = {2}(sec)'.format(N, len(ans), tCost))
运行结果如下:
N = 10000, numOfLoops = 34, tCost = 0.0997314453125(sec)
print(ans):[2, 4, 8, 10, 14, 16, 20, 22, 26, 40, 44, 52, 106, 184, 206, 244, 274, 322, 526, 650, 668, 790, 866, 976, 1154, 1300, 1438, 1732, 1780, 1822, 2308, 2734, 3238, 7288]
不过正如原书中所说的,虽然在10000以内就找到了34个数能回到初始状态,再加大搜索范围就再也没有了。笔者验证1,000,000以内是没有的。这个也确实有点神奇,由此间接地能略窥一点原始考拉兹猜想的神秘风采。