题目14：找出以100万以下的数字开始的最长序列

欧拉计划

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

题目：

以下迭代序列定义在整数集合上：

n → n/2 (当 n 是偶数时)
n → 3n + 1 (当 n 是奇数时)

应用以上规则，并且以数字 13 开始，我们得到以下序列：

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可以看出这个以 13 开始以 1 结束的序列包含 10 个项。虽然还没有被证明（Collatz 问题），但是人们认为在这个规则下，以任何数字开始都会以 1 结束。

以哪个不超过 100 万的数字开始，能给得到最长的序列？

注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。

翅膀团

#include <stdio.h>

int main(void)
{
    int a,n,i,num,l=0;
    for(n=1;n<=1000000;n++)
    {
        i = 1;
        a = n;
        while(a != 1)
        {
            if(a % 2)
            {
                a = 3 * a + 1;
                i++;
            }
            else
            {
                a = a / 2;
                i++;
            }
        }
    if(i > l)
    {
        num = n;
        l = i;
    }
    }
    printf("不超过 100 万的数字为%d",num);
}

如果有错误希望指出

huomqh

def g(n):
    if n%2==0:
        return n/2
    else:
        return 3*n+1
timesmax=0
nmax=0
for i in range(1,1000001):
    times=1
    n=i
    while n!=1:
        times+=1
        n=g(n)
    
    if times>timesmax:
        nmax=i
        timesmax=times
print(nmax,timesmax)

837799 525

飘飞的白杨

n = 0
a = 1
for i in range(1,1000001):
    m = 0
    j = i
    while j!=1:
        if j % 2 == 0:
            j //= 2
            m += 1
        else:
            j = 3 * j + 1
            m += 1
    if m > a :
        n = i
        a = m
print(n,a)

答案：837799 525

愤怒的大头菇

temp=1;list1 = []
def Collatz():
      global temp,list1
      while True:
            collatz = []
            temp += 1
            x = temp
            collatz.append(temp)
            if temp > 1000000:
                  break
            while x != 1:
                  if x > 1:
                        if x % 2:
                              x = x * 3 + 1
                              collatz.append(x)
                        if not x % 2:
                              x = x // 2
                              collatz.append(x)
                  
                  if x == 1:
                        list1.append(len(collatz))
      return list1
            
                        


if __name__ == '__main__':
      collatz = Collatz()
      collatz.sort()
      print(collatz[-1])

先得到最长的有多少位
然后根据得到的数在collatz中用index

迷雾少年

inline int how(unsigned int g)
{
        int k = 1;
        unsigned int n = g;
        while ( n && n!=1)
        {
                if ( 0==n%2 )
                {
                        n=n/2;
                }else
                {
                        n=3*n+1;
                }
                k++;
        }
        return k;
}
int main()
{
        int maxValue = 0,n;
        int max;
        for ( n = 0;n<=1000000;n++)
        {
                int k =  how (n);
        //        std::cout<<n<<"="<<k<<std::endl;
                if( maxValue < k )
                {
                        maxValue = k;
                        max = n;
                }
        }
        std::cout<<maxValue<<" "<<max;
}

和上面的一样

jerryxjr1220

837799 525
[Finished in 64.2s]

def rule(num):
        if num == 1:
                output = 0
        elif num % 2:
                output = num * 3 + 1
        else:
                output = num /2
        return output

def calc(num):
        op = num
        cal = 0
        while op > 0:
                op = rule(op)
                cal += 1
        return cal

maxi = 0
maxn = 0
for i in range(1,1000000):
        if maxi < calc(i):
                maxi = calc(i)
                maxn = i
print (maxn, maxi)

时间有点长，感觉算法应该能再优化一下。

jerryxjr1220

换了一种标记法，时间缩短很多
837799
[Finished in 15.6s]

def rule(num):
        if num == 1:
                output = 0
        elif num % 2:
                output = num * 3 + 1
        else:
                output = num /2
        return output

calc = [None]*3000001
def calf(num):
        for c in range(1,num+1):
                if c>1 and calc[rule(c)] != None:
                        calc[c] = calc[rule(c)] + 1
                else:
                        op,cal = c,0
                        while op > 1:
                                op = rule(op)
                                cal += 1
                        calc[c] = cal
                if c == 1: calc[c] = 0
        return calc[num]

calf(1000000)
print calc.index(max(calc[:1000000]))

