Restricted Partition Functions

Examples

Eckhard Manthei

Setup

SetDirectory[
        ToFileName[NotebookDirectory /. Options[$FrontEnd]]];

Get["RestrictedPartitionFunctions`"]

Off[General::"spell1", PartitionData::"pcr", 
      PartitionData::"sym", PartitionData::"aut", 
      PartitionData::"sym", PartitionData::"com", 
      PartitionData::"net", PartitionData::"rbs", 
      PartitionData::"syl", PartitionData::"new", 
      PartitionData::"pnd", PartitionData::"gkp"]

Information

?RestrictedPartitionFunctions`*

Tests

Overview

cns = {5, 7, 11};

pcr = 
      PartitionData[cns, PartitionMethod -> PrimeFourier]
pnd = NewtonDataL[cns]
rub = RubinsteinData[cns]

ColumnForm[MatrixForm /@ pcr]

{pcr[[1]], BinomialToNewton[pcr[[1]]], 
      BinomialToNormal[pcr[[1]]]}
{pnd[[1]], NewtonToBinomial[pnd[[1]]], 
      NewtonToNormal[pnd[[1]]]}
{rub[[1]], NormalToBinomial[rub[[1]]], 
      NormalToNewton[rub[[1]]]}

Denumerant[pcr][10^6]
NewtonDenumerant[pnd][10^6]
NormalDenumerant[rub][10^6]

Denumerant[pcr][10^120]
NewtonDenumerant[pnd][10^120]
NormalDenumerant[rub][10^120]

net = NettoData[cns, n]
Table[FullSimplify[net], {n, 25}]

gkp = GrahamData[cns];
GrahamDenumerant[gkp][10^6]

new = NewtonDataG[cns]; 
    MatrixForm[new[[1]]]
NewtonDenumerant[new][10^6]

bel = BellData[cns, n];
bel[[Mod[10^6, Length[bel]] + 1]] /. n -> 10^6

SylvesterData[cns, n]
RubinsteinData[cns, n]

ser = SertoezData[cns, n]
ser /. n -> 10^6 /. 
      z_ SymbolicBinomial[x_, y_] :> 
        z If[IntegerQ[x], Binomial[x, y], 0]

Series expansion

cns = {3, 4, 8, 8, 12, 32, 48, 97};
Timing[pcr = PartitionData[cns];]
VectorQ[tu = Table[Denumerant[pcr][n], {n, 0, 500}], 
      IntegerQ]
tu == Series[(Times @@ (1 - z^cns))^-1, {z, 0, 
            500}][[3]]

cns = Range[6];
Timing[pcr = PartitionData[cns];]
VectorQ[tu = Table[Denumerant[pcr][n], {n, 0, 500}], 
      IntegerQ]
tu == Series[(Times @@ (1 - z^cns))^-1, {z, 0, 
            500}][[3]]

Comtet

?Comtet*

cns = {1, 2, 3, 4};
com = 
        PartitionData[cns, 
          PartitionMethod -> Comtet];
MatrixForm /@ com
Table[Denumerant[com][n], {n, 0, 25}]

cns = {1, 2, 3, 4};
com = ComtetData[cns]; MatrixForm /@ com
ByteCount[com]
Table[Denumerant[com][n], {n, 0, 25}]

Fourier

?RestrictedPartitionFunctions`*Fourier*

cns = {1, 2, 3, 4};
pcr = PartitionData[cns]
pcr = 
      PartitionData[cns, 
        PartitionMethod -> PrimeFourier]
pcr = 
      PartitionData[cns, 
        PartitionMethod -> SymbolicFourier]
Table[Denumerant[pcr][n], {n, 0, 25}]

pcr = PrimeFourierData[cns]
ByteCount[pcr]
Table[Denumerant[pcr][n], {n, 0, 25}]

cns = {137, 251, 256};
Timing[pcr = PrimeFourierData[cns];]
ByteCount[pcr]

crc = PartitionData[cns];
pcr = 
        PartitionData[cns, 
          PartitionMethod -> PrimeFourier];
sym = 
        PartitionData[cns, 
          PartitionMethod -> 
            SymbolicFourier];
ColumnForm[MatrixForm /@ pcr]

Graham

?Graham*

cns = {1, 2, 3, 4};
gkp = GrahamData[cns]
ByteCount[gkp]

Table[GrahamDenumerant[gkp][n], {n, 0, 25}]

Newton

?*Newton*

cns = {1, 2, 3, 4};
MatrixForm[First[new = NewtonDataG[cns]]]
ByteCount[new]
Table[NewtonDenumerant[new][n], {n, 0, 25}]

