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

阿bang

import time


start = time.time()
cntlist = []
for i in range(2, 1000000):
    numlist = [i]
    num = i
    while num != 1:
        if num % 2 == 0:
            num /= 2
        else:
            num = num * 3 + 1
        numlist.append(num)
        if num in numlist:

    cntlist.append(len(numlist))
print max(cntlist)
print time.time() - start

十分初级的版本。考虑优化点有2：

1、类似素数筛选法：已经算过的数的2的n次方倍数的数，计数直接+n，结束。
2、维护一个数的序列的表，如果出现某个数在列表内，则计数直接加上列表后面的长度，结束。

阿bang

(837799, 524)
2.58100008965

优化了一下，速度提高了不少。不过最后的字典里取结果可能慢了。还有优化的空间。代码如下：

import time


def longestCollatz(n=1000001):
    start = time.time()
    collatzdict = {}  #维护一个统一的collatz的统计字典，初始为[2：2]
    numlist = [True] * (n - 1) #默认所有数都未被‘挖掉’, 从2 开始
    for i in range(2, n):
        count = 0
        num = i
        if numlist[i - 2] == True: #若一个数未被挖掉，计算数量
            while num != 1:
                num = num * 3 + 1 if num % 2 else num / 2
                count += 1
                if num in collatzdict: #若计算到某个步骤，产生了已经出现过的数，则直接加上该数的计数，计数结束
                    count += collatzdict[num]
                    break
            collatzdict[i] = count
            numlist[i - 2] = False
            if i < n / 2:             #以i为基数，挖掉i的2的j次方倍的所有的数
                j = 1
                while i * pow(2, j) < n:
                    if numlist[i] == True:
                        numlist[i * pow(2, j) - 2] = False #挖掉第i个数2的j次方倍的数
                        collatzdict[i * pow(2, j)] = collatzdict[i] + j
                    j += 1
    print list(sorted(collatzdict.items(), key=lambda x:x[1], reverse=True))[0]
    print time.time() - start


if __name__ == '__main__':
    longestCollatz()

阿bang

阿bang 发表于 2018-4-4 12:43
优化了一下，速度提高了不少。不过最后的字典里取结果可能慢了。还有优化的空间。代码如下：

import time


def longestCollatz(n=1000001):
    start = time.time()
    collatzdict = {}  #维护一个统一的collatz的统计字典，初始为[2：2]
    numlist = [True] * (n - 1) #默认所有数都未被‘挖掉’, 从2 开始
    maxnum = 2
    maxcnt = 2
    for i in range(2, n):
        count = 0
        num = i
        if numlist[i - 2] == True: #若一个数未被挖掉，计算数量
            while num != 1:
                num = num * 3 + 1 if num % 2 else num / 2
                count += 1
                if num in collatzdict: #若计算到某个步骤，产生了已经出现过的数，则直接加上该数的计数，计数结束
                    count += collatzdict[num]
                    break
            collatzdict[i] = count
            if count > maxcnt:
                maxcnt = count
                maxnum = i
            numlist[i - 2] = False
            if i < n / 2:             #以i为基数，挖掉i的2的j次方倍的所有的数
                j = 1
                while i * pow(2, j) < n:
                    if numlist[i] == True:
                        numlist[i * pow(2, j) - 2] = False #挖掉第i个数2的j次方倍的数
                        collatzdict[i * pow(2, j)] = collatzdict[i] + j
                        if collatzdict[i * pow(2, j)] > maxcnt:
                            maxcnt = collatzdict[i * pow(2, j)]
                            maxnum = i * pow(2, j)
                    j += 1


    # print list(sorted(collatzdict.items(), key=lambda x:x[1], reverse=True))[0]
    print maxnum, maxcnt
    print time.time() - start


if __name__ == '__main__':
    longestCollatz()

再改了一下，只需要找最大的，不需要最后排序字典的话，会快一点

837799 524
1.69199991226

najin

