小练习：20170904 变种考拉兹序列

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。

什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives

这里已经有了500余题。

                               
登录/注册后可看大图

要求：

以python语言完成，如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成，即9.4 10：00之前，其后将公开大家的答案，并评比成绩。

另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

-- 回帖需写明解题思路，鼓励在程序中加上注释 --

-- 一些鱼油反映题目有些过难，为此略过一部分偏难的题目 --

                               
登录/注册后可看大图

277

题目：
变种考拉兹序列

jerryxjr1220

这题我好像有点投机取巧了，先来说下我“投机取巧”的思路...找规律...
我先写了一个考拉兹函数，来观察前100个数的规律。

1. def collatz (n):
   
2.         s = ''
   
3.         while n > 1:
   
4.                 if n % 3 == 0:
   
5.                         n //= 3
   
6.                         s += 'D'
   
7.                 elif n % 3 == 1:
   
8.                         n = (4*n+2)//3
   
9.                         s += 'U'
   
10.                 else:
    
11.                         n = (2*n-1)//3
    
12.                         s += 'd'
    
13.         return s

复制代码

然后发现，所有以‘U’开头的数都是4,7,10,13,16...这样的等差数列；
而以'UD'开头的数都是4,13,22,31...这样的等差数列；
以'UDD'开头的数都是13,40,67,94...这样的等差数列；
可以发现只要增加一个字符串，等差数列的公差就会以倍数的形式增加，发现规律以后程序就很简单了。

1. def collatz (n):
   
2.         s = ''
   
3.         while n > 1:
   
4.                 if n % 3 == 0:
   
5.                         n //= 3
   
6.                         s += 'D'
   
7.                 elif n % 3 == 1:
   
8.                         n = (4*n+2)//3
   
9.                         s += 'U'
   
10.                 else:
    
11.                         n = (2*n-1)//3
    
12.                         s += 'd'
    
13.         return s
    
14. 
    
15. s = 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'
    
16. n = 2 #开始
    
17. i = 1 #字符串位数
    
18. d = 1 #公差
    
19. while collatz(n)[:30] != s[:30]:
    
20.         while True:
    
21.                 if collatz(n)[:i] == s[:i]:
    
22.                         n1 = n #序列第一个
    
23.                         break
    
24.                 n += d
    
25.         n += d
    
26.         while True:
    
27.                 if collatz(n)[:i] == s[:i]:
    
28.                         n2 = n #序列第二个
    
29.                         break
    
30.                 n += d
    
31.         d = n2 - n1 #公差
    
32.         i += 1
    
33. while n < 10**15:
    
34.         n += d
    
35. print(n, collatz(n))

复制代码

1125977393124310 UDDDUdddDDUDDddDdDddDDUDDdUUDdUDDUdUddDUdddDDUdUUddddDUUUDDUUDDUUdUUdDUDDUdDD

Noregret

start = 'U D D D U d d d D D U D D d d D d D d d D D U D D d U U D d'
quip = start.split(' ')
x = 1000000000000000
while True:
    n = x
    for each in quip:
        if round(n) == n:
            if each == 'D':
                n /= 3
            elif each == 'U':
                n = (4 * n + 2) / 3
            elif each == 'd':
                n = (2 * n - 1) / 3
        else:
            break
        
    if round(n) == n:        
        while round(n) ==n:
            if n == 1:
                print(x)
                break
            if n % 3 == 0:
                n /= 3
            elif n % 3 == 1:
                n = (4 * n + 2) / 3
            elif n % 3 == 2:
                n = (2 * n - 1) / 3

    x +=1

小剑剑

1. def eulid(a,b,gcd=1):
   
2.     li1=[1,0,a]
   
3.     li2=[0,1,b]
   
4.     while li2[2]!=gcd:
   
5.         q=li1[2]//li2[2]
   
6.         templist=[li1[i]-li2[i]*q for i in range(3)]
   
7.         li1,li2=li2,templist
   
8.     return li2[0]%b
   
9. 
   
10. def f(string):
    
11.     if string[-1]=='d':
    
12.         b=1
    
13.         c=2
    
14.     elif string[-1]=='U':
    
15.         b=-2
    
16.         c=4
    
17.     else:
    
18.         b=0
    
19.         c=1
    
20.     a=3
    
21.     for i in range(-2,-1*len(string)-1,-1):
    
22.         a*=3
    
