(* Content-type: application/vnd.wolfram.mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 10.4' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 158, 7] NotebookDataLength[ 17741, 526] NotebookOptionsPosition[ 16562, 480] NotebookOutlinePosition[ 16906, 495] CellTagsIndexPosition[ 16863, 492] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell["Recam\[AAcute]n\[CloseCurlyQuote]s Sequence", "Title", CellChangeTimes->{{3.7765904995543933`*^9, 3.7765905136720357`*^9}}], Cell["Adam Rumpf, 8/25/2018", "Text", CellChangeTimes->{{3.7765905248474903`*^9, 3.776590541701131*^9}}], Cell[CellGroupData[{ Cell["Introduction", "Section", CellChangeTimes->{{3.7765908131251736`*^9, 3.776590816785983*^9}}], Cell[TextData[{ "Recam\[AAcute]n\[CloseCurlyQuote]s sequence starts at index ", Cell[BoxData[ FormBox[ RowBox[{"n", "=", "0"}], TraditionalForm]]], " with element ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "0"], "=", "0"}], TraditionalForm]]], ". To find ", Cell[BoxData[ FormBox[ SubscriptBox["a", RowBox[{"n", "+", "1"}]], TraditionalForm]]], " given ", Cell[BoxData[ FormBox[ SubscriptBox["a", "n"], TraditionalForm]]], ", we either take ", Cell[BoxData[ FormBox["n", TraditionalForm]]], " steps backward or ", Cell[BoxData[ FormBox["n", TraditionalForm]]], " steps forward. We go backward if ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "n"], "-", "n"}], TraditionalForm]]], " is (a) nonnegative and (b) not already part of the sequence. Otherwise we \ go forward." }], "Text", CellChangeTimes->{{3.7442324030080566`*^9, 3.7442329422873044`*^9}, { 3.744232974096304*^9, 3.7442329947321434`*^9}, 3.7765906679017487`*^9}], Cell[TextData[{ "Starting from ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "0"], "=", "0"}], TraditionalForm]]], ", our choices for ", Cell[BoxData[ FormBox[ SubscriptBox["a", "1"], TraditionalForm]]], " are to go backward to ", Cell[BoxData[ FormBox[ RowBox[{"-", "1"}], TraditionalForm]]], " or forward to ", Cell[BoxData[ FormBox["1", TraditionalForm]]], ". We only allow nonnegative entries, so we take ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "1"], "=", "1"}], TraditionalForm]]], ". Next we go either 2 steps backward to ", Cell[BoxData[ FormBox["0", TraditionalForm]]], " or 2 steps forward to ", Cell[BoxData[ FormBox["3", TraditionalForm]]], ". ", Cell[BoxData[ FormBox["0", TraditionalForm]]], " is already on our list, so we go forward to get ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "2"], "=", "3"}], TraditionalForm]]], ". For ", Cell[BoxData[ FormBox[ SubscriptBox["a", "3"], TraditionalForm]]], " our choices are ", Cell[BoxData[ FormBox["0", TraditionalForm]]], " or ", Cell[BoxData[ FormBox["6", TraditionalForm]]], ", so we take ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "3"], "=", "6"}], TraditionalForm]]], ". For ", Cell[BoxData[ FormBox[ SubscriptBox["a", "4"], TraditionalForm]]], " our choices are ", Cell[BoxData[ FormBox["2", TraditionalForm]]], " or ", Cell[BoxData[ FormBox["10", TraditionalForm]]], ", and since ", Cell[BoxData[ FormBox["2", TraditionalForm]]], " is not yet on our list, we go backwards to ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["a", "4"], "=", "2"}], TraditionalForm]]], ". The first 10 elements are:" }], "Text", CellChangeTimes->{{3.7442324030080566`*^9, 3.7442329422873044`*^9}, { 3.744232974096304*^9, 3.7442329947321434`*^9}, {3.7765906679017487`*^9, 3.7765906742287025`*^9}}], Cell[TextData[Cell[BoxData[ FormBox[ RowBox[{ "0", ",", " ", "1", ",", " ", "3", ",", " ", "6", ",", " ", "2", ",", " ", "7", ",", " ", "13", ",", " ", "20", ",", " ", "12", ",", " ", "21", ",", " ", "..."}], TraditionalForm]], FormatType->"TraditionalForm"]], "Text", CellChangeTimes->{{3.7442324030080566`*^9, 3.7442329422873044`*^9}, { 3.744232974096304*^9, 3.7442329947321434`*^9}, {3.7765906679017487`*^9, 3.7765906855611153`*^9}}], Cell["\<\ The common way to \"picture\" Recam\[AAcute]n's sequence is to draw \ semicircles on the number line, alternating over/under to connect pairs of \ consecutive values. Given the values in the sequence, we can generate the \ shapes with the Circle function.\ \>", "Text", CellChangeTimes->{{3.7442324030080566`*^9, 3.7442329422873044`*^9}, { 3.744232974096304*^9, 3.7442329947321434`*^9}, {3.7765906679017487`*^9, 3.7765906835077677`*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Code", "Section", CellChangeTimes->{{3.776590828273492*^9, 3.776590841577402*^9}}], Cell[CellGroupData[{ Cell["Initialization", "Subsection", CellChangeTimes->{{3.776590850848407*^9, 3.7765908530267057`*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"(*", " ", RowBox[{ "Generate", " ", "the", " ", "first", " ", "n", " ", "elements", " ", "of", " ", RowBox[{"Recam\[AAcute]n", "'"}], "s", " ", RowBox[{"sequence", "."}]}], " ", "*)"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"recaman", "[", "n_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"out", "=", RowBox[{"ConstantArray", "[", RowBox[{ RowBox[{"-", "1"}], ",", "n"}], "]"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"out", "[", RowBox[{"[", "1", "]"}], "]"}], "=", "0"}], ";", "\[IndentingNewLine]", RowBox[{"Do", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{ RowBox[{"i", "-", "1"}], ">", RowBox[{"out", "[", RowBox[{"[", RowBox[{"i", "-", "1"}], "]"}], "]"}]}], "||", RowBox[{"MemberQ", "[", RowBox[{"out", ",", RowBox[{ RowBox[{"out", "[", RowBox[{"[", RowBox[{"i", "-", "1"}], "]"}], "]"}], "-", "i", "+", "1"}]}], "]"}]}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"out", "[", RowBox[{"[", "i", "]"}], "]"}], "=", RowBox[{ RowBox[{"out", "[", RowBox[{"[", RowBox[{"i", "-", "1"}], "]"}], "]"}], "+", "i", "-", "1"}]}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"out", "[", RowBox[{"[", "i", "]"}], "]"}], "=", RowBox[{ RowBox[{"out", "[", RowBox[{"[", RowBox[{"i", "-", "1"}], "]"}], "]"}], "-", "i", "+", "1"}]}], ";"}]}], "\[IndentingNewLine]", "]"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"i", ",", "2", ",", "n"}], "}"}]}], "]"}], ";", "\[IndentingNewLine]", "out"}]}], "\[IndentingNewLine]", "]"}]}]}]], "Input", CellChangeTimes->{{3.7442330056289673`*^9, 3.7442330994125185`*^9}, { 3.7442393624630013`*^9, 3.7442395277059183`*^9}, {3.7442395682113776`*^9, 3.744239579582741*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"(*", " ", RowBox[{ RowBox[{"Given", " ", "a", " ", "list", " ", "of", " ", "values"}], ",", " ", RowBox[{"draws", " ", "alternating", " ", RowBox[{"over", "/", "under"}], " ", "semicircles", " ", "on", " ", "the", " ", "number", " ", "line", " ", "linking", " ", "consecutive", " ", RowBox[{"values", "."}]}]}], " ", "*)"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"rdraw", "[", "list_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"g", "=", RowBox[{"{", "}"}]}], ",", RowBox[{"p", "=", "1"}], ",", "c", ",", "r"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"(*", " ", RowBox[{"g", " ", "=", " ", RowBox[{ RowBox[{ "list", " ", "of", " ", "graphics", " ", "objects", " ", "to", " ", "display", "\[IndentingNewLine]", "p"}], " ", "=", " ", RowBox[{ RowBox[{ "parity", " ", "of", " ", "current", " ", "list", " ", "entry", " ", RowBox[{"(", RowBox[{"\[PlusMinus]", "1"}], ")"}], "\[IndentingNewLine]", "c"}], " ", "=", " ", RowBox[{ RowBox[{ "center", " ", "of", " ", "new", " ", "semicircle", "\[IndentingNewLine]", "r"}], " ", "=", " ", RowBox[{ "radius", " ", "of", " ", "new", " ", "semicircle"}]}]}]}]}], " ", "*)"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Do", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"c", "=", FractionBox[ RowBox[{ RowBox[{"list", "[", RowBox[{"[", "i", "]"}], "]"}], "+", RowBox[{"list", "[", RowBox[{"[", RowBox[{"i", "+", "1"}], "]"}], "]"}]}], "2"]}], ";", "\[IndentingNewLine]", RowBox[{"r", "=", FractionBox[ RowBox[{"Abs", "[", RowBox[{ RowBox[{"list", "[", RowBox[{"[", "i", "]"}], "]"}], "-", RowBox[{"list", "[", RowBox[{"[", RowBox[{"i", "+", "1"}], "]"}], "]"}]}], "]"}], "2"]}], ";", "\[IndentingNewLine]", RowBox[{"g", "=", RowBox[{"Append", "[", RowBox[{"g", ",", RowBox[{"Circle", "[", RowBox[{ RowBox[{"{", RowBox[{"c", ",", "0"}], "}"}], ",", "r", ",", RowBox[{"If", "[", RowBox[{ RowBox[{"p", ">", "0"}], ",", RowBox[{"{", RowBox[{"0", ",", "Pi"}], "}"}], ",", RowBox[{"{", RowBox[{"Pi", ",", RowBox[{"2", "Pi"}]}], "}"}]}], "]"}]}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"p", "*=", RowBox[{"-", "1"}]}]}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"i", ",", "1", ",", RowBox[{ RowBox[{"Length", "[", "list", "]"}], "-", "1"}]}], "}"}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"Graphics", "[", "g", "]"}]}]}], "\[IndentingNewLine]", "]"}]}]}]], "Input", CellChangeTimes->{{3.7442396489621964`*^9, 3.7442396878727245`*^9}, { 3.744239718849804*^9, 3.744240132943098*^9}}] }, Closed]], Cell[CellGroupData[{ Cell["Demonstration", "Subsection", CellChangeTimes->{{3.776590877179969*^9, 3.776590878772458*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"recaman", "[", "20", "]"}]], "Input", CellChangeTimes->{{3.744239485976697*^9, 3.744239489691038*^9}, { 3.7442395314040203`*^9, 3.744239539586299*^9}, {3.7442395852249513`*^9, 3.744239585938708*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0", ",", "1", ",", "3", ",", "6", ",", "2", ",", "7", ",", "13", ",", "20", ",", "12", ",", "21", ",", "11", ",", "22", ",", "10", ",", "23", ",", "9", ",", "24", ",", "8", ",", "25", ",", "43", ",", "62"}], "}"}]], "Output", CellChangeTimes->{{3.7442394879317155`*^9, 3.7442395865105467`*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"rdraw", "[", RowBox[{"recaman", "[", "10", "]"}], "]"}]], "Input", CellChangeTimes->{{3.744240064007079*^9, 3.7442400661813836`*^9}, { 3.7442401231879654`*^9, 3.744240125653216*^9}}], Cell[BoxData[ GraphicsBox[{ CircleBox[NCache[{Rational[1, 2], 0}, {0.5, 0}], NCache[ Rational[1, 2], 0.5], NCache[{0, Pi}, {0, 3.141592653589793}]], CircleBox[{2, 0}, 1, NCache[{Pi, 2 Pi}, {3.141592653589793, 6.283185307179586}]], CircleBox[NCache[{Rational[9, 2], 0}, {4.5, 0}], NCache[ Rational[3, 2], 1.5], NCache[{0, Pi}, {0, 3.141592653589793}]], CircleBox[{4, 0}, 2, NCache[{Pi, 2 Pi}, {3.141592653589793, 6.283185307179586}]], CircleBox[NCache[{Rational[9, 2], 0}, {4.5, 0}], NCache[ Rational[5, 2], 2.5], NCache[{0, Pi}, {0, 3.141592653589793}]], CircleBox[{10, 0}, 3, NCache[{Pi, 2 Pi}, {3.141592653589793, 6.283185307179586}]], CircleBox[NCache[{Rational[33, 2], 0}, {16.5, 0}], NCache[ Rational[7, 2], 3.5], NCache[{0, Pi}, {0, 3.141592653589793}]], CircleBox[{16, 0}, 4, NCache[{Pi, 2 Pi}, {3.141592653589793, 6.283185307179586}]], CircleBox[NCache[{Rational[33, 2], 0}, {16.5, 0}], NCache[ Rational[9, 2], 4.5], NCache[{0, Pi}, {0, 3.141592653589793}]]}]], "Output", CellChangeTimes->{{3.744240066704217*^9, 3.7442401347849693`*^9}, { 3.776591054169651*^9, 3.7765910581853857`*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"(*", " ", RowBox[{ "Manipulate", " ", "to", " ", "generate", " ", "a", " ", "long", " ", "Recam\[AAcute]n", " ", "sequence", " ", "and", " ", "animate", " ", "the", " ", "drawing", " ", RowBox[{"process", "."}]}], " ", "*)"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"nmax", "=", "100"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"rlist", "=", RowBox[{"recaman", "[", "nmax", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Manipulate", "[", RowBox[{ RowBox[{"Show", "[", RowBox[{ RowBox[{"rdraw", "[", RowBox[{"rlist", "[", RowBox[{"[", RowBox[{"1", ";;", "n"}], "]"}], "]"}], "]"}], ",", RowBox[{"PlotRange", "\[Rule]", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"-", "1"}], ",", RowBox[{ RowBox[{"Max", "[", "rlist", "]"}], "+", "1"}]}], "}"}], ",", RowBox[{"{", RowBox[{ RowBox[{ RowBox[{"-", "nmax"}], "-", "1"}], ",", RowBox[{"nmax", "+", "1"}]}], "}"}]}], "}"}]}]}], "]"}], ",", RowBox[{"{", RowBox[{"n", ",", "2", ",", "nmax", ",", "1"}], "}"}]}], "]"}]}]}]], "Input", CellChangeTimes->{{3.7442401408959684`*^9, 3.7442401766210194`*^9}, { 3.744240354392541*^9, 3.744240440955964*^9}, {3.744240482992465*^9, 3.7442404834353294`*^9}, {3.744240708961824*^9, 3.744240957278532*^9}, { 3.7442409908046117`*^9, 3.7442409908785863`*^9}}], Cell[BoxData[ TagBox[ StyleBox[ DynamicModuleBox[{$CellContext`n$$ = 100, Typeset`show$$ = True, Typeset`bookmarkList$$ = {}, Typeset`bookmarkMode$$ = "Menu", Typeset`animator$$, Typeset`animvar$$ = 1, Typeset`name$$ = "\"untitled\"", Typeset`specs$$ = {{ Hold[$CellContext`n$$], 2, 100, 1}}, Typeset`size$$ = { 360., {156., 160.}}, Typeset`update$$ = 0, Typeset`initDone$$, Typeset`skipInitDone$$ = True, $CellContext`n$64662$$ = 0}, DynamicBox[Manipulate`ManipulateBoxes[ 1, StandardForm, "Variables" :> {$CellContext`n$$ = 2}, "ControllerVariables" :> { Hold[$CellContext`n$$, $CellContext`n$64662$$, 0]}, "OtherVariables" :> { Typeset`show$$, Typeset`bookmarkList$$, Typeset`bookmarkMode$$, Typeset`animator$$, Typeset`animvar$$, Typeset`name$$, Typeset`specs$$, Typeset`size$$, Typeset`update$$, Typeset`initDone$$, Typeset`skipInitDone$$}, "Body" :> Show[ $CellContext`rdraw[ Part[$CellContext`rlist, Span[1, $CellContext`n$$]]], PlotRange -> {{-1, Max[$CellContext`rlist] + 1}, {-$CellContext`nmax - 1, $CellContext`nmax + 1}}], "Specifications" :> {{$CellContext`n$$, 2, 100, 1}}, "Options" :> {}, "DefaultOptions" :> {}], ImageSizeCache->{411., {202., 208.}}, SingleEvaluation->True], Deinitialization:>None, DynamicModuleValues:>{}, SynchronousInitialization->True, UndoTrackedVariables:>{Typeset`show$$, Typeset`bookmarkMode$$}, UnsavedVariables:>{Typeset`initDone$$}, UntrackedVariables:>{Typeset`size$$}], "Manipulate", Deployed->True, StripOnInput->False], Manipulate`InterpretManipulate[1]]], "Output", CellChangeTimes->{{3.744240710709268*^9, 3.7442407417829285`*^9}, { 3.7442408124253116`*^9, 3.744240817789596*^9}, {3.7442408487867656`*^9, 3.74424087012694*^9}, 3.7442409595598*^9, 3.7442409914119277`*^9, 3.7442431841989555`*^9, 3.7765910642354493`*^9}] }, Open ]] }, Open ]] }, Open ]] }, Open ]] }, WindowSize->{759, 833}, WindowMargins->{{420, Automatic}, {Automatic, 76}}, FrontEndVersion->"10.4 for Microsoft Windows (64-bit) (April 11, 2016)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[580, 22, 130, 1, 90, "Title"], Cell[713, 25, 105, 1, 30, "Text"], Cell[CellGroupData[{ Cell[843, 30, 99, 1, 63, "Section"], Cell[945, 33, 1002, 34, 68, "Text"], Cell[1950, 69, 1907, 73, 106, "Text"], Cell[3860, 144, 456, 9, 30, "Text"], Cell[4319, 155, 453, 8, 68, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[4809, 168, 89, 1, 63, "Section"], Cell[CellGroupData[{ Cell[4923, 173, 104, 1, 43, "Subsection"], Cell[5030, 176, 2315, 63, 232, "Input"], Cell[7348, 241, 3382, 89, 419, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10767, 335, 101, 1, 35, "Subsection"], Cell[CellGroupData[{ Cell[10893, 340, 229, 4, 31, "Input"], Cell[11125, 346, 349, 7, 31, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[11511, 358, 212, 4, 31, "Input"], Cell[11726, 364, 1179, 22, 169, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[12942, 391, 1574, 41, 132, "Input"], Cell[14519, 434, 1991, 40, 427, "Output"] }, Open ]] }, Open ]] }, Open ]] }, Open ]] } ] *)