题目14：找出以100万以下的数字开始的最长序列
Longest Collatz sequenceThe 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-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);
}
如果有错误希望指出 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;
}
和上面的一样 837799 525
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)
时间有点长，感觉算法应该能再优化一下。 换了一种标记法，时间缩短很多
837799
def rule(num):
if num == 1:
output = 0
elif num % 2:
output = num * 3 + 1
else:
output = num /2
return output
calc = *3000001
def calf(num):
for c in range(1,num+1):
if c>1 and calc != None:
calc = calc + 1
else:
op,cal = c,0
while op > 1:
op = rule(op)
cal += 1
calc = cal
if c == 1: calc = 0
return calc
calf(1000000)
print calc.index(max(calc[:1000000])) 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 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 = ]
for key in resdic:
lis = list(resdic)
if temp<len(lis):
temp =
print( 'startnumber:{} length:{} time:{}'.format(temp,temp,time.clock()-t) )
startnumber:837799 length:525 time:37.26619450396688 本帖最后由 芒果加黄桃 于 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 == None:
l_result = int(l_result) + 1
t *= 2
t = num
if t % 2 != 0 and t * 3 + 1 < N and l_result == None:
t = t * 3 + 1
l_result = l_result - 1
t *=2
while t < N and l_result == None:
l_result = int(l_result) + 1
t *= 2
if __name__ == '__main__':
start = time()
N = 1000000
l_result = * (N + 1)
l_result,l_result = 0,1
for i in range(2, N + 1):
if l_result == None:
l_result = 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: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
import time
def collatz_sequence(number):
'求number以下的，能得到最长的序列的数字'
list_sequence = #存储以列表下标开始的序列长度，list_sequence用于存储最长序列的下标
for i in range(3, number):
count = 0
n = i
while n != 1:
if n < len(list_sequence):
count += list_sequence
break
if n % 2 == 0:
n = int(n / 2)
else:
n = 3 * n + 1
count += 1
list_sequence.append(count)
if list_sequence] < count:
list_sequence = i
return , list_sequence]]
start = time.clock()
print(collatz_sequence(1000000))
end = time.clock()
print('程序执行了%fs。' %(end - start))
执行结果：
程序执行了3.018928s。 本帖最后由 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=dict1+count
break
else:
i=chain(i)
count+=1
if not(temp in dict1):dict1=count
if max1<dict1+1:
max1=dict1+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 19:05 编辑
FlySelf 发表于 2017-2-7 11:24
执行结果：
程序执行了3.018928s。
你这个好棒！手动点赞！C语言秒出结果。
#include <stdio.h>
#define MAX 1000000
int main()
{
int num;
long a;
int length, max = 0, result;
int record;
record = 0;
record = 1;
record = 2;
for(num = 3; num < MAX; num++)
{
a = num;
length = 0;
while(a != 1)
{
if(a < num)
{
length += record;
break;
}
if(a % 2)
{
a = 3 * a + 1;
}
else
{
a /= 2;
}
length++;
}
record = length;
if(length > max)
{
max = length;
result = num;
}
}
printf("%d-->%d\n", result, max);
return 0;
} 本帖最后由 JonTargaryen 于 2017-4-2 19:04 编辑
JonTargaryen 发表于 2017-4-2 18:52
你这个好棒！手动点赞！C语言秒出结果。
def main():
record =
max_length = 0
for num in range(3, 1000000):
a = num
length = 0
while(a != 1):
if a < num:
length += record
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;
} FlySelf 发表于 2017-2-7 11:24
执行结果：
程序执行了3.018928s。
自己想出来的和4楼一样，还是你这个快，
if n < len(list_sequence):
count += list_sequence
这真没想到，还把空闲的list_sequence利用起来，感觉很老练
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))