23.         b*=3
    
24.         if string[i]=='d':
    
25.             b+=c
    
26.             c*=2
    
27.         elif string[i]=='U':
    
28.             b-=2*c
    
29.             c*=4
    
30.     t=eulid(a,c)*-1*b%c
    
31.     while (t*a+b)//c<10**15:
    
32.         t+=c
    
33.     return (t*a+b)//c
    
34. print(f('UDDDUdddDDUDDddDdDddDDUDDdUUDd'))

复制代码

1125977393124310

chunchun2017

答案是：1125977393124310


直到上周末才分析出规律，到今天早上才算出来，不管对不对，这个过程真的是很考验人！！！不管对不对，自己都很激动！
以UDD开头的数如下：这些数是一个等差数列，间隔是27=(3**3)
13 UDDd
40 UDDDd
67 UDDUdDD

以UDDD开头的数如下，这些数是一个等差数列，间隔是81= 3**4
40 UDDDd
121 UDDDDd
202 UDDDUdDD

以UDDDU开头的数如下，这些数是一个等差数列，间隔是243=3**5
202 UDDDUdDD
445 UDDDUDUdDD
688 UDDDUUddDDD

观察可以得出两个规律：
1）以相同字符串(假设这个字符串长度为n0)开头的数，从小到大排列起来是一个等差数列，公差为3**n0 (上面也说明了）
2）以UDDDUdddD***开头的数字，一定是在以UDDDUdddD开头的数字的递增序列中，当然也会在以UDDDUdddD开头，以UDDDU开头的递增系列中，
再看要求的问题，要求出以UDDDUdddDDUDDddDdDddDDUDDdUUDd开头，且大于10**15的最小数，需要先找出以UDDDUdddDDUDDddDdDddDDUDDdUUDd开头的最小值（当然也不一定非要找最小值，只要找其中一个小于10**15的就可以了），然后按照3**30的递增顺序，找到第一个大于10**15的数，就是答案

关键在于求以UDDDUdddDDUDDddDdDddDDUDDdUUDd开头的最小值，不知道是不是我太笨了，这个求解过程我花了好几天时间想办法，直接枚举没算出来，还是要从等差数列做文章，前面观察的时候已经计算了一些值，这里就直接拿来用：
以UDDDUdddDD开头的最小值是51232，以公差3**9递增，找到第一个以UDDDUdddDDU开头的最小值后，公差变成3**10，依此类推，当公差变为3**30时，说明已经找到了以UDDDUdddDDUDDddDdDddDDUDDdUUDd开头的值，这时求出的值是小于10**15的，然后以3**30的公差递增，就能找到大于10**15的第一个数了。
==============================================
下面是代码：

1. str0 = 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'
   
2. str1 = 'UDDDUdddDD'
   
3. len0 = len(str1)
   
4. step = 3**len0
   
5. N = 51232
   
6. while(1e15>N>=51232): #求出以str0开头的最小数
   
7.    N+=step
   
8.    num0=N
   
9.    str2=''
   
10.    while(len(str2)<len0+1):
    
11.      if(num0%3==0):
    
12.         str2+='D'
    
13.         num0//=3
    
14.      elif(num0%3==1):
    
15.         str2+='U'
    
16.         num0=(4*num0+2)//3
    
17.      elif(num0%3==2):
    
18.         str2+='d'
    
19.         num0=(2*num0-1)//3
    
20.    if(str2==str0[0:len0+1]):
    
21.      len0+=1
    
22.      step=3**len0
    
23.      #print(len0,N)
    
24.    if(len0==30):
    
25.      break
    
26. while(N<=1e15): #求出以str0开头并且大于10**15的最小值
    
27.      N+=3**30
    
28. print(N)
    
29. 
    
30.       

复制代码

gunjang

通过分析，发现每个Collatz的输入和输出都有规律性，都是等差数列
将长度30的序列分成三部分
最后求出答案 1125977393124310

1. #D an = 3*an1  when mod 3 == 0
   
2. #U an = (3*an1-2)//4  when mod 3 == 1
   
3. #d an = (3*an1+1)//2  when mod 3 == 2
   
4. import time
   
5. 
   
6. sequence1  = 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'
   
7. 
   
8. def tryCollatz(start, clist, step=1):
   
9.         n = start;
   
10.         while True:
    
11.                 flag = False
    
12.                 a = n
    
13.                 for c in clist:
    
14.                         if c == 'D':
    
15.                                 if n%3 != 0:
    
16.                                         flag = True
    
17.                                         break
    
18.                                 n //= 3
    
19.                         elif c=='U':
    
20.                                 if n%3 != 1:
    
21.                                         flag = True
    
22.                                         break
    
23.                                 n = (n*4+2)//3
    
24.                         else:
    
25.                                 if n%3 != 2:
    
26.                                         flag = True
    
27.                                         break
    
28.                                 n = (n*2-1)//3
    
29.                 if not flag:
    
30.                         return a, n
    
31.                 n = a+step
    
32. 
    
33. def processCollatz(start, clist):
    
34.         n = start
    
35.         for c in clist:
    
36.                 if c == 'D':
    
37.                         if n%3 != 0:
    
38.                                 return -1
    
39.                         n //= 3
    
40.                 elif c=='U':
    
41.                         if n%3 != 1:
    
42.                                 return -1
    
43.                         n = (n*4+2)//3
    
44.                 else:
    
45.                         if n%3 != 2:
    
46.                                 return -1
    
47.                         n = (n*2-1)//3
    
48.         return n
    
49. 
    
50. st = time.time()
    
51. 
    
52. now = 2
    
53. step = 1
    
54. input1, output1 = tryCollatz(now+1, sequence1[:10], step) #length is 30, 51232 111,setp is 3^10, 128
    
55. now = input1+step
    
56. input1_2, output1_2 = tryCollatz(now+1, sequence1[:10], step) #length is 30, 51232 111,setp is 3^10, 128
    
57. step1 = input1_2 - input1
    
58. outstep1 = output1_2 - output1
    
59. print('First 10 Sequence: ', input1, step1)
    
60. print('output: ', output1, outstep1)
    
61. 
    
62. now = output1
    
63. step = outstep1
    
64. input2, output2 = tryCollatz(now, sequence1[10:20], step) #length is 30, middle 10 op:1228783 2663 8787055 19047,setp is 7558272, 16384
    
65. now = input2+step
    
66. input2_2, output2_2 = tryCollatz(now, sequence1[10:20], step) #length is 30, middle 10 op:1228783 2663 8787055 19047,setp is 7558272, 16384
    
67. step2 = input2_2 - input2
    
68. outstep2 = output2_2 - output2
    
69. print('Middle 10 Sequence: ', input2, step2)
    
70. print('output: ', output2, outstep2)
    
71. 
    
72. 
    
73. now = output2
    
74. step = outstep2
    
75. input3, output3 = tryCollatz(now+step, sequence1[20:], step) #length is 30, last 10 op:453544551 1966289;1421003367 6160593,setp is 967458816, 16384
    
76. now = input3+step
    
77. input3_2, output3_2 = tryCollatz(now, sequence1[20:], step) #length is 30, middle 10 op:1228783 2663 8787055 19047,setp is 7558272, 16384
    
78. step3 = input3_2 - input3
    
79. outstep3 = output3_2 - output3
    
80. print('Last 10 Sequence: ', input3, step3)
    
81. print('output: ', output3, outstep3)
    
82. 
    
83. '''
    
84. input3, output3 = 453544551, 1966289
    
85. step3, outstep3 = 967458816, 16384
    
86. input2, output2 = 1228783, 2663
    
87. step2, outsetp2 = 7558272, 16384
    
88. input1, output1 = 51232, 111
    
89. step1, outstep1 = 59049, 128
    
90. '''
    
91. 
    
92. realinput2 = (input3 - output2)//outstep2 * step2 + input2
    
93. realinput1 = (realinput2 - output1)//outstep1 * step1 + input1 #96521732651065
    
94. 
    
95. rinput21 = (input3 + step3 - output2)//outstep2 * step2 + input2
    
96. rinput11 = (rinput21 - output1)//outstep1 * step1 + input1
    
97. realstep1 = rinput11 - realinput1 #205891132094649
    
98. 
    
99. print('First input & output:', realinput1, processCollatz(realinput1, sequence1))
    
100. 
     
101. x = int((10**15 - realinput1)/realstep1) + 1 # a0+x*step > 10^15
     
102. a1 = realinput1 + x * realstep1 #1125977393124310
     
103. print('the smallest a1 > 1015 is',a1) #1125977393124310 22937809
     
104. print('cost',time.time()-st,'s')

复制代码