Mathematica中的Collat​​z猜想

Question

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

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

这基于:http://en.wikipedia.org/wiki/Collat​​z_conjecture

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

ReplaceRepeated::rrlim: Exiting after {1,2,3,4} scanned 65536 times. >>

请帮我理解模式/规则中的错误.

问候

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

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

Answer 2

你有正确的递归情况,但你没有基本情况来终止递归导致无限递归(或直到Mathematica达到模式替换限制).如果在达到1时停止,它将按预期工作:

In[1]:= A = {1,2,3,4}
Out[1]= {1,2,3,4}

In[2]:= A //. {x_?EvenQ /; x>1 -> x/2, x_?OddQ /; x>1 -> 3 x+1}
Out[2]= {1,1,1,1}