(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 46205, 1308]*) (*NotebookOutlinePosition[ 46926, 1333]*) (* CellTagsIndexPosition[ 46882, 1329]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["Restricted Partition Functions", "Title"], Cell["Examples", "Subtitle"], Cell["Eckhard Manthei", "Subsubtitle"], Cell[CellGroupData[{ Cell["Setup", "Section"], Cell[BoxData[ \(\(SetDirectory[ ToFileName[NotebookDirectory /. Options[$FrontEnd]]];\)\)], "Input", InitializationCell->True], Cell[BoxData[ \(Get["\"]\)], "Input", InitializationCell->True], Cell[BoxData[ \(Off[General::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\", PartitionData::"\"]\)], "Input", InitializationCell->True] }, Open ]], Cell[CellGroupData[{ Cell["Information", "Section"], Cell[BoxData[ \(\(?RestrictedPartitionFunctions`*\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Tests", "Section"], Cell[CellGroupData[{ Cell["Overview", "Subsection"], Cell[BoxData[ \(\(cns = {5, 7, 11};\)\)], "Input"], Cell[BoxData[{ \(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier]\), "\n", \(pnd = NewtonDataL[cns]\), "\n", \(rub = RubinsteinData[cns]\)}], "Input"], Cell[BoxData[ \(ColumnForm[MatrixForm /@ pcr]\)], "Input"], Cell[BoxData[{ \({pcr[\([1]\)], BinomialToNewton[pcr[\([1]\)]], BinomialToNormal[pcr[\([1]\)]]}\), "\[IndentingNewLine]", \({pnd[\([1]\)], NewtonToBinomial[pnd[\([1]\)]], NewtonToNormal[pnd[\([1]\)]]}\), "\[IndentingNewLine]", \({rub[\([1]\)], NormalToBinomial[rub[\([1]\)]], NormalToNewton[rub[\([1]\)]]}\)}], "Input"], Cell[BoxData[{ \(\(Denumerant[pcr]\)[10^6]\), "\[IndentingNewLine]", \(\(NewtonDenumerant[pnd]\)[10^6]\), "\[IndentingNewLine]", \(\(NormalDenumerant[rub]\)[10^6]\)}], "Input"], Cell[BoxData[{ \(\(Denumerant[pcr]\)[10^120]\), "\[IndentingNewLine]", \(\(NewtonDenumerant[pnd]\)[10^120]\), "\[IndentingNewLine]", \(\(NormalDenumerant[rub]\)[10^120]\)}], "Input"], Cell[BoxData[{ \(net = NettoData[cns, n]\), "\[IndentingNewLine]", \(Table[FullSimplify[net], {n, 25}]\)}], "Input"], Cell[BoxData[{ \(\(gkp = GrahamData[cns];\)\), "\[IndentingNewLine]", \(\(GrahamDenumerant[gkp]\)[10^6]\)}], "Input"], Cell[BoxData[{ \(new = NewtonDataG[cns]; MatrixForm[new[\([1]\)]]\), "\[IndentingNewLine]", \(\(NewtonDenumerant[new]\)[10^6]\)}], "Input"], Cell[BoxData[{ \(\(bel = BellData[cns, n];\)\), "\[IndentingNewLine]", \(bel[\([Mod[10^6, Length[bel]] + 1]\)] /. n \[Rule] 10^6\)}], "Input"], Cell[BoxData[{ \(SylvesterData[cns, n]\), "\[IndentingNewLine]", \(RubinsteinData[cns, n]\)}], "Input"], Cell[BoxData[{ \(ser = SertoezData[cns, n]\), "\[IndentingNewLine]", \(\(ser /. n \[Rule] 10^6\) /. z_\ SymbolicBinomial[x_, y_] \[RuleDelayed] z\ If[IntegerQ[x], Binomial[x, y], 0]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Series expansion", "Subsection"], Cell[BoxData[{ \(\(cns = {3, 4, 8, 8, 12, 32, 48, 97};\)\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \(VectorQ[tu = Table[\(Denumerant[pcr]\)[n], {n, 0, 500}], IntegerQ]\), "\n", \(tu == \(Series[\((Times @@ \((1 - z^cns)\))\)^\(-1\), {z, 0, 500}]\)[\([3]\)]\)}], "Input"], Cell[BoxData[{ \(\(cns = Range[6];\)\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\), "\n", \(VectorQ[tu = Table[\(Denumerant[pcr]\)[n], {n, 0, 500}], IntegerQ]\), "\[IndentingNewLine]", \(tu == \(Series[\((Times @@ \((1 - z^cns)\))\)^\(-1\), {z, 0, 500}]\)[\([3]\)]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Comtet", "Subsection"], Cell[BoxData[ \(\(?Comtet*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(\(com = PartitionData[cns, PartitionMethod \[Rule] Comtet];\)\), "\[IndentingNewLine]", \(MatrixForm /@ com\), "\[IndentingNewLine]", \(Table[\(Denumerant[com]\)[n], {n, 0, 25}]\)}], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(com = ComtetData[cns]; MatrixForm /@ com\), "\[IndentingNewLine]", \(ByteCount[com]\), "\[IndentingNewLine]", \(Table[\(Denumerant[com]\)[n], {n, 0, 25}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Fourier", "Subsection"], Cell[BoxData[ \(\(?RestrictedPartitionFunctions`*Fourier*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(pcr = PartitionData[cns]\), "\[IndentingNewLine]", \(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier]\), "\[IndentingNewLine]", \(pcr = PartitionData[cns, PartitionMethod \[Rule] SymbolicFourier]\), "\[IndentingNewLine]", \(Table[\(Denumerant[pcr]\)[n], {n, 0, 25}]\)}], "Input"], Cell[BoxData[{ \(pcr = PrimeFourierData[cns]\), "\[IndentingNewLine]", \(ByteCount[pcr]\), "\[IndentingNewLine]", \(Table[\(Denumerant[pcr]\)[n], {n, 0, 25}]\)}], "Input"], Cell[BoxData[{ \(\(cns = {137, 251, 256};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PrimeFourierData[cns];\)]\), "\[IndentingNewLine]", \(ByteCount[pcr]\)}], "Input"], Cell[BoxData[{ \(\(crc = PartitionData[cns];\)\), "\[IndentingNewLine]", \(\(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier];\)\), "\[IndentingNewLine]", \(\(sym = PartitionData[cns, PartitionMethod \[Rule] SymbolicFourier];\)\), "\[IndentingNewLine]", \(ColumnForm[MatrixForm /@ pcr]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Graham", "Subsection"], Cell[BoxData[ \(\(?Graham*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(gkp = GrahamData[cns]\), "\[IndentingNewLine]", \(ByteCount[gkp]\)}], "Input"], Cell[BoxData[ \(Table[\(GrahamDenumerant[gkp]\)[n], {n, 0, 25}]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Newton", "Subsection"], Cell[BoxData[ \(\(?*Newton*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\n", \(MatrixForm[First[new = NewtonDataG[cns]]]\), "\n", \(ByteCount[new]\), "\n", \(Table[\(NewtonDenumerant[new]\)[n], {n, 0, 25}]\)}], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(pnd = NewtonDataL[cns]\), "\[IndentingNewLine]", \(ByteCount[pnd]\), "\[IndentingNewLine]", \(Table[\(NewtonDenumerant[pnd]\)[n], {n, 0, 25}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Bell", "Subsection"], Cell[BoxData[ \(\(?Bell*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(bel = BellData[cns, n]; MatrixForm[bel]\), "\[IndentingNewLine]", \(ByteCount[bel]\), "\[IndentingNewLine]", \(p = Length[bel]; Table[bel[\([Mod[n, p] + 1]\)], {n, 0, 25}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Netto", "Subsection"], Cell[BoxData[ \(\(?Netto*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(net = NettoData[cns, n]\), "\[IndentingNewLine]", \(ByteCount[net]\), "\[IndentingNewLine]", \(Table[FullSimplify[net], {n, 0, 25}]\)}], "Input"], Cell[BoxData[{ \(\(cns = {137, 251, 256};\)\), "\[IndentingNewLine]", \(Timing[\(net = NettoData[cns, n];\)]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Rubinstein", "Subsection"], Cell[BoxData[ \(\(?Rubinstein*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\n", \(rub = RubinsteinData[cns, n]\), "\n", \(ByteCount[rub]\), "\[IndentingNewLine]", \(Table[FullSimplify[rub], {n, 0, 25}]\)}], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(RubinsteinData[cns]\)}], "Input"], Cell[BoxData[{ \(\(cns = {137, 251, 256};\)\), "\[IndentingNewLine]", \(Timing[\(RubinsteinData[cns, n];\)]\)}], "Input"], Cell[BoxData[{ \(\(cns = Range[8];\)\), "\[IndentingNewLine]", \(Timing[\(RubinsteinData[cns, n];\)]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Sylvester", "Subsection"], Cell[BoxData[ \(\(?Sylvester*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(syl = SylvesterData[cns, n]\), "\[IndentingNewLine]", \(ByteCount[syl]\), "\[IndentingNewLine]", \(Table[FullSimplify[syl], {n, 0, 25}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Sertoez", "Subsection"], Cell[BoxData[ \(\(?Sertoez*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4};\)\), "\[IndentingNewLine]", \(ser = SertoezData[cns, n]\), "\[IndentingNewLine]", \(ByteCount[ser]\), "\[IndentingNewLine]", \(Table[ ser /. z_\ SymbolicBinomial[x_, y_] \[RuleDelayed] z\ If[IntegerQ[x], Binomial[x, y], 0], {n, 0, 25}]\)}], "Input"], Cell[BoxData[ \(\(\( (*\ Apart\ steigt\ aus\ *) \)\(\[IndentingNewLine]\)\(\(cns = {137, 251, 256};\)\[IndentingNewLine] Timing[\(SertoezData[cns, n];\)]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ Apart\ steigt\ aus\ *) \)\(\[IndentingNewLine]\)\(\(cns = Range[5];\)\[IndentingNewLine] Timing[\(ser = SertoezData[cns, n];\)]\)\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Time comparisons", "Subsection"], Cell[BoxData[{ \(cns = {5, 7}\), "\[IndentingNewLine]", \(SylvesterData[cns, n]\)}], "Input"], Cell[BoxData[{ \(\(cns = {11, 13, 15};\)\), "\[IndentingNewLine]", \(Timing[\(syl = SylvesterData[cns, n];\)]\), "\[IndentingNewLine]", \(Timing[\(rub = RubinsteinData[cns, n];\)]\), "\[IndentingNewLine]", \(Timing[\(ser = SertoezData[cns, n];\)]\), "\[IndentingNewLine]", \(Timing[\(net = NettoData[cns, n];\)]\)}], "Input"], Cell[BoxData[{ \(Table[FullSimplify[syl], {n, 0, 25}]\), "\[IndentingNewLine]", \(Table[FullSimplify[rub], {n, 0, 25}]\), "\[IndentingNewLine]", \(Table[FullSimplify[net], {n, 0, 25}]\), "\[IndentingNewLine]", \(Table[ ser /. z_\ SymbolicBinomial[x_, y_] \[RuleDelayed] z\ If[IntegerQ[x], Binomial[x, y], 0], {n, 0, 25}]\)}], "Input"], Cell[BoxData[ \(ByteCount /@ {syl, rub, net, ser}\)], "Input"], Cell[BoxData[{ \(\(cns = {11, 13, 15, 17};\)\), "\[IndentingNewLine]", \(Timing[\(crc = PartitionData[cns];\)]\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier];\)]\), "\[IndentingNewLine]", \(Timing[\(sym = PartitionData[cns, PartitionMethod \[Rule] SymbolicFourier];\)]\), "\[IndentingNewLine]", \(Timing[\(com = PartitionData[cns, PartitionMethod \[Rule] Comtet];\)]\)}], "Input"], Cell[BoxData[ \(ByteCount /@ {crc, pcr, sym, com}\)], "Input"], Cell[BoxData[{ \(\(cns = {11, 13};\)\), "\[IndentingNewLine]", \(Timing[\(new = PartitionData[cns, PartitionMethod \[Rule] NewtonG];\)]\), "\[IndentingNewLine]", \(Timing[\(pnd = PartitionData[cns, PartitionMethod \[Rule] NewtonL];\)]\), "\[IndentingNewLine]", \(Timing[\(gkp = PartitionData[cns, PartitionMethod \[Rule] Graham];\)]\)}], "Input"], Cell[BoxData[ \(ByteCount /@ {new, pnd, gkp}\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 5, 15, 17};\)\), "\[IndentingNewLine]", \(Timing[\(crc = PartitionData[cns];\)]\), "\[IndentingNewLine]", \(Timing[\(com = PartitionData[cns, PartitionMethod \[Rule] Comtet];\)]\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier];\)]\), "\[IndentingNewLine]", \(Timing[\(new = PartitionData[cns, PartitionMethod \[Rule] NewtonG];\)]\), "\[IndentingNewLine]", \(Timing[\(pnd = PartitionData[cns, PartitionMethod \[Rule] NewtonL];\)]\), "\[IndentingNewLine]", \(Timing[\(gkp = PartitionData[cns, PartitionMethod \[Rule] Graham];\)]\)}], "Input"], Cell[BoxData[{ \(\(Denumerant[crc]\)[10^6]\), "\[IndentingNewLine]", \(\(Denumerant[pcr]\)[10^6]\), "\[IndentingNewLine]", \(\(Denumerant[com]\)[10^6]\), "\[IndentingNewLine]", \(\(NewtonDenumerant[pnd]\)[10^6]\), "\[IndentingNewLine]", \(\(NewtonDenumerant[new]\)[10^6]\), "\[IndentingNewLine]", \(\(GrahamDenumerant[gkp]\)[10^6]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Euler", "Subsection"], Cell[BoxData[ \(\(?RestrictedPartitionFunctions`Euler*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4, 5};\)\), "\[IndentingNewLine]", \(\(EulerDenumerant[cns]\)[10^3]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["MatrixPower", "Subsection"], Cell[BoxData[ \(\(?MatrixPowerDenumerant*\)\)], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 3, 4, 5};\)\), "\[IndentingNewLine]", \(\(MatrixPowerDenumerant[cns]\)[10^3]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["gcd(A) > 1", "Subsection"], Cell[BoxData[{ \(\(cns = {9, 15, 27, 105};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \(Table[\(Denumerant[pcr]\)[n], {n, 0, 120}]\)}], "Input"], Cell[BoxData[{ \(cns = {9, 15, 27, 105}; gcd = GCD @@ cns\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns/gcd];\)]\), "\[IndentingNewLine]", \(Table[ DiscreteDelta[Mod[n, gcd]] \(Denumerant[pcr]\)[n/gcd], {n, 0, 120}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["PartialApart", "Subsection"], Cell[BoxData[{ \(\(cns = {2, 4, 5, 16, 25, 32, 64, 128};\)\), "\[IndentingNewLine]", \(PartialApart[cns, 16, z]\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Plots", "Section"], Cell[CellGroupData[{ Cell["Beispiel 1", "Subsection"], Cell[BoxData[{ \(\(cns = {5, 7};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\)}], "Input"], Cell[BoxData[{ \(\(pls = Plus @@ cns;\)\), "\[IndentingNewLine]", \(frb = Max[Position[Table[\(PartitionFunction[pcr]\)[n], {n, 0, 500}], 0] - 1]\)}], "Input"], Cell[BoxData[{ \(Block[\[IndentingNewLine]{$DisplayFunction = Identity\ }, \[IndentingNewLine]rng = Range[0, Length[cns] - 1]; pol = Flatten[pcr[\([1]\)]] . Binomial[n + rng, rng]; \[IndentingNewLine]lp1 = Plot[pol, {n, \(-100\), 100}, PlotStyle \[Rule] {Thickness[0.005], RGBColor[1, 0, 0]}]; \[IndentingNewLine]den = Table[{n, \(Denumerant[pcr]\)[n]}, {n, \(-100\), 100}]; \[IndentingNewLine]lp2 = ListPlot[den, PlotStyle \[Rule] {PointSize[0.008], RGBColor[0, 0, 1]}];\[IndentingNewLine]]\), "\n", \(\(Show[lp1, lp2, ImageSize \[Rule] 6\ 72, TextStyle -> "\", GridLines \[Rule] {{\(-frb\) - pls, \(-pls\)/2, frb}, None}, PlotRange \[Rule] {\(-3\), 3}];\)\)}], "Input"], Cell[BoxData[ \(\(Table[{\(Denumerant[pcr]\)[ k], \(-\(Denumerant[pcr]\)[\(-\((pls + k)\)\)]\)}, {k, 0, 15}];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Beispiel 2", "Subsection"], Cell[BoxData[{ \(\(cns = {15, 21, 23};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\)}], "Input"], Cell[BoxData[{ \(\(pls = Plus @@ cns;\)\), "\[IndentingNewLine]", \(frb = Max[Position[Table[\(PartitionFunction[pcr]\)[n], {n, 0, 500}], 0] - 1]\)}], "Input"], Cell[BoxData[{ \(Block[{$DisplayFunction = Identity\ }, \[IndentingNewLine]rng = Range[0, Length[cns] - 1]; pol = Flatten[pcr[\([1]\)]] . Binomial[n + rng, rng]; \[IndentingNewLine]lp1 = Plot[pol, {n, \(-200\), 200}, PlotStyle \[Rule] {Thickness[0.005], RGBColor[1, 0, 0]}]; \[IndentingNewLine]den = Table[{n, \(Denumerant[pcr]\)[n]}, {n, \(-200\), 200}]; \[IndentingNewLine]lp2 = ListPlot[den, PlotStyle \[Rule] {PointSize[0.008], RGBColor[0, 0, 1]}];\[IndentingNewLine]]\), "\n", \(\(Show[lp1, lp2, ImageSize \[Rule] 6\ 72, TextStyle -> "\", GridLines \[Rule] {{\(-frb\) - pls, \(-pls\)/2, frb}, None}, PlotRange \[Rule] {\(-0.5\), 2}];\)\)}], "Input"], Cell[BoxData[ \(\(Table[{\(Denumerant[pcr]\)[ k], \(Denumerant[pcr]\)[\(-\((pls + k)\)\)]}, {k, 0, 15}];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Beispiel 3", "Subsection"], Cell[BoxData[{ \(\(cns = {15, 21, 23, 27, 35, 39};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier];\)]\)}], "Input"], Cell[BoxData[{ \(\(pls = Plus @@ cns;\)\), "\[IndentingNewLine]", \(frb = Max[Position[Table[\(Denumerant[pcr]\)[n], {n, 0, 500}], 0] - 1]\)}], "Input"], Cell[BoxData[{ \(Block[{$DisplayFunction = Identity\ }, \[IndentingNewLine]rng = Range[0, Length[cns] - 1]; pol = Flatten[pcr[\([1]\)]] . Binomial[n + rng, rng]; \[IndentingNewLine]lp1 = Plot[pol, {n, \(-300\), 200}, PlotStyle \[Rule] {Thickness[0.005], RGBColor[1, 0, 0]}]; \[IndentingNewLine]den = Table[{n, \(Denumerant[pcr]\)[n]}, {n, \(-300\), 200}]; \[IndentingNewLine]lp2 = ListPlot[den, PlotStyle \[Rule] {PointSize[0.01], RGBColor[0, 0, 1]}];\[IndentingNewLine]]\), "\[IndentingNewLine]", \(\(Show[lp1, lp2, ImageSize \[Rule] 8\ 72, TextStyle -> "\", GridLines \[Rule] {{\(-frb\) - pls, \(-pls\)/2, frb}, None}, PlotRange \[Rule] {\(-7\), 7}];\)\)}], "Input"], Cell[BoxData[ \(\(Table[{\(Denumerant[pcr]\)[ k], \(-\(Denumerant[pcr]\)[\(-\((pls + k)\)\)]\)}, {k, 0, 15}];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Beispiel 4", "Subsection"], Cell[BoxData[{ \(\(cns = Range[10];\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier];\)]\)}], "Input"], Cell[BoxData[ \(pls = Plus @@ cns; frb = \(-1\);\)], "Input"], Cell[BoxData[{ \(Block[{$DisplayFunction = Identity\ }, \[IndentingNewLine]rng = Range[0, Length[cns] - 1]; pol = Flatten[pcr[\([1]\)]] . Binomial[n + rng, rng]; \[IndentingNewLine]lp1 = Plot[pol, {n, \(-75\), 20}, PlotStyle \[Rule] {Thickness[0.005], RGBColor[1, 0, 0]}]; \[IndentingNewLine]den = Table[{n, \(Denumerant[pcr]\)[n]}, {n, \(-75\), 20}]; \[IndentingNewLine]lp2 = ListPlot[den, PlotStyle \[Rule] {PointSize[0.01], RGBColor[0, 0, 1]} (*\(,\)\(PlotJoined \[Rule] True\)*) ];\[IndentingNewLine]]\), "\[IndentingNewLine]", \(\(Show[lp1, lp2, ImageSize \[Rule] 9\ 72, TextStyle -> "\", GridLines \[Rule] {{\(-frb\) - pls, \(-pls\)/2, frb}, None}, PlotRange \[Rule] {\(-7\), 7}];\)\)}], "Input"], Cell[BoxData[ \(\(Table[{\(Denumerant[pcr]\)[ k], \ \(-\(Denumerant[pcr]\)[\(-\((pls + k)\)\)]\)}, {k, 0, 15}];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Beispiel 5", "Subsection"], Cell[BoxData[{ \(\(cns = Range[15];\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns, PartitionMethod \[Rule] PrimeFourier];\)]\)}], "Input"], Cell[BoxData[ \(pls = Plus @@ cns; frb = \(-1\);\)], "Input"], Cell[BoxData[{ \(Block[{$DisplayFunction = Identity\ }, \[IndentingNewLine]rng = Range[0, Length[cns] - 1]; pol = Flatten[pcr[\([1]\)]] . Binomial[n + rng, rng]; \[IndentingNewLine]lp1 = Plot[pol, {n, \(-140\), 20}, PlotStyle \[Rule] {Thickness[0.005], RGBColor[1, 0, 0]}]; \[IndentingNewLine]den = Table[{n, \(Denumerant[pcr]\)[n]}, {n, \(-140\), 20}]; \[IndentingNewLine]lp2 = ListPlot[den, PlotStyle \[Rule] {PointSize[0.01], RGBColor[0, 0, 1]}];\[IndentingNewLine]]\), "\[IndentingNewLine]", \(\(Show[lp1, lp2, ImageSize \[Rule] 9\ 72, TextStyle -> "\", GridLines \[Rule] {{\(-frb\) - pls, \(-pls\)/2, frb}, None}, PlotRange \[Rule] {\(-1\), 7}];\)\)}], "Input"], Cell[BoxData[ \(\(Table[{\(Denumerant[pcr]\)[ k], \ \(Denumerant[pcr]\)[\(-\((pls + k)\)\)]}, {k, 0, 15}];\)\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Benchmarks", "Section"], Cell[BoxData[{ \(\(cns = {1, 2, 5, 10, 20, 50, 100, 200};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(\(cns = {1, 2, 5, 10, 20, 50, 100, 200, 500};\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(\(cns = Range[10];\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(\(cns = Range[15];\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(\(cns = Range[20];\)\), "\[IndentingNewLine]", \(Timing[\(pcr = PartitionData[cns];\)]\), "\[IndentingNewLine]", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(cns = Table[Random[Integer, {100, 999}], {5}]\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\), "\n", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(cns = Table[Random[Integer, {100, 999}], {10}]\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\ (*\ 203.67\ Second\ *) \), "\n", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(cns = Table[Random[Integer, {100, 999}], {15}]\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\ (*\ 499.5\ Second\ *) \), "\n", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(cns = Table[Random[Integer, {100, 999}], {20}]\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\ (*\ 989.6\ Second\ *) \), "\n", \({cns, pcr} >> "\"\)}], "Input"], Cell[BoxData[{ \(cns = Table[Random[Integer, {1000, 9999}], {10}]\), "\n", \(Timing[\(pcr = PartitionData[cns];\)]\ (*\ 30884.1\ Second\ *) \), "\n", \({cns, pcr} >> "\"\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Introduction", "Section"], Cell[CellGroupData[{ Cell["PrettyTable", "Subsection"], Cell[BoxData[{ \(Needs["\"]\), "\n", \(Needs["\"]\)}], "Input", InitializationCell->True], Cell[BoxData[ \(PrettyTable[m_List, opts___] \ := \[IndentingNewLine]DisplayForm[\[IndentingNewLine]StyleBox[\ \[IndentingNewLine]GridBox[\[IndentingNewLine]Map[ToBoxes, m, {2}], \[IndentingNewLine]Evaluate[ FilterOptions[GridBox, opts]], \[IndentingNewLine]GridFrame \[Rule] 2, \[IndentingNewLine]RowLines \[Rule] {1, 0}, \[IndentingNewLine]ColumnLines \[Rule] {1, 0}\[IndentingNewLine]], \[IndentingNewLine]Evaluate[ FilterOptions[StyleBox, opts]], \[IndentingNewLine]Background \[Rule] GrayLevel[0.8]\[IndentingNewLine]]\[IndentingNewLine]]\)], "Input",\ InitializationCell->True] }, Closed]], Cell[CellGroupData[{ Cell["Circulator", "Subsection"], Cell[BoxData[ \(Periode[d_Integer?Positive] := Table[d\ DiscreteDelta[Mod[n, d]] - 1, {n, 0, d - 1}]\)], "Input", InitializationCell->True], Cell[BoxData[ \(PrimePeriode[ p_Integer?Positive] := \[IndentingNewLine]Module[{d, tab}, \[IndentingNewLine]tab = \(\((MoebiusMu[p/#] Periode[#])\) &\) /@ Divisors[p]; \[IndentingNewLine]Plus @@ PadRight[tab, {Length[tab], p}, tab]\[IndentingNewLine]]\)], "Input",\ InitializationCell->True], Cell[BoxData[ \(Sawtooth[{p_Integer?Positive, q_Integer?Positive}] := \[IndentingNewLine]Module[{gcd = GCD[p, q], inv}, \[IndentingNewLine]inv = PowerMod[q/gcd, \(-1\), p/gcd]; \[IndentingNewLine]Table[\(-\((inv\ n/ p - \[LeftFloor]inv\ n/p\[RightFloor] - 1/2 + gcd/\((2 p)\))\)\) DiscreteDelta[Mod[n, gcd]], {n, 0, p - 1}]\[IndentingNewLine]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(PrimeSawtooth[{p_Integer?Positive, q_Integer? Positive}] := \[IndentingNewLine]Module[{pcr}, \ \[IndentingNewLine]pcr = \(\((MoebiusMu[p/#] \((#/p)\) Sawtooth[{#, q}])\) &\) /@ Divisors[p]; \[IndentingNewLine]Plus @@ PadRight[pcr, {Length[pcr], p}, pcr]\[IndentingNewLine]]\)], "Input",\ InitializationCell->True], Cell[BoxData[ \(Circulator[ a_List] := \[IndentingNewLine]Module[{p = First[a], tab}, \[IndentingNewLine]tab = Table[Sawtooth[{p, a[\([k]\)]}], {k, 2, Length[a]}]; \[IndentingNewLine]Fold[ ListConvolve[#1, #2, {1, 1}] &, {1}, tab]\[IndentingNewLine]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(PrimeCirculator[ a_List] := \[IndentingNewLine]Module[{p = First[a], tab}, \[IndentingNewLine]tab = Table[PrimeSawtooth[{p, a[\([k]\)]}], {k, 2, Length[a]}]; \[IndentingNewLine]Fold[ ListConvolve[#1, #2, {1, 1}] &, {1}, tab]\[IndentingNewLine]]\)], "Input", InitializationCell->True] }, Closed]], Cell[CellGroupData[{ Cell["Laurent", "Subsection"], Cell[BoxData[ \(Laurent[cns_List, d_Integer] := \[IndentingNewLine]Module[{rng, wur, lau, z}, \[IndentingNewLine]rng = Range[Count[Mod[cns, d], 0]]; \[IndentingNewLine]wur = If[OddQ[d], \(-\((\(-1\))\)^\((1/d)\)\), \((\(-1\))\)^\((2/ d)\)]; \[IndentingNewLine]lau = Series[\((Times @@ \((1 - z^cns)\))\)^\(-1\), {z, wur, \(-1\)}]; \[IndentingNewLine]Expand[ Coefficient[lau, z - wur, \(-rng\)]/\((\(-wur\))\)^ rng]\[IndentingNewLine]]\)], "Input", InitializationCell->True], Cell[BoxData[{ \(\(\(SymbolicLaurent[cns_List, 1, \[Omega]_] := \[IndentingNewLine]Module[{m, z, den}, \[IndentingNewLine]m = Length[cns]; \[IndentingNewLine]den = Times @@ \(Plus @@@ \((z^\((Range[cns] - 1)\))\)\); \[IndentingNewLine]Table[ Expand[\((\(-1\))\)^\((m - j)\)/\(\((m - j)\)!\) \((D[ den^\(-1\), {z, m - j}] /. z \[Rule] 1)\)], {j, m}]\[IndentingNewLine]]\)\(\n\) \)\), "\[IndentingNewLine]", \(SymbolicLaurent[cns_List, d_Integer, \[Omega]_] := \[IndentingNewLine]Module[{div, com, m, z, den}, \[IndentingNewLine]div = Cases[cns/d, _Integer]; com = cns /. Thread[d\ div \[RuleDelayed] Sequence[]]; m = Length[div]; \[IndentingNewLine]den = Times @@ \(Plus @@@ \((z^\((d\ Range[div] - d)\))\)\) Times @@ \((1 - z^com)\) Sum[\((z/\[Omega])\)^i, {i, 0, d - 1}]^ m; \[IndentingNewLine]Table[\[IndentingNewLine]Expand[\((\(-\ \[Omega]\))\)^\((m - j)\)/\(\((m - j)\)!\) \((D[den^\(-1\), {z, m - j}] /. z \[Rule] \[Omega])\)] /. \[Omega]^e_ \[Rule] \[Omega]^ Mod[e, d], {j, m}\[IndentingNewLine]]\[IndentingNewLine]]\)}], "Input", InitializationCell->True] }, Closed]], Cell[CellGroupData[{ Cell["Apart", "Subsection"], Cell[BoxData[{ \(\(cns = {1, 2, 3};\)\), "\[IndentingNewLine]", \(PrimeFourierData[cns]\)}], "Input"], Cell[BoxData[{ \(d = 3; m = 1;\), "\[IndentingNewLine]", \(apt = Apart[\((Times @@ \((1 - z^cns)\))\)^\(-1\)]\), "\n", \(HoldForm[\((2 - z - z^2)\)]/ HoldForm[9 \((1 - z^3)\)]\), "\[IndentingNewLine]", \(CoefficientList[Series[apt[\([\(-1\)]\)], {z, 0, 2 d - 1}], z]\), "\[IndentingNewLine]", \(pol = Evaluate[Cyclotomic[d, #]] &\), "\n", \(ftr = Evaluate[First[SymbolicLaurent[cns, d, #]] #^\(-n\)] &\), "\n", \(Table[Simplify[RootSum[pol, ftr]], {n, 0, d - 1}]\), "\n", \({ftr1 = Evaluate[#^\(-n\)/\((d \((1 - #)\))\)] &, ftr2 = Evaluate[#^\(-n\)/\((d \((1 - #^2)\))\)] &}\), "\ \[IndentingNewLine]", \({Table[Simplify[RootSum[pol, ftr1]], {n, 0, d - 1}], Table[Simplify[RootSum[pol, ftr2]], {n, 0, d - 1}]}\), "\[IndentingNewLine]", \(\({l1 = Sawtooth[{3, 1}], l2 = Sawtooth[{3, 2}]};\)\), "\n", \(\(ListConvolve[l1, l2, {1, 1}];\)\), "\n", \(\(Circulator[{3, 1, 2}];\)\)}], "Input"], Cell[BoxData[{ \(d = 3; m = 1;\), "\[IndentingNewLine]", \(pol = Expand[Factor[ apt[\([\(-1\)]\)] \((1 - z^d)\)^m]]\), "\[IndentingNewLine]", \(Sum[ Coefficient[pol, z, j] SymbolicBinomial[m - 1 + \((n - j)\)/d, m - 1], {j, 0, m\ d - 1}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Poles ", "Subsection"], Cell[BoxData[{ \(\(cns = {3, 4, 5};\)\), "\n", \({div = Union @@ Divisors[cns], mul = \(Count[Mod[cns, #], 0] &\) /@ div, phi = EulerPhi[div]}\), "\n", \({Plus @@ cns, mul . phi}\), "\n", \(\(sol = \(\((z /. NSolve[1 - z^# \[Equal] 0, z])\) &\) /@ cns;\)\), "\n", \(\(grt = \[IndentingNewLine]Graphics[\[IndentingNewLine]{\ \[IndentingNewLine]PointSize[ 0.0175], \[IndentingNewLine]Table[{Hue[ 1/k], \(Point[{Re[#], Im[#]}] &\) /@ sol[\([k]\)]}, {k, Length[cns]}]\[IndentingNewLine]}\[IndentingNewLine]];\)\), "\ \n", \(\(big = Graphics[{PointSize[0.035], RGBColor[1, 1, 0], Point[{1, 0}]}];\)\), "\n", \(\(Show[grt, big, AspectRatio \[Rule] Automatic, Axes \[Rule] True, Ticks \[Rule] None, ImageSize \[Rule] 72\ 5];\)\)}], "Input"], Cell[BoxData[{ \(\(cns = {15, 21, 23};\)\), "\n", \({div = Union @@ Divisors[cns], mul = \(Count[Mod[cns, #], 0] &\) /@ div, phi = EulerPhi[div]}\), "\n", \({Plus @@ cns, mul . phi}\), "\n", \(\(cns = {15, 21, 23};\)\), "\n", \(\(sol = \(\((z /. NSolve[1 - z^# \[Equal] 0, z])\) &\) /@ cns;\)\), "\n", \(\(grt = \[IndentingNewLine]Graphics[\[IndentingNewLine]{\ \[IndentingNewLine]PointSize[ 0.0175], \[IndentingNewLine]Table[{Hue[ 1/k], \(Point[{Re[#], Im[#]}] &\) /@ sol[\([k]\)]}, {k, Length[cns]}]\[IndentingNewLine]}\[IndentingNewLine]];\)\), "\ \n", \(\(big = Graphics[{PointSize[0.035], RGBColor[1, 1, 0], Point[{1, 0}]}];\)\), "\n", \(\(Show[grt, big, AspectRatio \[Rule] Automatic, Axes \[Rule] True, Ticks \[Rule] None, ImageSize \[Rule] 72\ 5];\)\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Sawtooth as an Inverse Discrete Fourier Transform", "Subsection", TextAlignment->Left, TextJustification->0], Cell[BoxData[ \(\(\( (*\ Sawtooth\ one\ *) \)\(\[IndentingNewLine]\)\(sz1[x_] := 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ /; \ \ \ Element[x, Integers]\[IndentingNewLine] sz1[x_] := x - \[LeftFloor]x\[RightFloor] - 1/2 /; \[Not] Element[x, Integers]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ Sawtooth\ two\ *) \)\(\[IndentingNewLine]\)\(sz2[x_] := x - \[LeftFloor]x\[RightFloor] - 1/2\)\)\)], "Input"], Cell[BoxData[{ \(p = 5; k = 2;\), "\[IndentingNewLine]", \(\({Evaluate[Cyclotomic[p, #]] &, Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &};\)\), "\n", \(\(pol = If[PrimeQ[p], Evaluate[Cyclotomic[p, #]] &, Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &];\)\n (*\ Sawtooth\ one\ *) \), "\[IndentingNewLine]", \(Table[sz1[n/p], {n, 0, p - 1}]\), "\n", \(\(\(Table[ FullSimplify[\(1\/p\) RootSum[pol, \((#/\((1 - #)\) + 1/2)\) #^n &]], {n, 0, p - 1}]\)\(\[IndentingNewLine]\) \) (*\ Sawtooth\ two\ *) \), "\n", \(\(Table[ sz2[n/p] + 1/2\ DiscreteDelta[Mod[n, p]], {n, 0, p - 1}];\)\), "\n", \(\(tb = Table[{n, sz1[n/p]}, {n, 0, k\ p - 1}];\)\), "\n", \(Block[{$DisplayFunction = Identity}, \[IndentingNewLine]g1 = Plot[sz1[x/p], {x, 0, k\ p}, Ticks \[Rule] {Range[k\ p], tb[\([All, 2]\)]}]; \[IndentingNewLine]g2 = ListPlot[tb, PlotStyle \[Rule] {PointSize[0.02], RGBColor[1, 0, 0]}];\n]\), "\n", \(\(Show[g1, g2, ImageSize \[Rule] 72\ 8, PlotRange \[Rule] {\(-0.6\), 0.6}, TextStyle -> "\"];\)\)}], "Input"], Cell[BoxData[{ \(p = 5; k = 2;\), "\[IndentingNewLine]", \(\({Evaluate[Cyclotomic[p, #]] &, Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &};\)\), "\n", \(\(pol = If[PrimeQ[p], Evaluate[Cyclotomic[p, #]] &, Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &];\)\n (*\ Sawtooth\ one\ *) \), "\[IndentingNewLine]", \(\(Table[\(-\((sz1[n/p] + 1/\((2 p)\) - 1/2 DiscreteDelta[Mod[n, p]])\)\), {n, 0, p - 1}];\)\[IndentingNewLine] (*\ Sawtooth\ two\ *) \), "\n", \(Table[\(-\((sz2[n/p] + 1/\((2 p)\))\)\), {n, 0, p - 1}]\), "\n", \(\(\(Table[ FullSimplify[\(1\/p\) RootSum[pol, #^\(-n\)/\((1 - #)\) &]], {n, 0, p - 1}]\)\(\[IndentingNewLine]\) \) (*\ Plot\ *) \), "\n", \(\(tb = Table[{n, \(-\((sz2[n/p] + 1/\((2 p)\))\)\)}, {n, 0, k\ p - 1}];\)\), "\n", \(Block[\[IndentingNewLine]{$DisplayFunction = Identity}, \n\ \ \ g1 = Plot[\(-\((sz2[x/p] + 1/\((2 p)\))\)\), {x, 0, k\ p}, Ticks \[Rule] {Range[k\ p], tb[\([All, 2]\)]}]; \[IndentingNewLine]g2 = ListPlot[tb, PlotStyle \[Rule] {PointSize[0.02], RGBColor[0, 0, 1]}];\n]\), "\n", \(\(Show[g1, g2, ImageSize \[Rule] 72\ 8, PlotRange \[Rule] {\(-0.6\), 0.6}, TextStyle -> "\"];\)\)}], "Input"], Cell[BoxData[ \(\(\( (*\ Difference\ between\ sz1\ and\ sz2\ *) \)\(\[IndentingNewLine]\)\(\(p = 5;\)\[IndentingNewLine] Table[sz1[n/p], {n, 0, p - 1}] - Table[sz2[n/p], {n, 0, p - 1}]\[IndentingNewLine] Table[ FullSimplify[RootSum[\((1 - #^p)\) &, #^n &]]/\((2 p)\), {n, 0, p - 1}]\[IndentingNewLine] Table[DiscreteDelta[Mod[n, p]]/2, {n, 0, p - 1}]\)\)\)], "Input"], Cell[BoxData[{ \(Table[sz1[n/p], {n, 0, p - 1}]\), "\[IndentingNewLine]", \(Table[ sz2[n/p] + 1/2\ DiscreteDelta[Mod[n, p]], {n, 0, p - 1}]\)}], "Input"], Cell[BoxData[{ \(Table[ sz1[n/p] - 1/2 DiscreteDelta[Mod[n, p]], {n, 0, p - 1}]\), "\[IndentingNewLine]", \(Table[sz2[n/p], {n, 0, p - 1}]\)}], "Input"], Cell[BoxData[{ \(Table[\(-\((sz1[n/p] + 1/\((2 p)\) - 1/2 DiscreteDelta[Mod[n, p]])\)\), {n, 0, p - 1}]\), "\[IndentingNewLine]", \(Table[\(-\((sz2[n/p] + 1/\((2 p)\))\)\), {n, 0, p - 1}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["PrimeSawtooth Computation via Moebius-Inversion", "Subsection"], Cell[BoxData[ \(\(\( (*\ Periode\ and\ PrimePeriode\ *) \)\(\[IndentingNewLine]\)\(\(p = 15;\)\[IndentingNewLine] \(pol = Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &;\)\[IndentingNewLine] Table[ FullSimplify[RootSum[pol, #^\(-n\) &]], {n, 0, p - 1}]\[IndentingNewLine] Periode[p]\[IndentingNewLine] \(pol = Evaluate[Cyclotomic[p, #]] &;\)\[IndentingNewLine] Table[ FullSimplify[RootSum[pol, #^\(-n\) &]], {n, 0, p - 1}]\[IndentingNewLine] PrimePeriode[p]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ \(Periode\ is\ a\ sum\ of\ PrimePeriode\.b4s\)\(,\)\ *) \)\(\ \[IndentingNewLine]\)\(\(p = 15;\)\[IndentingNewLine] \(tab = Table[DiscreteDelta[Mod[p, d]] PrimePeriode[d], {d, p}];\)\[IndentingNewLine] \(tab = PadRight[tab, {Length[tab], p}, tab];\)\[IndentingNewLine] \(mat = Append[tab, Plus @@ tab];\)\[IndentingNewLine] \(mat = Transpose[ Prepend[Transpose[mat], Range[p] \[Union] {"\<\[CapitalSigma]\>"}]];\)\[IndentingNewLine] \(lst = Last[IdentityMatrix[p]];\)\[IndentingNewLine] PrettyTable[mat, RowLines \[Rule] lst, ColumnLines \[Rule] Reverse[lst], FontSize \[Rule] 15]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ so, \ PrimePeriode\ can\ be\ computed\ via\ Moebius - Inversion\ *) \)\(\[IndentingNewLine]\)\(\(p = 15;\)\[IndentingNewLine] \(tab = Table[DiscreteDelta[Mod[p, d]] MoebiusMu[p/d] Periode[d], {d, p}];\)\[IndentingNewLine] \(tab = PadRight[tab, {Length[tab], p}, tab];\)\[IndentingNewLine] \(mat = Append[tab, Plus @@ tab];\)\[IndentingNewLine] \(mat = Transpose[ Prepend[Transpose[mat], Range[p] \[Union] {"\<\[CapitalSigma]\>"}]];\)\[IndentingNewLine] \(lst = Last[IdentityMatrix[p]];\)\[IndentingNewLine] PrettyTable[mat, RowLines \[Rule] lst, ColumnLines \[Rule] Reverse[lst], FontSize \[Rule] 15]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ Sawtooth\ and\ PrimeSawtooth\ *) \)\(\[IndentingNewLine]\)\(\({p, q} = {15, 1};\)\[IndentingNewLine] Sawtooth[{p, q}]\[IndentingNewLine] \(pol = Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &;\)\[IndentingNewLine] Table[ FullSimplify[\(1\/p\) RootSum[pol, #^\(-n\)/\((1 - #^q)\) &]], {n, 0, p - 1}]\[IndentingNewLine] PrimeSawtooth[{p, q}]\[IndentingNewLine] \(pol = Evaluate[Cyclotomic[p, #]] &;\)\[IndentingNewLine] Table[ FullSimplify[\(1\/p\) RootSum[pol, #^\(-n\)/\((1 - #^q)\) &]], {n, 0, p - 1}]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ \(Sawtooth\ is\ a\ sum\ of\ PrimeSawtooth\.b4s\)\(,\)\ *) \)\(\ \[IndentingNewLine]\)\(\({p, q} = {15, 1};\)\[IndentingNewLine] \(pcr = Table[DiscreteDelta[Mod[p, d]] d/p\ PrimeSawtooth[{d, q}], {d, p}];\)\[IndentingNewLine] \(pcr = PadRight[pcr, {Length[pcr], p}, pcr];\)\[IndentingNewLine] \(mat = Append[pcr, Plus @@ pcr];\)\[IndentingNewLine] \(mat = Transpose[ Prepend[Transpose[mat], Range[p] \[Union] {"\<\[CapitalSigma]\>"}]];\)\[IndentingNewLine] \(lst = Last[IdentityMatrix[p]];\)\[IndentingNewLine] PrettyTable[mat, RowLines \[Rule] lst, ColumnLines \[Rule] Reverse[lst], FontSize \[Rule] 15]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ so, \ PrimeSawtooth\ can\ be\ computed\ via\ Moebius - Inversion\ *) \)\(\[IndentingNewLine]\)\(\({p, q} = {15, 1};\)\[IndentingNewLine] \(pcr = Table[DiscreteDelta[Mod[p, d]] MoebiusMu[p/d] d/p\ Sawtooth[{d, q}], {d, p}];\)\[IndentingNewLine] \(pcr = PadRight[pcr, {Length[pcr], p}, pcr];\)\[IndentingNewLine] \(mat = Append[pcr, Plus @@ pcr];\)\[IndentingNewLine] \(mat = Transpose[ Prepend[Transpose[mat], Range[p] \[Union] {"\<\[CapitalSigma]\>"}]];\)\[IndentingNewLine] \(lst = Last[IdentityMatrix[p]];\)\[IndentingNewLine] PrettyTable[mat, RowLines \[Rule] lst, ColumnLines \[Rule] Reverse[lst], FontSize \[Rule] 15]\)\)\)], "Input"], Cell[BoxData[ \(\(\( (*\ or\ *) \)\(\[IndentingNewLine]\)\(\(pcr = \(\((MoebiusMu[ p/#] \((#/p)\)\ Sawtooth[{#, q}])\) &\) /@ Divisors[p];\)\[IndentingNewLine] Plus @@ PadRight[pcr, {Length[pcr], p}, pcr]\)\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Convolution", "Subsection"], Cell[BoxData[{ \(p = 5; q = 2; r = 3;\), "\[IndentingNewLine]", \(\(pol = Evaluate[Cyclotomic[p, #]] &;\)\), "\[IndentingNewLine]", \(Table[ FullSimplify[\(1\/p\) RootSum[pol, #^\(-n\)/\((\((1 - #^q)\) \((1 - #^r)\))\) &]], {n, 0, p - 1}]\)}], "Input"], Cell[BoxData[{ \(\(cpq = Circulator[{p, q}];\)\), "\[IndentingNewLine]", \(\(cpr = Circulator[{p, r}];\)\), "\[IndentingNewLine]", \(ListConvolve[cpq, cpr, {1, 1}]\), "\[IndentingNewLine]", \(Circulator[{p, q, r}]\)}], "Input"], Cell[BoxData[{ \(p = 6; q = 2; r = 5;\), "\[IndentingNewLine]", \(\(cpq = PrimeCirculator[{p, q}];\)\), "\[IndentingNewLine]", \(\(cpr = PrimeCirculator[{p, r}];\)\), "\[IndentingNewLine]", \(ListConvolve[cpq, cpr, {1, 1}]\), "\[IndentingNewLine]", \(PrimeCirculator[{p, q, r}]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Fourier - Transformation", "Subsection"], Cell[BoxData[{ \(p = 5; q = 1; r = 4;\), "\[IndentingNewLine]", \(tf = {PrimeSawtooth[{p, q}], PrimeSawtooth[{p, r}]}\), "\n", \(ft = Chop[Fourier[tf, FourierParameters \[Rule] {\(-1\), 1}]]\), "\n", \(rt = Rationalize[InverseFourier[ft, FourierParameters \[Rule] {\(-1\), 1}], 10^\(-10\)]\), "\[IndentingNewLine]", \(tf \[Equal] rt\)}], "Input"], Cell[BoxData[{ \(\(cns = {7, 11, 22};\)\), "\[IndentingNewLine]", \(p = First[cns]; rst = Rest[cns];\), "\[IndentingNewLine]", \(PrimeCirculator[cns]\), "\[IndentingNewLine]", \(tf = \(PrimeSawtooth[{p, #}] &\) /@ rst\), "\[IndentingNewLine]", \(\(ft = Chop[Fourier[tf, FourierParameters \[Rule] {\(-1\), 1}]];\)\), "\[IndentingNewLine]", \(rt = Rationalize[InverseFourier[ft, FourierParameters \[Rule] {\(-1\), 1}], 10^\(-10\)]\), "\[IndentingNewLine]", \(Fold[ListConvolve[#1, #2, {1, 1}] &, {1}, rt]\), "\[IndentingNewLine]", \(tf \[Equal] rt\)}], "Input"], Cell[BoxData[{ \(p = 5; q = 1; r = 3;\), "\n", \(\(tf = Sawtooth[{p, q}];\)\), "\n", \(tf = Circulator[{p, q, r}]\), "\[IndentingNewLine]", \(ft = Rationalize[ Chop[Fourier[tf, FourierParameters \[Rule] {\(-1\), 1}]]]\), "\n", \(\(rm = Max[Abs[ft]];\)\), "\n", \(\(Show[\[IndentingNewLine]Graphics[\[IndentingNewLine]{\ \[IndentingNewLine]Circle[{0, 0}, rm + 0.0075], \[IndentingNewLine]PointSize[ 0.02], RGBColor[1, 0, 0], \(Point[{Re[#], Im[#]}] &\) /@ ft\[IndentingNewLine]}\[IndentingNewLine]], \ \[IndentingNewLine]Axes \[Rule] True, \[IndentingNewLine]ImageSize \[Rule] 72\ 5, \[IndentingNewLine]AspectRatio \[Rule] Automatic, \[IndentingNewLine]PlotRange \[Rule] {{\(-rm\) - 0.01, rm + 0.01}, {\(-rm\) - 0.01, rm + 0.01}}\[IndentingNewLine]];\)\)}], "Input"], Cell[BoxData[{ \(p = 5; q = 1; r = 3; \[Omega] = \[ExponentialE]^\((2 \[Pi]\ \[ImaginaryI]/ p)\);\), "\[IndentingNewLine]", \(tf = Circulator[{p, q, r}]\), "\[IndentingNewLine]", \(s1 = Chop[Rest[ Fourier[tf, FourierParameters \[Rule] {\(-1\), 1}]]]\), "\[IndentingNewLine]", \(s2 = Chop[Table[\(1\/p\) N[1/\((\((1 - \((\[Omega]^k)\)^q)\) \((1 - \((\[Omega]^k)\)^ r)\))\)], {k, p - 1}]]\), "\[IndentingNewLine]", \(s1 \[Equal] s2\)}], "Input"], Cell[BoxData[ \(Table[ Rationalize[ Chop[Sum[\(1\/p\) N[\((\[Omega]^ k)\)^\(-n\)/\((\((1 - \((\[Omega]^k)\)^ q)\) \((1 - \((\[Omega]^k)\)^r)\))\)], {k, p - 1}]]], {n, 0, p - 1}]\)], "Input"] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for Microsoft Windows", ScreenRectangle->{{0, 1024}, {0, 723}}, AutoGeneratedPackage->None, WindowToolbars->"EditBar", WindowSize->{792, 500}, WindowMargins->{{Automatic, 84}, {29, Automatic}}, ShowSelection->True ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1776, 53, 47, 0, 95, "Title"], Cell[1826, 55, 28, 0, 51, "Subtitle"], Cell[1857, 57, 38, 0, 30, "Subsubtitle"], Cell[CellGroupData[{ Cell[1920, 61, 24, 0, 73, "Section"], Cell[1947, 63, 140, 3, 30, "Input", InitializationCell->True], Cell[2090, 68, 101, 2, 30, "Input", InitializationCell->True], Cell[2194, 72, 408, 7, 70, "Input", InitializationCell->True] }, Open ]], Cell[CellGroupData[{ Cell[2639, 84, 30, 0, 73, "Section"], Cell[2672, 86, 68, 1, 30, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[2777, 92, 24, 0, 43, "Section"], Cell[CellGroupData[{ Cell[2826, 96, 30, 0, 38, "Subsection"], Cell[2859, 98, 54, 1, 30, "Input"], Cell[2916, 101, 185, 4, 70, "Input"], Cell[3104, 107, 62, 1, 30, "Input"], Cell[3169, 110, 354, 6, 70, "Input"], Cell[3526, 118, 190, 3, 70, "Input"], Cell[3719, 123, 196, 3, 70, "Input"], Cell[3918, 128, 125, 2, 50, "Input"], Cell[4046, 132, 126, 2, 50, "Input"], Cell[4175, 136, 153, 3, 50, "Input"], Cell[4331, 141, 151, 2, 50, "Input"], Cell[4485, 145, 112, 2, 50, "Input"], Cell[4600, 149, 220, 4, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[4857, 158, 38, 0, 30, "Subsection"], Cell[4898, 160, 342, 6, 90, "Input"], Cell[5243, 168, 322, 6, 90, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[5602, 179, 28, 0, 30, "Subsection"], Cell[5633, 181, 45, 1, 30, "Input"], Cell[5681, 184, 299, 6, 87, "Input"], Cell[5983, 192, 255, 4, 90, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[6275, 201, 29, 0, 30, "Subsection"], Cell[6307, 203, 76, 1, 30, "Input"], Cell[6386, 206, 418, 9, 110, "Input"], Cell[6807, 217, 185, 3, 70, "Input"], Cell[6995, 222, 183, 3, 70, "Input"], Cell[7181, 227, 385, 9, 90, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[7603, 241, 28, 0, 30, "Subsection"], Cell[7634, 243, 45, 1, 30, "Input"], Cell[7682, 246, 161, 3, 70, "Input"], Cell[7846, 251, 80, 1, 30, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[7963, 257, 28, 0, 30, "Subsection"], Cell[7994, 259, 46, 1, 30, "Input"], Cell[8043, 262, 211, 4, 90, "Input"], Cell[8257, 268, 243, 4, 90, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[8537, 277, 26, 0, 30, "Subsection"], Cell[8566, 279, 43, 1, 30, "Input"], Cell[8612, 282, 278, 5, 90, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[8927, 292, 27, 0, 30, "Subsection"], Cell[8957, 294, 44, 1, 30, "Input"], Cell[9004, 297, 233, 4, 90, "Input"], Cell[9240, 303, 131, 2, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[9408, 310, 32, 0, 30, "Subsection"], Cell[9443, 312, 49, 1, 30, "Input"], Cell[9495, 315, 204, 4, 90, "Input"], Cell[9702, 321, 111, 2, 50, "Input"], Cell[9816, 325, 130, 2, 50, "Input"], Cell[9949, 329, 123, 2, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10109, 336, 31, 0, 30, "Subsection"], Cell[10143, 338, 48, 1, 30, "Input"], Cell[10194, 341, 237, 4, 90, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10468, 350, 29, 0, 30, "Subsection"], Cell[10500, 352, 46, 1, 30, "Input"], Cell[10549, 355, 324, 6, 110, "Input"], Cell[10876, 363, 196, 4, 70, "Input"], Cell[11075, 369, 193, 4, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[11305, 378, 38, 0, 30, "Subsection"], Cell[11346, 380, 102, 2, 50, "Input"], Cell[11451, 384, 349, 5, 110, "Input"], Cell[11803, 391, 370, 6, 110, "Input"], Cell[12176, 399, 66, 1, 30, "Input"], Cell[12245, 402, 546, 12, 110, "Input"], Cell[12794, 416, 66, 1, 30, "Input"], Cell[12863, 419, 424, 9, 90, "Input"], Cell[13290, 430, 61, 1, 30, "Input"], Cell[13354, 433, 776, 17, 150, "Input"], Cell[14133, 452, 373, 6, 130, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[14543, 463, 27, 0, 30, "Subsection"], Cell[14573, 465, 73, 1, 30, "Input"], Cell[14649, 468, 125, 2, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[14811, 475, 33, 0, 30, "Subsection"], Cell[14847, 477, 60, 1, 30, "Input"], Cell[14910, 480, 131, 2, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[15078, 487, 32, 0, 30, "Subsection"], Cell[15113, 489, 209, 3, 70, "Input"], Cell[15325, 494, 273, 5, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[15635, 504, 34, 0, 30, "Subsection"], Cell[15672, 506, 134, 2, 50, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[15855, 514, 24, 0, 43, "Section"], Cell[CellGroupData[{ Cell[15904, 518, 32, 0, 38, "Subsection"], Cell[15939, 520, 123, 2, 50, "Input"], Cell[16065, 524, 186, 4, 50, "Input"], Cell[16254, 530, 841, 16, 190, "Input"], Cell[17098, 548, 151, 3, 30, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[17286, 556, 32, 0, 38, "Subsection"], Cell[17321, 558, 129, 2, 50, "Input"], Cell[17453, 562, 186, 4, 50, "Input"], Cell[17642, 568, 822, 16, 170, "Input"], Cell[18467, 586, 146, 3, 30, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[18650, 594, 32, 0, 38, "Subsection"], Cell[18685, 596, 203, 4, 50, "Input"], Cell[18891, 602, 179, 4, 50, "Input"], Cell[19073, 608, 853, 17, 170, "Input"], Cell[19929, 627, 151, 3, 30, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[20117, 635, 32, 0, 38, "Subsection"], Cell[20152, 637, 188, 4, 50, "Input"], Cell[20343, 643, 65, 1, 30, "Input"], Cell[20411, 646, 885, 17, 170, "Input"], Cell[21299, 665, 153, 3, 30, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[21489, 673, 32, 0, 38, "Subsection"], Cell[21524, 675, 188, 4, 50, "Input"], Cell[21715, 681, 65, 1, 30, "Input"], Cell[21783, 684, 851, 17, 170, "Input"], Cell[22637, 703, 148, 3, 30, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[22834, 712, 29, 0, 43, "Section"], Cell[22866, 714, 213, 3, 70, "Input"], Cell[23082, 719, 229, 4, 70, "Input"], Cell[23314, 725, 193, 3, 70, "Input"], Cell[23510, 730, 193, 3, 70, "Input"], Cell[23706, 735, 193, 3, 70, "Input"], Cell[23902, 740, 184, 3, 70, "Input"], Cell[24089, 745, 219, 4, 70, "Input"], Cell[24311, 751, 218, 4, 70, "Input"], Cell[24532, 757, 218, 4, 70, "Input"], Cell[24753, 763, 222, 4, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[25012, 772, 31, 0, 43, "Section"], Cell[CellGroupData[{ Cell[25068, 776, 33, 0, 38, "Subsection"], Cell[25104, 778, 163, 3, 50, "Input", InitializationCell->True], Cell[25270, 783, 734, 15, 290, "Input", InitializationCell->True] }, Closed]], Cell[CellGroupData[{ Cell[26041, 803, 32, 0, 30, "Subsection"], Cell[26076, 805, 152, 3, 30, "Input", InitializationCell->True], Cell[26231, 810, 347, 7, 110, "Input", InitializationCell->True], Cell[26581, 819, 489, 9, 110, "Input", InitializationCell->True], Cell[27073, 830, 402, 9, 110, "Input", InitializationCell->True], Cell[27478, 841, 361, 8, 110, "Input", InitializationCell->True], Cell[27842, 851, 371, 8, 110, "Input", InitializationCell->True] }, Closed]], Cell[CellGroupData[{ Cell[28250, 864, 29, 0, 30, "Subsection"], Cell[28282, 866, 589, 11, 150, "Input", InitializationCell->True], Cell[28874, 879, 1314, 23, 330, "Input", InitializationCell->True] }, Closed]], Cell[CellGroupData[{ Cell[30225, 907, 27, 0, 30, "Subsection"], Cell[30255, 909, 110, 2, 50, "Input"], Cell[30368, 913, 984, 18, 270, "Input"], Cell[31355, 933, 306, 8, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[31698, 946, 28, 0, 30, "Subsection"], Cell[31729, 948, 872, 18, 270, "Input"], Cell[32604, 968, 915, 19, 290, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[33556, 992, 118, 2, 30, "Subsection"], Cell[33677, 996, 319, 6, 70, "Input"], Cell[33999, 1004, 145, 2, 50, "Input"], Cell[34147, 1008, 1222, 26, 306, "Input"], Cell[35372, 1036, 1386, 28, 346, "Input"], Cell[36761, 1066, 422, 9, 110, "Input"], Cell[37186, 1077, 168, 3, 50, "Input"], Cell[37357, 1082, 177, 4, 50, "Input"], Cell[37537, 1088, 235, 4, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[37809, 1097, 69, 0, 30, "Subsection"], Cell[37881, 1099, 556, 14, 170, "Input"], Cell[38440, 1115, 711, 14, 170, "Input"], Cell[39154, 1131, 756, 16, 170, "Input"], Cell[39913, 1149, 628, 14, 201, "Input"], Cell[40544, 1165, 734, 14, 170, "Input"], Cell[41281, 1181, 780, 16, 170, "Input"], Cell[42064, 1199, 265, 5, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[42366, 1209, 33, 0, 30, "Subsection"], Cell[42402, 1211, 292, 6, 85, "Input"], Cell[42697, 1219, 246, 4, 90, "Input"], Cell[42946, 1225, 315, 5, 110, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[43298, 1235, 46, 0, 38, "Subsection"], Cell[43347, 1237, 386, 7, 110, "Input"], Cell[43736, 1246, 660, 14, 170, "Input"], Cell[44399, 1262, 890, 16, 350, "Input"], Cell[45292, 1280, 580, 14, 126, "Input"], Cell[45875, 1296, 290, 7, 66, "Input"] }, Closed]] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)