|
发表于 2017-9-11 14:36:48
|
显示全部楼层
本帖最后由 gunjang 于 2017-9-11 17:09 编辑
通过分析,发现每个Collatz的输入和输出都有规律性,都是等差数列
将长度30的序列分成三部分
最后求出答案 1125977393124310
- #D an = 3*an1 when mod 3 == 0
- #U an = (3*an1-2)//4 when mod 3 == 1
- #d an = (3*an1+1)//2 when mod 3 == 2
- import time
- sequence1 = 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'
- def tryCollatz(start, clist, step=1):
- n = start;
- while True:
- flag = False
- a = n
- for c in clist:
- if c == 'D':
- if n%3 != 0:
- flag = True
- break
- n //= 3
- elif c=='U':
- if n%3 != 1:
- flag = True
- break
- n = (n*4+2)//3
- else:
- if n%3 != 2:
- flag = True
- break
- n = (n*2-1)//3
- if not flag:
- return a, n
- n = a+step
- def processCollatz(start, clist):
- n = start
- for c in clist:
- if c == 'D':
- if n%3 != 0:
- return -1
- n //= 3
- elif c=='U':
- if n%3 != 1:
- return -1
- n = (n*4+2)//3
- else:
- if n%3 != 2:
- return -1
- n = (n*2-1)//3
- return n
- st = time.time()
- now = 2
- step = 1
- input1, output1 = tryCollatz(now+1, sequence1[:10], step) #length is 30, 51232 111,setp is 3^10, 128
- now = input1+step
- input1_2, output1_2 = tryCollatz(now+1, sequence1[:10], step) #length is 30, 51232 111,setp is 3^10, 128
- step1 = input1_2 - input1
- outstep1 = output1_2 - output1
- print('First 10 Sequence: ', input1, step1)
- print('output: ', output1, outstep1)
- now = output1
- step = outstep1
- input2, output2 = tryCollatz(now, sequence1[10:20], step) #length is 30, middle 10 op:1228783 2663 8787055 19047,setp is 7558272, 16384
- now = input2+step
- input2_2, output2_2 = tryCollatz(now, sequence1[10:20], step) #length is 30, middle 10 op:1228783 2663 8787055 19047,setp is 7558272, 16384
- step2 = input2_2 - input2
- outstep2 = output2_2 - output2
- print('Middle 10 Sequence: ', input2, step2)
- print('output: ', output2, outstep2)
- now = output2
- step = outstep2
- input3, output3 = tryCollatz(now+step, sequence1[20:], step) #length is 30, last 10 op:453544551 1966289;1421003367 6160593,setp is 967458816, 16384
- now = input3+step
- input3_2, output3_2 = tryCollatz(now, sequence1[20:], step) #length is 30, middle 10 op:1228783 2663 8787055 19047,setp is 7558272, 16384
- step3 = input3_2 - input3
- outstep3 = output3_2 - output3
- print('Last 10 Sequence: ', input3, step3)
- print('output: ', output3, outstep3)
- '''
- input3, output3 = 453544551, 1966289
- step3, outstep3 = 967458816, 16384
- input2, output2 = 1228783, 2663
- step2, outsetp2 = 7558272, 16384
- input1, output1 = 51232, 111
- step1, outstep1 = 59049, 128
- '''
- realinput2 = (input3 - output2)//outstep2 * step2 + input2
- realinput1 = (realinput2 - output1)//outstep1 * step1 + input1 #96521732651065
- rinput21 = (input3 + step3 - output2)//outstep2 * step2 + input2
- rinput11 = (rinput21 - output1)//outstep1 * step1 + input1
- realstep1 = rinput11 - realinput1 #205891132094649
- print('First input & output:', realinput1, processCollatz(realinput1, sequence1))
- x = int((10**15 - realinput1)/realstep1) + 1 # a0+x*step > 10^15
- a1 = realinput1 + x * realstep1 #1125977393124310
- print('the smallest a1 > 1015 is',a1) #1125977393124310 22937809
- print('cost',time.time()-st,'s')
复制代码 |
评分
-
查看全部评分
|