The answer is 837799
Its length is 525
Time is 136 ms

jerry-R

0.80s在此哦~~~~
#include <iostream>
using namespace std;

int main()
{
        int longest = 0;
        int terms = 0;
        int i;
        unsigned long j;

        for (i = 1; i <= 1000000; i++)
        {
                j = i;
                int this_terms = 1;

                while (j != 1)
                {
                        this_terms++;

                        if (this_terms > terms)
                        {
                                terms = this_terms;
                                longest = i;
                        }

                        if (j % 2 == 0)
                        {
                                j = j / 2;
                        }
                        else
                        {
                                j = 3 * j + 1;
                        }
                }
        }

        cout << longest << endl << terms << endl;
        system("pause");
        return 0;
}

zzzgod

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
        bool dest[1000001];
        long long maxtime=0,maxnum=0,time,num;
        memset(dest,0,1000001);
        dest[1]=1;
        for(int i=1;i<=1000000;++i)
        {
                if(dest[i]==1)
                        continue;
                num=i;
                time=1;
                while(num!=1)
                {
                        ++time;
                        if(num<=1000000)
                                dest[num]=1;
                        if(num%2==0)
                        {
                                num/=2;
                        }
                        else
                        {
                                num=num*3+1;
                        }
                }
                if(time>maxtime)
                {
                        maxtime=time;
                        maxnum=i;
                }
        }
        cout<<"最长的序列数是："<<maxnum<<' '<<"总共有："<<maxtime<<"个元素"; 
}

不到1秒

山有扶苏啊

def Collatz(n):
    t = 0
    while n != 1:
        if n%2 == 0:
            n = n/2
            t += 1
        else:
            n = 3*n + 1
            t += 1
    return t

result = {}
for i in range(1, 1000000):
    result[i] = Collatz(i)

max(result, key = result.get)

837799

k往事如烟k

count1 = 1
num1 = 1
for n in range(1, 1000001):
    count = 1
    num = n
    while 1:
        if num % 2 == 0:
            num //= 2
            count += 1
        else:
            num = num * 3 + 1
            count += 1
        if num == 1:
            break
    if count >= count1:
        count1 = count
        num1 = n
print(num1)

837799

王小召

最大值：525
对应数值：837799
总用时：25.376614736835744

import time


def get_longer(num):
    if num <= 1000000:
        counter = 1
        while num != 1:
            if num % 2:
                num = num*3 + 1
            else:
                num = num/2
            counter += 1
        return counter
    else:
        raise ValueError

t1 = time.clock()
num_list = [get_longer(i) for i in range(2, 1000000)]
print("最大值：{} \n对应数值：{} \n总用时：{}".format(max(num_list), num_list.index(max(num_list))+2, time.clock() - t1))

cwhsmile

import time
import math
import functools

def test1():
    max_len = 0
    i = 1000001
    
    while i > 1:
        num = i
        count = 1
        while num != 1:
            if num%2 == 0:
                num = num//2
            else:
                num = 3*num + 1
            count += 1
        if max_len < count:
            max_len = count
            max_num = i
        i -= 2
    return max_len,max_num

start = time.perf_counter()

print(test1())
end = time.perf_counter()
print(end-start)

永恒的蓝色梦想

C++ 12ms

#include<iostream>

constexpr unsigned int MAX = 1000000;
unsigned short cache[MAX] = { 0, 1 };



unsigned short Collatz(unsigned int num)noexcept {
    if (num < MAX) {
        if (cache[num]) {
            return cache[num];
        }

        if (num & 1) {
            return cache[num] = Collatz((num >> 1) + num + 1) + 2;
        }

        return cache[num] = Collatz(num >> 1) + 1;
    }

    if (num & 1) {
        return Collatz((num >> 1) + num + 1) + 2;
    }

    return Collatz(num >> 1) + 1;
}



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    unsigned int num, max_num = 0;
    unsigned short len, max_len = 0;


    for (num = 1; num < MAX; num++) {
        if (!cache[num]) {
            if (num & 1) {
                len = Collatz((num >> 1) + num + 1) + 2;
            }
            else {
                len = Collatz(num >> 1) + 1;
            }

            if (len > max_len) {
                max_len = len;
                max_num = num;
            }
        }
    }


    cout << max_num << endl;
    return 0;
}