cns = {1, 2, 3, 4};
pnd = NewtonDataL[cns]
ByteCount[pnd]
Table[NewtonDenumerant[pnd][n], {n, 0, 25}]

Bell

?Bell*

cns = {1, 2, 3, 4};
bel = BellData[cns, n]; MatrixForm[bel]
ByteCount[bel]
p = Length[bel]; 
    Table[bel[[Mod[n, p] + 1]], {n, 0, 25}]

Netto

?Netto*

cns = {1, 2, 3, 4};
net = NettoData[cns, n]
ByteCount[net]
Table[FullSimplify[net], {n, 0, 25}]

cns = {137, 251, 256};
Timing[net = NettoData[cns, n];]

Rubinstein

?Rubinstein*

cns = {1, 2, 3, 4};
rub = RubinsteinData[cns, n]
ByteCount[rub]
Table[FullSimplify[rub], {n, 0, 25}]

cns = {1, 2, 3, 4};
RubinsteinData[cns]

cns = {137, 251, 256};
Timing[RubinsteinData[cns, n];]

cns = Range[8];
Timing[RubinsteinData[cns, n];]

Sylvester

?Sylvester*

cns = {1, 2, 3, 4};
syl = SylvesterData[cns, n]
ByteCount[syl]
Table[FullSimplify[syl], {n, 0, 25}]

Sertoez

?Sertoez*

cns = {1, 2, 3, 4};
ser = SertoezData[cns, n]
ByteCount[ser]
Table[
      ser /. z_ SymbolicBinomial[x_, y_] :> 
          z If[IntegerQ[x], Binomial[x, y], 0], {n, 0, 25}]

cns = {137, 251, 
          256};

    Timing[SertoezData[cns, n];]

cns = 
        Range[5];

    Timing[ser = SertoezData[cns, n];]

Time comparisons

cns = {5, 7}
SylvesterData[cns, n]

cns = {11, 13, 15};
Timing[syl = SylvesterData[cns, n];]
Timing[rub = RubinsteinData[cns, n];]
Timing[ser = SertoezData[cns, n];]
Timing[net = NettoData[cns, n];]

Table[FullSimplify[syl], {n, 0, 25}]
Table[FullSimplify[rub], {n, 0, 25}]
Table[FullSimplify[net], {n, 0, 25}]
Table[
      ser /. z_ SymbolicBinomial[x_, y_] :> 
          z If[IntegerQ[x], Binomial[x, y], 0], {n, 0, 25}]

ByteCount /@ {syl, rub, net, ser}

cns = {11, 13, 15, 17};
Timing[crc = PartitionData[cns];]
Timing[pcr = 
          PartitionData[cns, 
            PartitionMethod -> 
              PrimeFourier];]
Timing[sym = 
          PartitionData[cns, 
            PartitionMethod -> 
              SymbolicFourier];]
Timing[com = 
          PartitionData[cns, PartitionMethod -> Comtet];]

ByteCount /@ {crc, pcr, sym, com}

cns = {11, 13};
Timing[new = 
          PartitionData[cns, 
            PartitionMethod -> NewtonG];]
Timing[pnd = 
          PartitionData[cns, 
            PartitionMethod -> NewtonL];]
Timing[gkp = 
          PartitionData[cns, PartitionMethod -> Graham];]

ByteCount /@ {new, pnd, gkp}

cns = {1, 5, 15, 17};
Timing[crc = PartitionData[cns];]
Timing[com = 
          PartitionData[cns, 
            PartitionMethod -> Comtet];]
Timing[pcr = 
          PartitionData[cns, 
            PartitionMethod -> 
              PrimeFourier];]
Timing[new = 
          PartitionData[cns, 
            PartitionMethod -> NewtonG];]
Timing[pnd = 
          PartitionData[cns, 
            PartitionMethod -> NewtonL];]
Timing[gkp = 
          PartitionData[cns, PartitionMethod -> Graham];]

Denumerant[crc][10^6]
Denumerant[pcr][10^6]
Denumerant[com][10^6]
NewtonDenumerant[pnd][10^6]
NewtonDenumerant[new][10^6]
GrahamDenumerant[gkp][10^6]

Euler

