23
3
A collection of positive integers d_1 d_2 ... d_k
is a factorisation of a positive integer n
if
d_1 * d_2 * ... * d_k = n
Each positive integer has a unique prime factorisation, but in general they also have factorisations in which some of the terms are composite. E.g.
12 = 6 * 2 = 4 * 3 = 3 * 2 * 2
Write a program, function, verb, or similar which takes as input a single positive integer and returns or prints a complete list of its distinct factorisations. The factorisations may be produced in any order, and their terms may be in any order, but no two should be permutations of each other. Factorisations may not include 1
with two exceptions: for input n
you may give the factorisation n*1
instead of n
; and for input 1
you may give the factorisation 1
instead of the empty list.
You may assume that the input will be in the range of a signed 32-bit integer. If the output is as a string, there should be a clear distinction between the delimitation of numbers within a factorisation and the delimitation of the factorisations, but it is not necessary (for example) for the factors to be joined with an *
.
Your code should be capable of handling any valid input within 10 minutes on a reasonable desktop machine.
Examples
1 [[]]
or [[1]]
or [[1 1]]
7 [[7]]
or [[7 1]]
or [[1 7]]
12 [[12] [6 2] [4 3] [2 3 2]]
or variants
16 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
or variants
901800900 a list of 198091 factorisations
1338557220 a list of 246218 factorisations
Can you post the list of factorisations of
901800900
and1338557220
somewhere where we can check them? My code is giving me 2048 and 1024 factorizations for those numbers, respectively, and I'm not sure why. – Sherlock9 – 2016-07-29T09:28:58.987@Sherlock9, will do that when I get home. What I can do with an online generator is to give you a valid output for 5336100.
– Peter Taylor – 2016-07-29T10:22:40.7433This reminds me of a ProjectEuler challenge (unfortunately I don't remember which). But there you had to count the number of factorizations instead of listing them. – flawr – 2016-07-29T13:43:28.217
Related OEIS: A001055
– Sherlock9 – 2016-07-29T20:07:16.340