776667

def euler(x):
    lenght = 0
    result = 0
    for i in range(1,x+1):
        list_j = []
        j = i
        while j != 1:
            if j%2:
                j = j*3+1
            else:
                j /= 2
            list_j.append(j)
        if len(list_j) > lenght:
            lenght = len(list_j)
            result = i
    return result

if __name__ == '__main__':
    print(euler(1000000))

愤怒的大头菇

temp = 1;
list1 = []
while True:
    collatz=[]
    temp += 1
    x= temp
    collatz.append(temp)
    if temp >= 1000000:
        break
    while x != 1:
        if x > 1:
            if x %2:
                x = x * 3 + 1
                collatz.append(x)
            if not x % 2:
                x = x//2
                collatz.append(x)
    list1.append(len(collatz))
   
list2 = list1[:]
list1.sort()
print(list2.index(list1[-1])+2)

答案：837799

lyciam

endnum = 1000000
def goto1(now = 13): #规则序列生成器
    if now>=1:
        yield now
    elif now<1:
        raise StopIteration('Wrong Number')
    while now!=1:
        if now%2==0:
            now = int(now/2)
        else:
            now = 3*now+1
        yield now

# {0 : None} 结果字典{ 开始数:结果生成器 } :
resdic = {snum : goto1(snum) for snum in range(1,endnum+1)}

temp = [0,[]]
for key in resdic:
        lis = list(resdic[key])
        if temp[0]<len(lis):
                temp = [len(lis),lis]

print( 'startnumber:{}   length:{}   time:{}'.format(temp[1][0],temp[0],time.clock()-t) )

startnumber:837799   length:525   time:37.26619450396688

芒果加黄桃

# encoding:utf-8
# Collatz问题
from time import time

def euler014(N):
    tmp = N
    count = 1
    while tmp > 1:
        count += 1
        if tmp % 2 == 0:
            tmp = int(tmp / 2)
        else:
            tmp = tmp * 3 + 1
    return count

def euler014_next(num, l_result):
    N = len(l_result)
    t = num * 2
    while t < N and l_result[t] == None:
        l_result[t] = int(l_result[int(t / 2)]) + 1
        t *= 2
    t = num
    if t % 2 != 0 and t * 3 + 1 < N and l_result[t * 3 + 1] == None:
        t = t * 3 + 1
        l_result[t] = l_result[num] - 1
        t *=2
        while t < N and l_result[t] == None:
            l_result[t] = int(l_result[int(t / 2)]) + 1
            t *= 2
            
if __name__ == '__main__':
    start = time()
    N = 1000000
    l_result = [None] * (N + 1)
    l_result[0],l_result[1] = 0,1
    for i in range(2, N + 1):
        if l_result[i] == None:
            l_result[i] = euler014(i)
            euler014_next(i, l_result)
    print(max(l_result),'--',l_result.index(max(l_result)))
    print('cost %.3f sec' % (time() - start))

渡风

此代码使用MATLAB编程
Problem14所用时间7.4436秒
Problem14的答案为837799

%问题14：：找出以100万以下的数字开始的最长序列
%细节标记法
function Output=Problem14(Input)
if nargin==0
Input=1000000;
end
Rank=Input:-1:2;
Nmax=0;%储存最大是数
Lmax=0;%储存最大长度
N=0;%临时数
L=0;%临时长度
Flag=zeros(1,Input-1);
for ii=1:Input-1
    if Flag(ii)==0%假设没有被标记，则选择
        Temp=Rank(ii);
        N=Rank(ii);
        Flag(ii)=1;%选择之后标记
    else 
        continue
    end
    while (Temp>1)
        if mod(Temp,2)==0
            Temp=Temp/2;
        else
            Temp=Temp*3+1;
        end
        if Temp<Input
        Flag(Input-Temp)=1;%迭代的路上标记
        end
        L=L+1;
    end
     if L>Lmax;
         Lmax=L;
         Nmax=N;
     end
     L=0;
end
Output=Nmax;
toc  
disp('此代码使用MATLAB编程')
disp(['Problem14所用时间',num2str(toc),'秒'])
disp(['Problem14的答案为',num2str(Output)])
end

FlySelf

import time

