Collatz-Vermutung in Mathematica

Question

Ich bin neu in Mathematica und versuche, Muster und Regeln zu verstehen. Also habe ich das Folgende versucht:

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

Dies basiert auf: http://en.wikipedia.org/wiki/Collatz_conjecture

Das sollte eigentlich konvergieren, aber ich habe folgendes Ergebnis:

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

Bitte helfen Sie mir, meinen Fehler in der Vorlage/Regel zu verstehen.

Mit freundlichen Grüßen

Answer 1

So wie Sie das geschrieben haben, endet es nicht, also wechselt es z.B. zwischen 1 und 4, 2 usw. (alle rekursiven Beschreibungen müssen irgendwann irgendwo enden, und Ihre enthält keinen Fall, um das zu tun bei n=1 ).

Das funktioniert:

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

obwohl sie keine Liste der Zwischenergebnisse enthält. Ein bequemer Weg, sie zu erhalten, ist

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

oder

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

so dass z.B.

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

Übrigens war der schnellste Ansatz, den ich finden konnte (ich glaube, ich brauchte ihn für ein Euler-Problem), ungefähr so

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]]

vergleichen:

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

während

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

(wir müssen die Rekursionsgrenze erhöhen, damit dies korrekt funktioniert).

Answer 2

Sie haben die rekursiven Fälle richtig verstanden, aber Sie haben keinen Basisfall, um die Rekursion zu beenden, was zu einer unendlichen Rekursion führt (oder bis Mathematica die Grenze der Musterersetzung erreicht). Wenn Sie aufhören, wenn Sie 1 erreichen, funktioniert es wie erwartet:

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}

Answer 3

Im Dokumentationszentrum, den Abschnitt über das Schreiben von Paketen wird anhand eines Beispiels einer Collatz-Funktion veranschaulicht.