Aufgabe::tupledDivisors

["Udo und Susanne Krause" <su.krause@XXXXXXX.ch>]

Liebe Freundinnen und Freunde des karwöchentlichen Rechnens,

gelegentlich sollte man die ungeordneten multiplikativen Zerlegungen Z
einer positiven ganzen Zahl P in A ganzzahlige Faktoren kennen.

Natürlich ergibt sich Z einerseits durch Zusammenfassung der Primfaktoren
in A Gruppen, allenfalls unter Zuhilfenahme der 1, sofern nicht genügend
Primfaktoren vorhanden sind.

Andererseits ist Z eine Auswahl von A-Tupeln der Divisoren von P, die
Implementation bei Vorhandensein unbegrenzter Ressourcen ist schlicht

In[332]:= Z[A_Integer?Positive, P_Integer?Positive] :=
        Union[Sort /@ Select[Tuples[Divisors[P], A], (Times @@ # == P) &]]

Man finde eine effiziente Implementation für Z[A, P], etwa
tupledDivisors[A, P].
[divisor partition, multiplicative partition]

Mit den besten Grüssen
Udo.

P.S. 1: Beispiele

In[369]:= tupledDivisors[1, 36]
Out[369]= {{36}}

In[370]:= tupledDivisors[2, 36]
Out[370]= {{1, 36}, {2, 18},{3, 12}, {4, 9}, {6, 6}}

In[371]:= tupledDivisors[3, 36]
Out[371]= {{1, 1, 36}, {1, 2, 18}, {1, 3, 12}, {1, 4, 9},
        {1, 6, 6}, {2, 2, 9}, {2, 3, 6}, {3, 3, 4}}

In[372]:= tupledDivisors[4, 36]
Out[372]= {{1, 1, 1, 36}, {1, 1, 2, 18}, {1, 1, 3, 12},
        {1, 1, 4, 9}, {1, 1, 6, 6}, {1, 2, 2, 9}, {1, 2, 3, 6}, {1, 3, 3, 4},
        {2, 2, 3, 3}}

In[373]:= tupledDivisors[5, 36]
Out[373]= {{1, 1, 1, 1, 36}, {1, 1, 1, 2, 18}, {1, 1, 1, 3, 12}, {1, 1, 1,
4, 9},
        {1, 1, 1, 6, 6}, {1, 1, 2, 2, 9}, {1, 1, 2, 3, 6}, {1, 1, 3, 3, 4},
        {1, 2, 2, 3, 3}}

In[374]:= tupledDivisors[6, 36]
Out[374]= {{1, 1, 1, 1, 1, 36}, {1, 1, 1, 1, 2, 18}, {1, 1, 1, 1, 3, 12},
        {1, 1, 1, 1, 4, 9}, {1, 1, 1, 1, 6, 6}, {1, 1, 1, 2, 2, 9}, {1, 1, 1, 2,
3, 6},
        {1, 1, 1, 3, 3, 4}, {1, 1, 2, 2, 3, 3}}

P.S. 2: Effizienz

In[379]:= Length[Divisors[8 5 7 18 36]]
Out[379]= 140

In[380]:= Plus @@ Last /@ FactorInteger[8 5 7 18 36]
Out[380]= 12

In[381]:= Length[tupledDivisors[12, 8 5 7 18 36]] // Timing
Out[381]= {13.057, 6756}