:

## Partitions of a natural number into factors

Maple has  combinat [composition] (n, m)  command, which returns all possible lists of positive integers of  m  terms, the sum of which in each list is n. But there is no similar command for multiplication.

Wrote recently procedure  Factoring, which solves this problem. Formal arguments:  n> 1 - an integer, m - an optional parameter that indicates how many numbers in each list. The  Factoring (n)  command returns a list consisting of all lists of natural numbers (all numbers greater than 1), the product of which in each list is  n  (the numbers in the lists are in increasing order).  Factoring (n, m)  command  returns all of the lists, each of which has  m  numbers.

This procedure may be useful, for example, in solving some Diophantine equations, and also in several other aspects of the theory of numbers.

Procedure code:

Factoring:=proc(n::posint, m::posint)

local  p, L, M, Div, k, i, j, K;

uses numtheory;

if n=1 then error "should be n>1"; fi;

if nargs=2 and m>bigomega(n) then  error cat(`should be m<=`,bigomega(n)); fi;

if _params['m']=NULL then p:=bigomega(n) else p:=m; fi;

L:=[[n]];

M:=[];

Div:=sort(convert(divisors(n) minus {1, n}, list), `>`):

for k in Div while n/k<=k do

M:=[op(M), [n/k, k]];

od;

L:=M;

for i from 3 to p do

K:=[];

for j from 1 to nops(L[i-1]) do

Div:=divisors(L[i-1][j,i-1]) minus {1, L[i-1][j,i-1]}:

for k in Div do

if k<=(L[i-1][j][i-1])/k and L[i-1][j][i-2]<=k then

K:=[op(K), [op(L[i-1][j][1..i-2]), k, (L[i-1][j][i-1])/k]]; fi;

od; od;

L[i]:=K;

od;

if _params['m']=NULL then [seq(op(L[i]), i=1..p)] else

L[m]; fi;

end proc:

Examples:

Factoring(72);

[, [2, 36], [3, 24], [4, 18], [6, 12], [8, 9], [2, 2, 18], [2, 3, 12], [2, 4, 9], [2, 6, 6], [3, 3, 8], [3, 4, 6], [2, 2, 2, 9], [2, 2, 3, 6], [2, 3, 3, 4], [2, 2, 2, 3, 3]]

Factoring(72, 3);

[[2, 2, 18], [2, 3, 12], [2, 4, 9], [2, 6, 6], [3, 3, 8], [3, 4, 6]]

Application to the solution of Diophantine equations  {x + y + z + u = 711, x * y * z * u = 711 * 100 ^ 3} . This problem was discussed at  http://www.mapleprimes.com/questions/141437-Help-With-Procedures-Needed-Asap

S:=[]:

for i in Factoring(711*100^3, 4) do

if convert(i,`+`)=711 then S:=[op(S), i]:  fi:

od:

S;

[[120, 125, 150, 316]] ﻿