leon0149

525 837799
0.788s

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000
#define NUM 1000000

long long odd(long long);
long long even(long long);
void init(long long *);
void Insert(long long *, long long);

void init(long long* array){
    array[0] = 0;
}

void Insert(long long* array, long long e){
    if (array[0] == MAX)
        exit(EXIT_FAILURE);
    array[++array[0]] = e;
}

void execute(long long *array, long long e){
    long long temp = e;
    Insert(array, temp);
    while (temp != 1) {
        if (temp % 2 != 0) {
            temp = odd(temp);
            Insert(array, temp);
        }
        if (temp % 2 == 0) {
            temp = even(temp);
            Insert(array, temp);
        }
    }
}

long long odd(long long num){
    return 3 * num + 1;
}

long long even(long long num){
    return num / 2;
}

int main(void)
{
    int max = 0;
    int maxNum = 0;
    int temp;
    long long array[MAX] = {0};
    for (int i = NUM - 1; i > 1; i-=2) {
        init(array);
        execute(array, i);
        temp = (int)array[0];
        if (max < temp){
            maxNum = i;
            max = temp;
        }
    }

    printf("最大链长: %d, 数字: %d\n", max, maxNum);
    
    return 0;
}

数据小随从

#include<stdio.h>
#include<stdlib.h>


void main()
{
        int i, k;//定义一个整数变量，从1遍历到一百万
        int t;
        int n = 1;
        int max = 1;
        for (i = 2; i <= 5; i++)
        {
                t = i;
                n = 1;
                while (t != 1)
                {
                        if (t % 2 == 0)
                        {
                                t = t / 2;
                                n++;
                        }
                        else
                        {
                                t = (t * 3) + 1;
                                n++;
                        }
                        if (t == 1)
                                if (n > max)
                                {
                                        max = n;
                                        k = i;
                                }
                }
        }
        printf("%d,%d\n", max, k);



        system("pause");
}

有马_冬巳

'''以下迭代序列定义在整数集合上：
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 万的。'''

def longestsequence(num_of_sequence):
    number = 1
    longest = 1
    memory = {}
    while number <= num_of_sequence:
        #print("这是%d的序列:" %number)
        temp = 1
        lonumber = number
        while True:
            if lonumber == 1:
                #print(lonumber)
                break
            elif lonumber % 2 == 0:
                #print(lonumber)
                lonumber = int(lonumber / 2)
                temp += 1
                if memory.__contains__(lonumber):
                    temp += memory[lonumber] - 1
                    break
            elif lonumber % 2 == 1:
                #print(lonumber)
                lonumber = 3*lonumber + 1
                temp += 1
                if memory.__contains__(lonumber):
                    temp += memory[lonumber] - 1
                    break
        if temp > longest:
            longest = temp
            longestnumber = number
        memory[number] = temp
        number += 1
        #print("--------")

    print("在不超过%d的数字中，能得到最长序列的数字是%d" %(num_of_sequence,longestnumber))
    print("该数字序列量为： %d" %longest)
    #print(memory)

start_longestsequence = time.time()
longestsequence(1000000)
time_longestsequence = time.time() - start_longestsequence
print("%f秒" %time_longestsequence)

在不超过1000000的数字中，能得到最长序列的数字是837799
该数字序列量为： 525
2.077740秒

做一个字典去存储已经计算过的序列，之后再遇到那一段同样的序列就可以直接加上已储存的值，这个方法把整个程序从33秒提升到2秒

gonorth