?RestrictedPartitionFunctions`Euler*

cns = {1, 2, 3, 4, 5};
EulerDenumerant[cns][10^3]

MatrixPower

?MatrixPowerDenumerant*

cns = {1, 2, 3, 4, 5};
MatrixPowerDenumerant[cns][10^3]

gcd(A) > 1

cns = {9, 15, 27, 105};
Timing[pcr = PartitionData[cns];]
Table[Denumerant[pcr][n], {n, 0, 120}]

cns = {9, 15, 27, 105}; gcd = GCD @@ cns
Timing[pcr = PartitionData[cns/gcd];]
Table[
      DiscreteDelta[Mod[n, gcd]] Denumerant[pcr][n/gcd], {n, 0, 
        120}]

PartialApart

cns = {2, 4, 5, 16, 25, 32, 64, 128};
PartialApart[cns, 16, z]

Plots

Beispiel 1

cns = {5, 7};
Timing[pcr = PartitionData[cns];]

pls = Plus @@ cns;
frb = 
      Max[Position[Table[PartitionFunction[pcr][n], {n, 0, 500}], 0] - 
          1]

Block[
{$DisplayFunction = 
          Identity }, 
rng = Range[0, Length[cns] - 1]; 
      pol = Flatten[pcr[[1]]] . 
          Binomial[n + rng, rng]; 
lp1 = 
        Plot[pol, {n, -100, 100}, 
          PlotStyle -> {Thickness[0.005], 
              RGBColor[1, 0, 0]}]; 
den = 
        Table[{n, Denumerant[pcr][n]}, {n, -100, 
            100}]; 
lp2 = 
        ListPlot[den, 
          PlotStyle -> {PointSize[0.008], 
              RGBColor[0, 0, 1]}];
]
Show[lp1, lp2, ImageSize -> 6 72, 
        TextStyle -> "Subsection", 
        GridLines -> {{-frb - pls, -pls/2, frb}, None}, 
        PlotRange -> {-3, 3}];

Table[{Denumerant[pcr][
            k], -Denumerant[pcr][-(pls + k)]}, {k, 0, 
          15}];

Beispiel 2

cns = {15, 21, 23};
Timing[pcr = PartitionData[cns];]

pls = Plus @@ cns;
frb = 
      Max[Position[Table[PartitionFunction[pcr][n], {n, 0, 500}], 0] - 
          1]

Block[{$DisplayFunction = Identity }, 
rng = 
        Range[0, Length[cns] - 1]; 
      pol = Flatten[pcr[[1]]] . 
          Binomial[n + rng, rng]; 
lp1 = 
        Plot[pol, {n, -200, 200}, 
          PlotStyle -> {Thickness[0.005], 
              RGBColor[1, 0, 0]}]; 
den = 
        Table[{n, Denumerant[pcr][n]}, {n, -200, 
            200}]; 
lp2 = 
        ListPlot[den, 
          PlotStyle -> {PointSize[0.008], 
              RGBColor[0, 0, 1]}];
]
Show[lp1, lp2, ImageSize -> 6 72, 
        TextStyle -> "Subsection", 
        GridLines -> {{-frb - pls, -pls/2, frb}, None}, 
        PlotRange -> {-0.5, 2}];

Table[{Denumerant[pcr][
            k], Denumerant[pcr][-(pls + k)]}, {k, 0, 
          15}];

Beispiel 3

cns = {15, 21, 23, 27, 35, 39};
Timing[pcr = 
          PartitionData[cns, 
            PartitionMethod -> PrimeFourier];]

pls = Plus @@ cns;
frb = 
      Max[Position[Table[Denumerant[pcr][n], {n, 0, 500}], 0] - 
          1]

Block[{$DisplayFunction = Identity }, 
rng = 
        Range[0, Length[cns] - 1]; 
      pol = Flatten[pcr[[1]]] . 
          Binomial[n + rng, rng]; 
lp1 = 
        Plot[pol, {n, -300, 200}, 
          PlotStyle -> {Thickness[0.005], 
              RGBColor[1, 0, 0]}]; 
den = 
        Table[{n, Denumerant[pcr][n]}, {n, -300, 
            200}]; 
lp2 = 
        ListPlot[den, 
          PlotStyle -> {PointSize[0.01], 
              RGBColor[0, 0, 
                1]}];
]
Show[lp1, lp2, ImageSize -> 8 72, 
        TextStyle -> "Subsection", 
        GridLines -> {{-frb - pls, -pls/2, frb}, None}, 
        PlotRange -> {-7, 7}];

Table[{Denumerant[pcr][
            k], -Denumerant[pcr][-(pls + k)]}, {k, 0, 
          15}];

Beispiel 4

cns = Range[10];
Timing[pcr = 
          PartitionData[cns, 
            PartitionMethod -> PrimeFourier];]

pls = Plus @@ cns; frb = -1;

Block[{$DisplayFunction = Identity }, 
rng = 
        Range[0, Length[cns] - 1]; 
      pol = Flatten[pcr[[1]]] . 
          Binomial[n + rng, rng]; 
lp1 = 
        Plot[pol, {n, -75, 20}, 
          PlotStyle -> {Thickness[0.005], 
              RGBColor[1, 0, 0]}]; 
den = 
        Table[{n, Denumerant[pcr][n]}, {n, -75, 
            20}]; 
lp2 = 
        ListPlot[den, 
          PlotStyle -> {PointSize[0.01], 
              RGBColor[0, 0, 1]}  ];
]
Show[lp1, lp2, ImageSize -> 9 72, 
        TextStyle -> "Subsection", 
        GridLines -> {{-frb - pls, -pls/2, frb}, None}, 
        PlotRange -> {-7, 7}];

Table[{Denumerant[pcr][
            k],  -Denumerant[pcr][-(pls + k)]}, {k, 0, 
          15}];

Beispiel 5

cns = Range[15];
Timing[pcr = 
          PartitionData[cns, 
            PartitionMethod -> PrimeFourier];]

pls = Plus @@ cns; frb = -1;

Block[{$DisplayFunction = Identity }, 
rng = 
        Range[0, Length[cns] - 1]; 
      pol = Flatten[pcr[[1]]] . 
          Binomial[n + rng, rng]; 
lp1 = 
        Plot[pol, {n, -140, 20}, 
          PlotStyle -> {Thickness[0.005], 
              RGBColor[1, 0, 0]}]; 
den = 
        Table[{n, Denumerant[pcr][n]}, {n, -140, 
            20}]; 
lp2 = 
        ListPlot[den, 
          PlotStyle -> {PointSize[0.01], 
              RGBColor[0, 0, 
                1]}];
]
Show[lp1, lp2, ImageSize -> 9 72, 
        TextStyle -> "Subsection", 
        GridLines -> {{-frb - pls, -pls/2, frb}, None}, 
        PlotRange -> {-1, 7}];

Table[{Denumerant[pcr][
            k],  Denumerant[pcr][-(pls + k)]}, {k, 0, 
          15}];

Benchmarks

cns = {1, 2, 5, 10, 20, 50, 100, 200};
Timing[pcr = PartitionData[cns];]
{cns, pcr} >> "euro200.txt"

cns = {1, 2, 5, 10, 20, 50, 100, 200, 
          500};
Timing[pcr = PartitionData[cns];]
{cns, pcr} >> "euro500.txt"

cns = Range[10];
Timing[pcr = PartitionData[cns];]
{cns, pcr} >> "benchRg10.txt"

cns = Range[15];
Timing[pcr = PartitionData[cns];]
{cns, pcr} >> "benchRg15.txt"

cns = Range[20];
Timing[pcr = PartitionData[cns];]
{cns, pcr} >> "benchRg20.txt"

cns = Table[Random[Integer, {100, 999}], {5}]
Timing[pcr = PartitionData[cns];]
{cns, pcr} >> "benchS3R5.txt"

cns = Table[Random[Integer, {100, 999}], {10}]
Timing[pcr = PartitionData[cns];]   
{cns, pcr} >> "benchS3R10.txt"

cns = Table[Random[Integer, {100, 999}], {15}]
Timing[pcr = PartitionData[cns];]   
{cns, pcr} >> "benchS3R15.txt"

cns = Table[Random[Integer, {100, 999}], {20}]
Timing[pcr = PartitionData[cns];]   
{cns, pcr} >> "benchS3R20.txt"

cns = Table[Random[Integer, {1000, 9999}], {10}]
Timing[pcr = PartitionData[cns];]   
{cns, pcr} >> "benchS4R10.txt"

Introduction

PrettyTable

Needs["Utilities`FilterOptions`"]
Needs["LinearAlgebra`MatrixManipulation`"]

PrettyTable[m_List, 
        opts___] := 
DisplayForm[
StyleBox[
GridBox[
Map[ToBoxes, 
              m, {2}], 
Evaluate[
              FilterOptions[GridBox, 
                opts]], 
GridFrame -> 
              2, 
RowLines -> {1, 
                0}, 
ColumnLines -> {1, 
                0}
], 
Evaluate[
            FilterOptions[StyleBox, 
              opts]], 
Background -> 
            GrayLevel[0.8]
]
]

Circulator

Periode[d_Integer?Positive] := 
      Table[d DiscreteDelta[Mod[n, d]] - 1, {n, 0, d - 1}]

PrimePeriode[
        p_Integer?Positive] := 
Module[{d, 
          tab}, 
tab = (MoebiusMu[p/#] 
                  Periode[#]) & /@ Divisors[p]; 
Plus @@ 
          PadRight[tab, {Length[tab], p}, tab]
]

Sawtooth[{p_Integer?Positive, 
          q_Integer?Positive}] := 
Module[{gcd = GCD[p, q], 
          inv}, 
inv = 
          PowerMod[q/gcd, -1, 
            p/gcd]; 
Table[-(inv n/
                      p - ⌊inv n/p⌋ - 1/2 + 
                  gcd/(2  p)) DiscreteDelta[Mod[n, gcd]], {n, 0, 
            p - 1}]
]

PrimeSawtooth[{p_Integer?Positive, 
          q_Integer?
            Positive}] := 
Module[{pcr}, 
pcr = (MoebiusMu[p/#] (#/p) 
                  Sawtooth[{#, q}]) & /@ 
            Divisors[p]; 
Plus @@ 
          PadRight[pcr, {Length[pcr], p}, pcr]
]

Circulator[
        a_List] := 
Module[{p = First[a], 
          tab}, 
tab = 
          Table[Sawtooth[{p, a[[k]]}], {k, 2, 
              Length[a]}]; 
Fold[
          ListConvolve[#1, #2, {1, 1}] &, {1}, 
          tab]
]

PrimeCirculator[
        a_List] := 
Module[{p = First[a], 
          tab}, 
tab = 
          Table[PrimeSawtooth[{p, a[[k]]}], {k, 2, 
              Length[a]}]; 
Fold[
          ListConvolve[#1, #2, {1, 1}] &, {1}, 
          tab]
]

Laurent

Laurent[cns_List, 
        d_Integer] := 
Module[{rng, wur, lau, 
          z}, 
rng = 
          Range[Count[Mod[cns, d], 0]]; 
wur = 
          If[OddQ[d], -(-1)^(1/d), (-1)^(2/
                  d)]; 
lau = 
          Series[(Times @@ (1 - z^cns))^-1, {z, 
              wur, -1}]; 
Expand[
          Coefficient[lau, z - wur, -rng]/(-wur)^
              rng]
]

\(\(\(SymbolicLaurent[cns_List, 
        1, ω_] := 
Module[{m, z, 
          den}, 
m = Length[cns]; 
den = 
          Times @@ \(Plus @@@ \((z^\((Range[cns] - 
                      1)\))\)\); 
Table[
          Expand[\((\(-1\))\)^\((m - j)\)/\(\((m - j)\)!\) \((D[
                    den^\(-1\), {z, m - j}] /. z -> 1)\)], {j, 
            m}]
]\)\(
\)
    \)\)
SymbolicLaurent[cns_List, 
        d_Integer, ω_] := 
Module[{div, com, m, z, 
          den}, 
div = Cases[cns/d, _Integer]; 
        com = cns /. Thread[d div :> Sequence[]]; 
        m = Length[div]; 
den = 
          Times @@ Plus @@@ (z^(d Range[div] - d)) 
            Times @@ (1 - z^com) 
            Sum[(z/ω)^i, {i, 0, d - 1}]^
              m; 
Table[
Expand[(-ω)^(m - j)/(m - j)! (D[den^-1, {z, m - j}] /. 
                    z -> ω)] /. ω^e_ -> ω^
                Mod[e, d], {j, 
            m}
]
]

Apart

cns = {1, 2, 3};
PrimeFourierData[cns]

d = 3; m = 1;
apt = Apart[(Times @@ (1 - z^cns))^-1]
HoldForm[(2 - z - z^2)]/
      HoldForm[9 (1 - z^3)]
CoefficientList[Series[apt[[-1]], {z, 0, 2  d - 1}], 
      z]
pol = Evaluate[Cyclotomic[d, #]] &
ftr = Evaluate[First[SymbolicLaurent[cns, d, #]] #^-n] &
Table[Simplify[RootSum[pol, ftr]], {n, 0, d - 1}]
{ftr1 = Evaluate[#^-n/(d (1 - #))] &, 
      ftr2 = Evaluate[#^-n/(d (1 - #^2))] &}
{Table[Simplify[RootSum[pol, ftr1]], {n, 0, d - 1}], 
      Table[Simplify[RootSum[pol, ftr2]], {n, 0, 
          d - 1}]}
{l1 = Sawtooth[{3, 1}], l2 = Sawtooth[{3, 2}]};
ListConvolve[l1, l2, {1, 1}];
Circulator[{3, 1, 2}];

d = 3; m = 1;
pol = 
      Expand[Factor[
          apt[[-1]] (1 - z^d)^m]]
Sum[
      Coefficient[pol, z, j] 
        SymbolicBinomial[m - 1 + (n - j)/d, m - 1], {j, 0, 
        m d - 1}]

Poles

cns = {3, 4, 5};
{div = Union @@ Divisors[cns], 
      mul = Count[Mod[cns, #], 0] & /@ div, 
      phi = EulerPhi[div]}
{Plus @@ cns, mul . phi}
sol = (z /. NSolve[1 - z^# == 0, z]) & /@ 
          cns;
grt = 
Graphics[
{
PointSize[
              0.0175], 
Table[{Hue[
                  1/k], Point[{Re[#], Im[#]}] & /@ sol[[k]]}, {k, 
                Length[cns]}]
}
];
big = 
        Graphics[{PointSize[0.035], RGBColor[1, 1, 0], 
            Point[{1, 0}]}];
Show[grt, big, AspectRatio -> Automatic, Axes -> True, 
        Ticks -> None, ImageSize -> 72 5];

cns = {15, 21, 23};
{div = Union @@ Divisors[cns], 
      mul = Count[Mod[cns, #], 0] & /@ div, 
      phi = EulerPhi[div]}
{Plus @@ cns, mul . phi}
cns = {15, 21, 23};
sol = (z /. NSolve[1 - z^# == 0, z]) & /@ 
          cns;
grt = 
Graphics[
{
PointSize[
              0.0175], 
Table[{Hue[
                  1/k], Point[{Re[#], Im[#]}] & /@ sol[[k]]}, {k, 
                Length[cns]}]
}
];
big = 
        Graphics[{PointSize[0.035], RGBColor[1, 1, 0], 
            Point[{1, 0}]}];
Show[grt, big, AspectRatio -> Automatic, Axes -> True, 
        Ticks -> None, ImageSize -> 72 5];

Sawtooth as an Inverse Discrete Fourier Transform

sz1[x_] := 
      0                         /;    Element[x, 
          Integers]

    sz1[x_] := 
      x - ⌊x⌋ - 
          1/2 /; ¬ Element[x, Integers]

sz2[x_] := 
      x - ⌊x⌋ - 1/2

p = 5; k = 2;
{Evaluate[Cyclotomic[p, #]] &, 
        Evaluate[Cancel[(1 - #^p)/(1 - #)]] &};
\(\(pol = 
        If[PrimeQ[p], Evaluate[Cyclotomic[p, #]] &, 
          Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &];\)
 (*\ 
      Sawtooth\ one\ *) \)
Table[sz1[n/p], {n, 0, p - 1}]
Table[
      FullSimplify[(1/p) 
          RootSum[pol, (#/(1 - #) + 1/2) #^n &]], {n, 0, 
        p - 1}]

      
Table[
        sz2[n/p] + 1/2 DiscreteDelta[Mod[n, p]], {n, 0, p - 1}];
tb = Table[{n, sz1[n/p]}, {n, 0, k p - 1}];
\(Block[{$DisplayFunction = Identity}, 
g1 = 
        Plot[sz1[x/p], {x, 0, k\ p}, 
          Ticks -> {Range[k\ p], 
              tb[\([All, 2]\)]}]; 
g2 = 
        ListPlot[tb, 
          PlotStyle -> {PointSize[0.02], 
              RGBColor[1, 0, 0]}];
]\)
Show[g1, g2, ImageSize -> 72 8, 
        PlotRange -> {-0.6, 0.6}, 
        TextStyle -> "Subsection"];

p = 5; k = 2;
{Evaluate[Cyclotomic[p, #]] &, 
        Evaluate[Cancel[(1 - #^p)/(1 - #)]] &};
\(\(pol = 
        If[PrimeQ[p], Evaluate[Cyclotomic[p, #]] &, 
          Evaluate[Cancel[\((1 - #^p)\)/\((1 - #)\)]] &];\)
 (*\ 
      Sawtooth\ one\ *) \)
Table[-(sz1[n/p] + 1/(2  p) - 
              1/2  DiscreteDelta[Mod[n, p]]), {n, 0, 
          p - 1}];
  
Table[-(sz2[n/p] + 1/(2  p)), {n, 0, p - 1}]
Table[
      FullSimplify[(1/p) RootSum[pol, #^-n/(1 - #) &]], {n, 0, 
        p - 1}]

      
tb = 
        Table[{n, -(sz2[n/p] + 1/(2  p))}, {n, 0, 
            k p - 1}];
\(Block[
{$DisplayFunction = Identity}, 
\ \ \ g1 = 
        Plot[\(-\((sz2[x/p] + 1/\((2  p)\))\)\), {x, 0, k\ p}, 
          Ticks -> {Range[k\ p], 
              tb[\([All, 2]\)]}]; 
g2 = 
        ListPlot[tb, 
          PlotStyle -> {PointSize[0.02], 
              RGBColor[0, 0, 1]}];
]\)
Show[g1, g2, ImageSize -> 72 8, 
        PlotRange -> {-0.6, 0.6}, 
        TextStyle -> "Subsection"];

p = 
        5;

    Table[sz1[n/p], {n, 0, p - 1}] - 
      Table[sz2[n/p], {n, 0, p - 1}]

    Table[
      FullSimplify[RootSum[(1 - #^p) &, #^n &]]/(2  p), {n, 0, 
        p - 1}]

    Table[DiscreteDelta[Mod[n, p]]/2, {n, 0, p - 1}]

Table[sz1[n/p], {n, 0, p - 1}]
Table[
      sz2[n/p] + 1/2 DiscreteDelta[Mod[n, p]], {n, 0, p - 1}]

Table[
      sz1[n/p] - 1/2  DiscreteDelta[Mod[n, p]], {n, 0, 
        p - 1}]
Table[sz2[n/p], {n, 0, p - 1}]

Table[-(sz1[n/p] + 1/(2  p) - 
            1/2  DiscreteDelta[Mod[n, p]]), {n, 0, 
        p - 1}]
Table[-(sz2[n/p] + 1/(2  p)), {n, 0, p - 1}]

PrimeSawtooth Computation via Moebius-Inversion

p = 
        15;

    pol = 
        Evaluate[Cancel[(1 - #^p)/(1 - #)]] &;

    Table[
      FullSimplify[RootSum[pol, #^-n &]], {n, 0, 
        p - 1}]

    Periode[p]

    pol = Evaluate[Cyclotomic[p, #]] &;

    Table[
      FullSimplify[RootSum[pol, #^-n &]], {n, 0, 
        p - 1}]

    PrimePeriode[p]

\(\(\( (*\ \(Periode\ is\ a\ sum\ of\ PrimePeriode´s\)\(,\)\ *) \)\(
\)\(\(p = 15;\)

    \(tab = 
        Table[DiscreteDelta[Mod[p, d]] PrimePeriode[d], {d, 
            p}];\)

    \(tab = PadRight[tab, {Length[tab], p}, tab];\)

    \(mat = Append[tab, Plus @@ tab];\)

    \(mat = 
        Transpose[
          Prepend[Transpose[mat], 
            Range[p] ⋃ {"Σ"}]];\)

    \(lst = Last[IdentityMatrix[p]];\)

    PrettyTable[mat, RowLines -> lst, ColumnLines -> Reverse[lst], 
      FontSize -> 15]\)\)\)

p = 
        15;

    tab = 
        Table[DiscreteDelta[Mod[p, d]] MoebiusMu[p/d] Periode[d], {d, 
            p}];

    tab = PadRight[tab, {Length[tab], p}, tab];

    mat = Append[tab, Plus @@ tab];

    mat = 
        Transpose[
          Prepend[Transpose[mat], 
            Range[p] ⋃ {"Σ"}]];

    lst = Last[IdentityMatrix[p]];

    PrettyTable[mat, RowLines -> lst, ColumnLines -> Reverse[lst], 
      FontSize -> 15]

{p, 
          q} = {15, 1};

    Sawtooth[{p, q}]

    pol = 
        Evaluate[Cancel[(1 - #^p)/(1 - #)]] &;

    Table[
      FullSimplify[(1/p) RootSum[pol, #^-n/(1 - #^q) &]], {n, 0, 
        p - 1}]

    PrimeSawtooth[{p, q}]

    pol = Evaluate[Cyclotomic[p, #]] &;

    Table[
      FullSimplify[(1/p) RootSum[pol, #^-n/(1 - #^q) &]], {n, 0, 
        p - 1}]

\(\(\( (*\ \(Sawtooth\ is\ a\ sum\ of\ PrimeSawtooth´s\)\(,\)\ *) \)\(
\)\(\({p, q} = {15, 1};\)

    \(pcr = 
        Table[DiscreteDelta[Mod[p, d]] d/p\ PrimeSawtooth[{d, q}], {d, 
            p}];\)

    \(pcr = PadRight[pcr, {Length[pcr], p}, pcr];\)

    \(mat = Append[pcr, Plus @@ pcr];\)

    \(mat = 
        Transpose[
          Prepend[Transpose[mat], 
            Range[p] ⋃ {"Σ"}]];\)

    \(lst = Last[IdentityMatrix[p]];\)

    PrettyTable[mat, RowLines -> lst, ColumnLines -> Reverse[lst], 
      FontSize -> 15]\)\)\)

{p, q} = {15, 
          1};

    pcr = 
        Table[DiscreteDelta[Mod[p, d]] MoebiusMu[p/d] 
            d/p Sawtooth[{d, q}], {d, p}];

    pcr = PadRight[pcr, {Length[pcr], p}, pcr];

    mat = Append[pcr, Plus @@ pcr];

    mat = 
        Transpose[
          Prepend[Transpose[mat], 
            Range[p] ⋃ {"Σ"}]];

    lst = Last[IdentityMatrix[p]];

    PrettyTable[mat, RowLines -> lst, ColumnLines -> Reverse[lst], 
      FontSize -> 15]

pcr = (MoebiusMu[
                  p/#] (#/p) Sawtooth[{#, q}]) & /@ 
          Divisors[p];

    Plus @@ PadRight[pcr, {Length[pcr], p}, pcr]

Convolution

p = 5; q = 2; r = 3;
pol = Evaluate[Cyclotomic[p, #]] &;
Table[
      FullSimplify[(1/p) 
          RootSum[pol, #^-n/((1 - #^q) (1 - #^r)) &]], {n, 0, 
        p - 1}]

cpq = Circulator[{p, q}];
cpr = Circulator[{p, r}];
ListConvolve[cpq, cpr, {1, 1}]
Circulator[{p, q, r}]

p = 6; q = 2; r = 5;
cpq = PrimeCirculator[{p, q}];
cpr = PrimeCirculator[{p, r}];
ListConvolve[cpq, cpr, {1, 1}]
PrimeCirculator[{p, q, r}]

Fourier - Transformation

p = 5; q = 1; r = 4;
tf = {PrimeSawtooth[{p, q}], PrimeSawtooth[{p, r}]}
ft = Chop[Fourier[tf, FourierParameters -> {-1, 1}]]
rt = 
      Rationalize[InverseFourier[ft, FourierParameters -> {-1, 1}], 
        10^-10]
tf == rt

cns = {7, 11, 22};
p = First[cns]; rst = Rest[cns];
PrimeCirculator[cns]
tf = PrimeSawtooth[{p, #}] & /@ rst
ft = 
        Chop[Fourier[tf, 
            FourierParameters -> {-1, 
                1}]];
rt = 
      Rationalize[InverseFourier[ft, FourierParameters -> {-1, 1}], 
        10^-10]
Fold[ListConvolve[#1, #2, {1, 1}] &, {1}, 
      rt]
tf == rt

p = 5; q = 1; r = 3;
tf = Sawtooth[{p, q}];
tf = Circulator[{p, q, r}]
ft = 
      Rationalize[
        Chop[Fourier[tf, FourierParameters -> {-1, 1}]]]
rm = Max[Abs[ft]];
Show[
Graphics[
{
Circle[{0, 0}, rm + 0.0075], 
PointSize[
              0.02], RGBColor[1, 0, 0], Point[{Re[#], Im[#]}] & /@ 
              ft
}
], 
Axes -> True, 
ImageSize -> 
          72 5, 
AspectRatio -> 
          Automatic, 
PlotRange -> {{-rm - 0.01, 
              rm + 0.01}, {-rm - 0.01, 
              rm + 0.01}}
];

p = 5; q = 1; 
    r = 3; ω = E^(2  π I/
              p);
tf = Circulator[{p, q, r}]
s1 = 
      Chop[Rest[
          Fourier[tf, 
            FourierParameters -> {-1, 
                1}]]]
s2 = 
      Chop[Table[(1/p) 
            N[1/((1 - (ω^k)^q) (1 - (ω^k)^
                          r))], {k, p - 1}]]
s1 == s2

Table[
      Rationalize[
        Chop[Sum[(1/p) 
              N[(ω^
                        k)^-n/((1 - (ω^k)^
                            q) (1 - (ω^k)^r))], {k, 
              p - 1}]]], {n, 0, p - 1}]