在 Ruby 中查找第二长的数组 - Collat​​z 猜想算法

Question

Collat​​z 猜想：

https://en.wikipedia.org/wiki/Collatz_conjecture

对于任何正整数 n 我们定义两个规则： 如果偶数：除以二 如果是奇数：乘以三，然后加一，重复直到结果为数字1。n的最小值为1。

这将生成如下数字序列，收敛到 1:

6、3、10、5、16、8、4、2、1

对于每个数字 n，我们现在可以计算此序列中的步数，直到达到 1。

所以上面的序列，从6开始，长度为9（包括起点和最后一个）。

我的问题：

我正在尝试找出所有小于或等于 1000 万的整数的第二长序列。你会怎么做？

到目前为止我想出了一个找到最长序列的解决方案，但我不确定如何找到第二个。

def collatz_sequence_eval(n)
  array_sequence = []
  until n == 1
    if n%2 != 0
        n = 3*n + 1
        array_sequence.push(n)
      else
        n = n/2
        array_sequence.push(n)
    end
  end
  return array_sequence
end

def collatz_iterator
  counter = 1
  current_longest_sequence = []
  until counter == 10000000
    cur_seq = collatz_sequence_eval(counter)
    if cur_seq.length > current_longest_sequence.length
      current_longest_sequence = cur_seq
      counter+=1
    else
      counter+=1
    end
  end
    puts "Starting number is #{current_longest_sequence[0]}.
    Sequence length is #{current_longest_sequence.length}"
end

Answer 1

def collatz(n)
  seq = [n]
  until n == 1
    n = n.even? ? n/2 : 3*n + 1
    seq << n
  end
  seq
end

(2..10**7).reduce([[],[]]) do |(longest, next_longest), n|
  seq = collatz(n)
  seq_size = seq.size
  if seq_size > longest.size
    [seq, longest]
  elsif seq_size < longest.size && seq_size > next_longest.size
    [longest, seq]
  else
    [longest, next_longest]
  end
end
  #=> [[8400511, 25201534, 12600767, 37802302, 18901151, 56703454, 
  #     ...
  #     106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
  #    [8865705, 26597116, 13298558, 6649279, 19947838, 9973919,
  #     ...
  #     17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]]

通过将最后的 end 更改为 end.map(&:size)，返回 [686, 668]，这意味着最长的序列长度为 686，下一个最长的序列, 668。

最长序列的长度似乎与 Wiki 中给出的结果一致，其中指出对于 n < 10^7 685 "steps" 是必需的。

在配备 1.2GHz 第 7 代 i5 的 Pixelbook 上使用 Linux 时，需要

226 秒来执行此计算。