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

欧拉计划 · 发表于 2015-4-21 16:24:26

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

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

x

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 万的。

翅膀团 · 发表于 2015-9-1 22:29:42

本帖最后由翅膀团于 2015-11-16 14:14 编辑

#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 · 发表于 2016-6-13 18:40:57

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

飘飞的白杨 · 发表于 2016-8-2 22:15:26

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

愤怒的大头菇 · 发表于 2016-8-24 21:16:14

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

迷雾少年 · 发表于 2016-8-28 10:11:28

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 · 发表于 2016-9-18 14:18:51

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 · 发表于 2016-10-11 13:02:51

换了一种标记法，时间缩短很多
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 · 发表于 2016-10-14 11:13:23

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))

复制代码

愤怒的大头菇 · 发表于 2016-11-16 11:33:34

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 · 发表于 2016-11-24 15:40:00

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

芒果加黄桃 · 发表于 2017-1-10 13:16:28

本帖最后由芒果加黄桃于 2017-1-10 13:18 编辑

# 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))

复制代码

渡风 · 发表于 2017-1-14 21:33:40

本帖最后由渡风于 2017-1-14 21:35 编辑

此代码使用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 · 发表于 2017-2-7 11:24:26

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 · 发表于 2017-3-14 21:49:19

本帖最后由 99592938 于 2017-3-14 21:52 编辑

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 · 发表于 2017-4-2 18:52:15

本帖最后由 JonTargaryen 于 2017-4-2 19:05 编辑

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 · 发表于 2017-4-2 19:01:50

本帖最后由 JonTargaryen 于 2017-4-2 19:04 编辑

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()

复制代码

天之南 · 发表于 2017-5-1 03:11:04

#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阿碗 · 发表于 2017-7-17 10:18:34

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

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

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

复制代码

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

BngThea · 发表于 2017-9-12 17:27:15

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))

复制代码

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

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

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

评分