wolfram-mathematica - Mathematica 中的 Collat​​z 猜想

Question

我是 Mathematica 的新手，正在尝试理解模式和规则。所以我尝试了以下方法:

A = {1, 2, 3, 4}
一种//。 {x_?EvenQ -> x/2, x_?OddQ -> 3 x + 1}

这是基于:http://en.wikipedia.org/wiki/Collatz_conjecture

这应该收敛，但我得到的是:

ReplaceRepeated::rrlim: {1,2,3,4} 扫描 65536 次后退出。 >>

请帮助我理解我在模式/规则中的错误。

问候

Answer 1

你写这个的方式，它不会终止，所以它例如最终在 1 和 4、2 等之间交替(所有递归描述最终必须在某个地方触底，并且你不包括在 n=1 处这样做的案例) .

这有效:

ClearAll[collatz];
collatz[1] = 1;
collatz[n_ /; EvenQ[n]] := collatz[n/2]
collatz[n_ /; OddQ[n]] := collatz[3 n + 1]

虽然它没有给出中间结果的列表。获取它们的便捷方法是

ClearAll[collatz];
collatz[1] = 1;
collatz[n_ /; EvenQ[n]] := (Sow[n]; collatz[n/2])
collatz[n_ /; OddQ[n]] := (Sow[n]; collatz[3 n + 1])
runcoll[n_] := Last@Last@Reap[collatz[n]]

runcoll[115]
(*
-> {115, 346, 173, 520, 260, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56,
28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}
*)

或者

colSeq[x_] := NestWhileList[
Which[
EvenQ[#], #/2,
True, 3*# + 1] &,
 x,
 # \[NotEqual] 1 &]

所以例如

colSeq[115]
(*
-> {115, 346, 173, 520, 260, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56,
28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}
*)

顺便说一下，我能想到的最快的方法(我想我需要它来解决一些欧拉问题)就像

Clear@collatz;
collatz[1] := {1}
collatz[n_] := collatz[n] = If[
  EvenQ[n] && n > 0,
  {n}~Join~collatz[n/2],
  {n}~Join~collatz[3*n + 1]]

相比:

colSeq /@ Range[20000]; // Timing
(*
-> {6.87047, Null}
*)

尽管

Block[{$RecursionLimit = \[Infinity]},
  collatz /@ Range[20000];] // Timing
(*
-> {0.54443, Null}
*)

(我们需要增加递归限制以使其正确运行)。