(* Content-type: application/mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 6.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 145, 7] NotebookDataLength[ 15410, 532] NotebookOptionsPosition[ 13160, 458] NotebookOutlinePosition[ 13541, 475] CellTagsIndexPosition[ 13498, 472] WindowFrame->Normal ContainsDynamic->False*) (* Beginning of Notebook Content *) Notebook[{ Cell["Demo arithmetic functions", "Title"], Cell[CellGroupData[{ Cell["Initialisation", "Section"], Cell[BoxData[ RowBox[{ RowBox[{"mod", "[", RowBox[{"x_", ",", "m_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", "arg1", "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"arg1", "=", RowBox[{"ReleaseHold", "[", RowBox[{ RowBox[{"Hold", "[", "x", "]"}], "/.", RowBox[{"Power", "\[Rule]", "List"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Length", "[", "arg1", "]"}], ">", "1"}], ",", "\[IndentingNewLine]", RowBox[{"Return", "[", RowBox[{"PowerMod", "[", RowBox[{ RowBox[{"arg1", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"arg1", "[", RowBox[{"[", "2", "]"}], "]"}], ",", "m"}], "]"}], "]"}], ",", "\[IndentingNewLine]", RowBox[{"Return", "[", RowBox[{"Mod", "[", RowBox[{"x", ",", "m"}], "]"}], "]"}]}], "\[IndentingNewLine]", "]"}]}]}], "\[IndentingNewLine]", "]"}]}]], "Input", InitializationCell->True], Cell[BoxData[ RowBox[{ RowBox[{"rep", "[", "n_", "]"}], ":=", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"10", "^", "n"}], "-", "1"}], ")"}], "/", "9"}]}]], "Input", InitializationCell->True], Cell[BoxData[ RowBox[{ RowBox[{"randominteger", "[", "n_", "]"}], ":=", RowBox[{"Random", "[", RowBox[{"Integer", ",", RowBox[{"{", RowBox[{ RowBox[{"10", "^", RowBox[{"(", RowBox[{"n", "-", "1"}], ")"}]}], ",", RowBox[{"10", "^", "n"}]}], "}"}]}], "]"}]}]], "Input", InitializationCell->True], Cell[BoxData[ RowBox[{ RowBox[{"randomprime", "[", "n_", "]"}], ":=", RowBox[{"nextprime", "[", RowBox[{"randominteger", "[", "n", "]"}], "]"}]}]], "Input", InitializationCell->True], Cell[BoxData[ RowBox[{ RowBox[{"sigma0", "[", "n_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"ans", ",", "k", ",", "m"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"n", ">", "1"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"m", "=", RowBox[{ RowBox[{"Transpose", "[", RowBox[{"FactorInteger", "[", "n", "]"}], "]"}], "[", RowBox[{"[", "2", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"m", "=", RowBox[{"(", RowBox[{"1", "+", "m"}], ")"}]}], ";", "\[IndentingNewLine]", RowBox[{"ans", "=", RowBox[{"Product", "[", RowBox[{ RowBox[{"m", "[", RowBox[{"[", "k", "]"}], "]"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", RowBox[{"Length", "[", "m", "]"}]}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Return", "[", "ans", "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"Return", "[", "1", "]"}]}], "\[IndentingNewLine]", "]"}]}], "\[IndentingNewLine]", "]"}]}]], "Input"], Cell[BoxData[ RowBox[{ RowBox[{"sigma1", "[", "n_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"ans", ",", "k", ",", "l", ",", "m"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"n", ">", "1"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"m", "=", RowBox[{"FactorInteger", "[", "n", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"ans", "=", RowBox[{"Product", "[", RowBox[{ RowBox[{"Sum", "[", RowBox[{ RowBox[{ RowBox[{"m", "[", RowBox[{"[", RowBox[{"k", ",", "1"}], "]"}], "]"}], "^", "l"}], ",", RowBox[{"{", RowBox[{"l", ",", "0", ",", RowBox[{"m", "[", RowBox[{"[", RowBox[{"k", ",", "2"}], "]"}], "]"}]}], "}"}]}], "]"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", RowBox[{"Length", "[", "m", "]"}]}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Return", "[", "ans", "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"Return", "[", "1", "]"}]}], "\[IndentingNewLine]", "]"}]}], "\[IndentingNewLine]", "]"}]}]], "Input"], Cell[BoxData[ RowBox[{ RowBox[{"r4", "[", "n_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"k", "=", RowBox[{"Floor", "[", RowBox[{"Sqrt", "[", "n", "]"}], "]"}]}], ",", "x", ",", "y", ",", "z", ",", "u", ",", RowBox[{"tel", "=", "0"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"For", "[", RowBox[{ RowBox[{"x", "=", RowBox[{"-", "k"}]}], ",", RowBox[{"x", "\[LessEqual]", "k"}], ",", RowBox[{"x", "++"}], ",", "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"y", "=", RowBox[{"-", "k"}]}], ",", RowBox[{"y", "\[LessEqual]", "k"}], ",", RowBox[{"y", "++"}], ",", "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"z", "=", RowBox[{"-", "k"}]}], ",", RowBox[{"z", "\[LessEqual]", "k"}], ",", RowBox[{"z", "++"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"u", "=", RowBox[{"n", "-", RowBox[{"x", "^", "2"}], "-", RowBox[{"y", "^", "2"}], "-", RowBox[{"z", "^", "2"}]}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"u", "==", "0"}], ",", RowBox[{"tel", "++"}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{"u", ">", "0"}], ")"}], "&&", RowBox[{"(", RowBox[{"u", "\[Equal]", RowBox[{ RowBox[{"(", RowBox[{"Floor", "[", RowBox[{"Sqrt", "[", RowBox[{"u", "+", "0.5"}], "]"}], "]"}], ")"}], "^", "2"}]}], ")"}]}], ",", RowBox[{"tel", "=", RowBox[{"tel", "+", "2"}]}]}], "]"}]}]}], "\[IndentingNewLine]", "]"}]}], "\[IndentingNewLine]", "]"}]}], "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", RowBox[{"Return", "[", "tel", "]"}], ";"}]}], "\[IndentingNewLine]", "]"}]}]], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Examples", "Section"], Cell[CellGroupData[{ Cell["Greatest Common Divisor", "Subsection"], Cell[BoxData[ RowBox[{"GCD", "[", RowBox[{"231", ",", "432"}], "]"}]], "Input"], Cell[BoxData[ RowBox[{"ExtendedGCD", "[", RowBox[{"231", ",", "432"}], "]"}]], "Input"], Cell[BoxData[ RowBox[{"a", "=", RowBox[{ RowBox[{"2", "^", "1000"}], "-", "1"}]}]], "Input"], Cell[BoxData[ RowBox[{"b", "=", RowBox[{ RowBox[{"3", "^", "1000"}], "-", "1"}]}]], "Input"], Cell[BoxData[ RowBox[{"GCD", "[", RowBox[{"a", ",", "b"}], "]"}]], "Input"], Cell[BoxData[ RowBox[{"a", "=", RowBox[{"rep", "[", "1000", "]"}]}]], "Input"], Cell[BoxData[ RowBox[{"b", "=", RowBox[{"rep", "[", "95", "]"}]}]], "Input"], Cell[BoxData[ RowBox[{"GCD", "[", RowBox[{"a", ",", "b"}], "]"}]], "Input"], Cell[BoxData[ RowBox[{"ExtendedGCD", "[", RowBox[{"a", ",", "b"}], "]"}]], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Divisor sums", "Subsection"], Cell["\<\ We have defined sigma1 [n]to be the sum of all (positive) divisors of n.\ \>", "Text"], Cell[BoxData[{ RowBox[{"sigma1", "[", "100", "]"}], "\[IndentingNewLine]", RowBox[{"sigma1", "[", "4", "]"}], "\[IndentingNewLine]", RowBox[{"sigma1", "[", "25", "]"}]}], "Input"], Cell[BoxData[{ RowBox[{"a", "=", RowBox[{"rep", "[", "71", "]"}]}], "\[IndentingNewLine]", RowBox[{"sigma1", "[", "a", "]"}]}], "Input"], Cell["Let us find all prefect numbers below 100,000", "Text", CellChangeTimes->{{3.461311730420648*^9, 3.461311731196731*^9}}], Cell[BoxData[ RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", RowBox[{"k", "<", "100000"}], ",", RowBox[{"k", "++"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"sigma1", "[", "k", "]"}], "\[Equal]", RowBox[{"2", "*", "k"}]}], ",", RowBox[{"Print", "[", "k", "]"}]}], "]"}]}], "]"}]], "Input"], Cell["What about superperfect numbers?", "Text"], Cell[BoxData[ RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", RowBox[{"k", "<", "100000"}], ",", RowBox[{"k", "++"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"sigma1", "[", "k", "]"}], "\[Equal]", RowBox[{"3", "*", "k"}]}], ",", RowBox[{"Print", "[", "k", "]"}]}], "]"}]}], "]"}]], "Input"], Cell[BoxData[ RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", RowBox[{"k", "<", "100000"}], ",", RowBox[{"k", "++"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"sigma1", "[", "k", "]"}], "\[Equal]", RowBox[{"4", "*", "k"}]}], ",", RowBox[{"Print", "[", "k", "]"}]}], "]"}]}], "]"}]], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Sums of squares", "Subsection"], Cell[TextData[{ "We defined r4[n] to be the number of integer solutions ", Cell[BoxData[ FormBox[ RowBox[{"x", ",", "y", ",", "z", ",", "u"}], TraditionalForm]]], " to\n", Cell[BoxData[ FormBox[ RowBox[{"n", "=", RowBox[{ SuperscriptBox["x", "2"], "+", SuperscriptBox["y", "2"], "+", SuperscriptBox["z", "2"], "+", SuperscriptBox["u", "2"]}]}], TraditionalForm]]] }], "Text"], Cell["Examples:", "Text"], Cell[BoxData[ RowBox[{"r4", "[", "53", "]"}]], "Input"], Cell["Compare with 8 times the divisor sum", "Text"], Cell[BoxData[ RowBox[{"8", "*", RowBox[{"sigma1", "[", "53", "]"}]}]], "Input"], Cell[BoxData[ RowBox[{ RowBox[{"Table", "[", RowBox[{ RowBox[{"{", RowBox[{"k", ",", RowBox[{"r4", "[", "k", "]"}], ",", RowBox[{"8", "*", RowBox[{"sigma1", "[", "k", "]"}]}]}], "}"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", "20"}], "}"}]}], "]"}], "//", "TableForm"}]], "Input"], Cell[BoxData[{ RowBox[{ RowBox[{"r4", "[", "14", "]"}], "/", "8"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"r4", "[", "2", "]"}], "/", "8"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"r4", "[", "7", "]"}], "/", "8"}]}], "Input"], Cell[BoxData[{ RowBox[{ RowBox[{"r4", "[", RowBox[{"3", "*", "32"}], "]"}], "/", "8"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"r4", "[", "3", "]"}], "/", "8"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"r4", "[", "32", "]"}], "/", "8"}]}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Ramanujan tau", "Subsection"], Cell[TextData[{ "Write\n", StyleBox["q", FontSize->18], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ UnderoverscriptBox["\[Product]", RowBox[{"k", "=", "1"}], "\[Infinity]"], SuperscriptBox[ RowBox[{"(", RowBox[{"1", "-", SuperscriptBox["q", "k"]}], ")"}], "24"]}], " ", "=", RowBox[{ UnderoverscriptBox["\[Sum]", RowBox[{"n", "=", "1"}], "\[Infinity]"], RowBox[{ RowBox[{"tau", "(", "n", ")"}], SuperscriptBox["q", "n"]}]}]}], TraditionalForm]], FontSize->18], "\nWe call tau(n) the Ramanujan tau-function" }], "Text"], Cell[BoxData[ RowBox[{"eta", "=", RowBox[{"q", "*", RowBox[{"Product", "[", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{"1", "-", RowBox[{"q", "^", "k"}], "+", RowBox[{ RowBox[{"O", "[", "q", "]"}], "^", "100"}]}], ")"}], "^", "24"}], ",", RowBox[{"{", RowBox[{"k", ",", "1", ",", "100"}], "}"}]}], "]"}]}]}]], "Input"], Cell[BoxData[ RowBox[{"tau", "=", RowBox[{"CoefficientList", "[", RowBox[{ RowBox[{ RowBox[{"Normal", "[", "eta", "]"}], "/", "q"}], ",", "q"}], "]"}]}]], "Input"], Cell["The tau function is multiplicative", "Text"], Cell[BoxData[ RowBox[{ RowBox[{"tau", "[", RowBox[{"[", "56", "]"}], "]"}], "-", RowBox[{ RowBox[{"tau", "[", RowBox[{"[", "8", "]"}], "]"}], "*", RowBox[{"tau", "[", RowBox[{"[", "7", "]"}], "]"}]}]}]], "Input"] }, Closed]] }, Open ]] }, AutoGeneratedPackage->None, WindowSize->{520, 600}, WindowMargins->{{239, Automatic}, {Automatic, 88}}, ShowSelection->True, FrontEndVersion->"6.0 for Linux x86 (64-bit) (April 20, 2007)", StyleDefinitions->"Demo.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[568, 21, 42, 0, 102, "Title"], Cell[CellGroupData[{ Cell[635, 25, 33, 0, 76, "Section"], Cell[671, 27, 1093, 31, 127, "Input", InitializationCell->True], Cell[1767, 60, 207, 7, 35, "Input", InitializationCell->True], Cell[1977, 69, 345, 11, 31, "Input", InitializationCell->True], Cell[2325, 82, 193, 5, 31, "Input", InitializationCell->True], Cell[2521, 89, 1172, 30, 159, "Input"], Cell[3696, 121, 1312, 36, 159, "Input"], Cell[5011, 159, 2279, 59, 239, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[7327, 223, 27, 0, 45, "Section"], Cell[CellGroupData[{ Cell[7379, 227, 45, 0, 40, "Subsection"], Cell[7427, 229, 83, 2, 33, "Input"], Cell[7513, 233, 91, 2, 33, "Input"], Cell[7607, 237, 99, 3, 33, "Input"], Cell[7709, 242, 99, 3, 33, "Input"], Cell[7811, 247, 79, 2, 33, "Input"], Cell[7893, 251, 82, 2, 33, "Input"], Cell[7978, 255, 80, 2, 33, "Input"], Cell[8061, 259, 79, 2, 33, "Input"], Cell[8143, 263, 87, 2, 33, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[8267, 270, 34, 0, 34, "Subsection"], Cell[8304, 272, 96, 2, 49, "Text"], Cell[8403, 276, 184, 3, 78, "Input"], Cell[8590, 281, 142, 3, 56, "Input"], Cell[8735, 286, 127, 1, 32, "Text"], Cell[8865, 289, 359, 11, 56, "Input"], Cell[9227, 302, 48, 0, 32, "Text"], Cell[9278, 304, 359, 11, 56, "Input"], Cell[9640, 317, 359, 11, 56, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10036, 333, 37, 0, 34, "Subsection"], Cell[10076, 335, 417, 14, 78, "Text"], Cell[10496, 351, 25, 0, 32, "Text"], Cell[10524, 353, 56, 1, 33, "Input"], Cell[10583, 356, 52, 0, 32, "Text"], Cell[10638, 358, 83, 2, 33, "Input"], Cell[10724, 362, 338, 11, 56, "Input"], Cell[11065, 375, 239, 6, 78, "Input"], Cell[11307, 383, 264, 7, 78, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[11608, 395, 35, 0, 34, "Subsection"], Cell[11646, 397, 609, 22, 96, "Text"], Cell[12258, 421, 392, 13, 78, "Input"], Cell[12653, 436, 184, 6, 33, "Input"], Cell[12840, 444, 50, 0, 32, "Text"], Cell[12893, 446, 239, 8, 33, "Input"] }, Closed]] }, Open ]] } ] *) (* End of internal cache information *)