Python求解一个经典循环数列问题

用Python求解一个经典循环数列问题

1、问题描述：
这是某个QQ群的入群问题：初始条件a[0]=10111,递推方程a[n+1]=int(a[n]^2/10000)-17001.求a[10 ^15].

2、数学分析：
这个差分方程显然是一个整数数列，不难证明该整数数列有上下界，因此取值个数有限，故而它从某一项开始（不一定是a[0]就开始循环）后续是一个循环序列。因此要解决该问题就需要找到循环周期T，和初始循环项a[i]。如果不是10^15太大，完全可以直接循环找到取值。

3、Python代码如下。

a = 10111 #初始值
num = []
l =0
while True:
    l = l+1 #第一个
    num.append(a) #列表储存数列
    a = int(a ** 2 / 10000) - 17001 #递推关系
    if a in num:
        num.append(a) #如果发现a已经储存过了，则再储存并退出
        break
for i in range(l): #遍历l项之前的每一项
    if num[i] == num[l]: #两次储存值相等，第i项之前不循环，之后才是循环数列，周期为l-i
        print(num[(10**15-i)%(l-i)+i])

4、如果用list(set())去重，列表长度小于循环次数再break跳出，也能找到两次重复项后者索引为285，然后遍历之前每一项，找出前者的索引值，从而得到周期。

本文地址：https://blog.csdn.net/u012929136/article/details/107644107