def f():
    record = []
    for n in range(13,14):
        count = 1
        while  1 :
            if n % 2 == 0:
                n = n // 2

                count += 1
            if n % 2 != 0 and n > 1:
                n = 3 * n + 1
                count += 1
            if n == 1:
                count
                #print (count)
                break
        record.append(count)
        count = 1
    return max(record)




print (f())

卢本伟牛逼

#include <stdio.h>
#include <math.h>

static int flag;//计数器 

int Collatz2(long long int value){//2、非递归 
        int count = 0;
        while(value > 1){
                flag++;
                value = (value%2)?value * 3 + 1: value / 2;
                count += 1;
        }
        return count + 1;
}

int main(void)
{
        int i;
        int max_Collatz_num;
        int max;
        int temp;

        for(i=1;i<1000000;i++){
                temp = Collatz2(i);
                if (temp > max){
                        max = temp;
                        max_Collatz_num = i;
                }
        }

        printf("max_Collatz_num = %d, count = %d\n", max_Collatz_num, Collatz2(max_Collatz_num));
        printf("flag = %d\n", flag);

        return 0;
}
//max_Collatz_num = 837799, count = 525
//flag = 131434796

ft215378

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

棒

番杰

#include<stdio.h>

#define MAX  1000000

typedef unsigned int   UINT;
int len = 0;

int Odd_or_Even(UINT);

int main(void)
{
        unsigned int Max_len = 0,Max_num = 0; 
        
        for(int i = 1;i < max;i++)
        {
                len = 0;
                Odd_or_Even(i);
                if(Max_len < len )
                {
                        Max_len = len;
                        Max_num = i;
                }
        }
        
        printf("%d,%d",Max_len,Max_num);
        
        return 0;
}

int Odd_or_Even(UINT num)
{
        len ++;        
        
        if(num == 1)
                return 1;
        else
        {
                if(num % 2 ==0)
                        Odd_or_Even((num / 2));
                else
                        Odd_or_Even((num * 3 + 1));
        }
        
        return 0;
}

guosl

/*
答案：837799
耗时：0.411748秒（单核）
      0.0373096秒（八核）
*/
#include <iostream>
#include <omp.h>
using namespace std;

const int N = 1000000;

int main(void)
{
  volatile int nMaxLen = 0, nVal = 0;
#pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic,16)
  for (int i = 1; i <= N; ++i)
  {
    int nStep = 1;
    long long l = i;
    while (l != 1LL)
    {
      if (l % 2LL == 0)
        l = l >> 1;
      else
        l = 3LL * l + 1LL;
      ++nStep;
    }
    if (nStep > nMaxLen)
    {
#pragma omp critical
      {
        nMaxLen = nStep;
        nVal = i;
      }
    }
  }
  cout << nVal << endl;
  return 0;
}

jerryxjr1220

package main

import (
        "fmt"
        "time"
)

//题目14：
//
//以下迭代序列定义在整数集合上：
//
//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 万的。

var n = map[int64]int64{
        1: 1,
        2: 2,
}

func If(b bool, vt int64, vf int64) int64 {
        if b == true {
                return vt
        } else {
                return vf
        }
}

func loop(a int64) int64 {
        t := a
        var c int64 = 0
        for n[t] == 0 {
                t = If(t%2 == 0, t/2, t*3+1)
                c++
        }
        n[a] = n[t] + c
        t = If(a%2 == 0, a/2, a*3+1)
        p := a
        for n[t] == 0 {
                n[t] = n[p] - 1
                p = t
                t = If(a%2 == 0, a/2, a*3+1)
        }
        return n[a]
}

func main() {
        t := time.Now()
        var i int64
        for i = 3; i < 1000000; i++ {
                _ = loop(i)
        }
        var max = map[string]int64{
                "key":   1,
                "value": 1,
        }
        for key, value := range n {
                if value > max["value"] {
                        max["value"] = value
                        max["key"] = key
                }
        }
        fmt.Println(max)
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

map[key:837799 value:525] 
耗时： 309 ms