Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
PARI/GP function to generate the set of multiplicative partitions of a non-negative integer
/*
Returns the multiplicative partition of integer n
Ref: https://oeis.org/A001055
https://oeis.org/A162247
https://oeis.org/A162247/a162247.txt
Inputs:
n: Non-negative integer
Output:
V: Vector of multiplicative partitions of n
Example:
mpartitions(60) =
[[2, 2, 3, 5], [2, 2, 15], [2, 3, 10], [2, 5, 6], [2, 30], [3, 4, 5], [3, 20], [4, 15], [5, 12],
[6, 10], [60]]
Written by: John Peach 28-Dec-2020
*/
mpartitions(n) =
{
\\ Local variables V and U
local(V,U);
\\ Largest partition is n
V = [[n]];
\\ Loop over divisors d of n, terminating at d <= sqrt(n)
\\ If n/d is a prime stop search otherwise, continue recursively with n/d
fordiv(n, d,
if( d > 1 & d <= sqrt(n),
if( isprime(n/d), V = concat(V, [[d, n/d]]), U = mpartitions(n/d) );
\\ Concatenate solutions U with current divisor d and sort
\\ keeping only valid products
for( j = 1, length(U),
if(vecprod(concat(d,U[j])) == n,
V = concat(V,[vecsort(concat(d,U[j]))])));
);
);
\\ Eliminate duplicates with Set function, sort in lexicographic order
return(vecsort(Set(V)));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment