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

冬雪雪冬 · 发表于 2017-9-4 10:00:00

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2017-9-11 19:51 编辑

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

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

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

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

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

这里已经有了500余题。

登录/注册后可看大图

要求：

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

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

注重程序效率和创意。

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

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

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

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

登录/注册后可看大图

277

题目：
变种考拉兹序列

jerryxjr1220 · 发表于 2017-9-4 16:36:01

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

def collatz (n):
        s = ''
        while n > 1:
                if n % 3 == 0:
                        n //= 3
                        s += 'D'
                elif n % 3 == 1:
                        n = (4*n+2)//3
                        s += 'U'
                else:
                        n = (2*n-1)//3
                        s += 'd'
        return s

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

def collatz (n):
        s = ''
        while n > 1:
                if n % 3 == 0:
                        n //= 3
                        s += 'D'
                elif n % 3 == 1:
                        n = (4*n+2)//3
                        s += 'U'
                else:
                        n = (2*n-1)//3
                        s += 'd'
        return s

s = 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'
n = 2 #开始
i = 1 #字符串位数
d = 1 #公差
while collatz(n)[:30] != s[:30]:
        while True:
                if collatz(n)[:i] == s[:i]:
                        n1 = n #序列第一个
                        break
                n += d
        n += d
        while True:
                if collatz(n)[:i] == s[:i]:
                        n2 = n #序列第二个
                        break
                n += d
        d = n2 - n1 #公差
        i += 1
while n < 10**15:
        n += d
print(n, collatz(n))

1125977393124310 UDDDUdddDDUDDddDdDddDDUDDdUUDdUDDUdUddDUdddDDUdUUddddDUUUDDUUDDUUdUUdDUDDUdDD

Noregret · 发表于 2017-9-4 22:09:48

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

小剑剑 · 发表于 2017-9-10 17:05:17

def eulid(a,b,gcd=1):
    li1=[1,0,a]
    li2=[0,1,b]
    while li2[2]!=gcd:
        q=li1[2]//li2[2]
        templist=[li1[i]-li2[i]*q for i in range(3)]
        li1,li2=li2,templist
    return li2[0]%b

def f(string):
    if string[-1]=='d':
        b=1
        c=2
    elif string[-1]=='U':
        b=-2
        c=4
    else:
        b=0
        c=1
    a=3
    for i in range(-2,-1*len(string)-1,-1):
        a*=3
        b*=3
        if string[i]=='d':
            b+=c
            c*=2
        elif string[i]=='U':
            b-=2*c
            c*=4
    t=eulid(a,c)*-1*b%c
    while (t*a+b)//c<10**15:
        t+=c
    return (t*a+b)//c
print(f('UDDDUdddDDUDDddDdDddDDUDDdUUDd'))

1125977393124310

chunchun2017 · 发表于 2017-9-10 22:16:18

本帖最后由 chunchun2017 于 2017-9-11 15:19 编辑

答案是：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的第一个数了。
==============================================
下面是代码：

str0 = 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'
str1 = 'UDDDUdddDD'
len0 = len(str1)
step = 3**len0
N = 51232
while(1e15>N>=51232): #求出以str0开头的最小数
   N+=step
   num0=N
   str2=''
   while(len(str2)<len0+1):
     if(num0%3==0):
        str2+='D'
        num0//=3
     elif(num0%3==1):
        str2+='U'
        num0=(4*num0+2)//3
     elif(num0%3==2):
        str2+='d'
        num0=(2*num0-1)//3
   if(str2==str0[0:len0+1]):
     len0+=1
     step=3**len0
     #print(len0,N)
   if(len0==30):
     break
while(N<=1e15): #求出以str0开头并且大于10**15的最小值
     N+=3**30
print(N)

gunjang · 发表于 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')

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20170904 变种考拉兹序列

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分