def collatz_sequence(number):
    '求number以下的，能得到最长的序列的数字'
    list_sequence = [0, 1, 2]#存储以列表下标开始的序列长度，list_sequence[0]用于存储最长序列的下标
    for i in range(3, number):
        count = 0
        n = i
        while n != 1:
            if n < len(list_sequence):
                count += list_sequence[n]
                break
            if n % 2 == 0:
                n = int(n / 2)
            else:
                n = 3 * n + 1
            count += 1
        list_sequence.append(count)
        if list_sequence[list_sequence[0]] < count:
            list_sequence[0] = i
    return [list_sequence[0], list_sequence[list_sequence[0]]]

start = time.clock()
print(collatz_sequence(1000000))
end = time.clock()
print('程序执行了%fs。' %(end - start))

执行结果：
[837799, 525]
程序执行了3.018928s。

99592938

def chain(x):
    if x%2:x=3*x+1
    else:x=x/2
    return x
import time
stime = time.clock()
max1=0
dict1={}
for i in range(2,1000000):
    temp=i
    count=0
    while i!=1:
        if i in dict1:
            dict1[temp]=dict1[i]+count
            break
        else:
            i=chain(i)
            count+=1
    if not(temp in dict1):dict1[temp]=count
    if max1<dict1[temp]+1:
        max1=dict1[temp]+1
        num=temp
print('The start number is %d,the longest chain is %d' %(num,max1))
etime= time.clock()
print('read:%.3f s' %(etime-stime))

>>>
The start number is 837799,the longest chain is 525
read:9.211 s
加了字典优化后，效率提升很高。
优化前要跑130多秒。
然而感觉还能优化，但我已力不从心。

JonTargaryen

FlySelf 发表于 2017-2-7 11:24
执行结果：
[837799, 525]
程序执行了3.018928s。

你这个好棒！手动点赞！C语言秒出结果。

#include <stdio.h>

#define MAX 1000000

int main()
{
    int num;
    long a;
    int length, max = 0, result;
    int record[MAX];

    record[0] = 0;
    record[1] = 1;
    record[2] = 2;

    for(num = 3; num < MAX; num++)
    {
        a = num;
        length = 0;

        while(a != 1)
        {
            if(a < num)
            {
                length += record[a];
                break;
            }
            if(a % 2)
            {
                a = 3 * a + 1;
            }
            else
            {
                a /= 2;
            }
            length++;
        }
        record[num] = length;

        if(length > max)
        {
            max = length;
            result = num;
        }
    }

    printf("%d-->%d\n", result, max);

    return 0;
 }

JonTargaryen

JonTargaryen 发表于 2017-4-2 18:52
你这个好棒！手动点赞！C语言秒出结果。

def main():
    record = [0, 1, 2]
    max_length = 0

    for num in range(3, 1000000):
        a = num
        length = 0

        while(a != 1):
            if a < num:
                length += record[a]
                break

            if(a % 2):
                a = 3 * a + 1
            else:
                a //= 2

            length += 1

        record.append(length)

        if length > max_length:
            max_length = length
            result = num

    print("%d-->%d" % (result, max_length))

if __name__ == "__main__":
    main()

天之南

#include<stdio.h>

long long collatz_len(long long);
int main()
{
        long long max_len = 0;
        long long num = 1;
        for (long long i = 1;i < 1000000;i++) {
                if (max_len < collatz_len(i))
                {
                        max_len = collatz_len(i);
                        num = i;
                }
        }
        printf("%lld:%lld\n", num, max_len);
        return 0;
}

long long collatz_len(long long x)
{
        long long count = 1;
        while (x > 1)
        {
                if (x % 2 == 0) {
                        x /= 2;
                }
                else {
                        x = x * 3 + 1;
                }
                count++;
        }
        return count;
}

py阿碗

FlySelf 发表于 2017-2-7 11:24
执行结果：
[837799, 525]
程序执行了3.018928s。

自己想出来的和4楼一样，还是你这个快，

 if n < len(list_sequence):
                count += list_sequence[n]

这真没想到，还把空闲的list_sequence[0]利用起来，感觉很老练

BngThea

maxlen,maxi = 0,0
for i in range(1,int(1e6)):
    count = 1
    n = int(i/2 if not i%2 else 3*i+1)
    while (n != 1):
        count += 1
        n = int(n/2 if not n%2 else 3*n+1)
    if maxlen < count:
        maxlen = count
        maxi = i
    

print('{0} can produce the longest chain of {1}'.format(maxi, maxlen))