考拉兹猜想:
对自然数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以内是没有的。这个也确实有点神奇,由此间接地能略窥一点原始考拉兹猜想的神秘风采。