26
\$\begingroup\$

Given a positive number n, output all distinct multiplicative partitions of n in any convenient format.

A multiplicative partition of n is a set of integers, all greater than one, such that their product is n. For example, 20 has the following distinct multiplicative partitions:

2 * 2 * 5
2 * 10
4 * 5
20

Order does not matter, so 2 * 2 * 5 is the same partition as 2 * 5 * 2.


Examples:

1 -> {}
2 -> {2}
4 -> {2, 2}, {4}
20 -> {2, 2, 5}, {2, 10}, {4, 5}, {20}
84 -> {2, 2, 3, 7}, {2, 2, 21}, {2, 14, 3}, {2, 6, 7}, {2, 42}, {4, 3, 7}, {28, 3}, {4, 21}, {6, 14}, {12, 7}, {84}
\$\endgroup\$

15 Answers 15

6
\$\begingroup\$

Brachylog, 16 bytes

>~l:{1<}a.*?,.=o

This is a function (not a full program) which takes a positive number as input and generates all multiplicative partitions of it. (I also avoided using any prime factorization builtins in this solution, mostly because I wasn't sure they'd help; I might try a more builtin-heavy solution too at some point.)

Try it online! (Extra code has been added around the function here to make it into a full program; if you provide the function shown above to TIO directly, it will run the function but not print its output anywhere, which is kind-of useless as a demonstration.)

This program really disappoints me, because much of it is working around bugs in the Brachylog interpreter and deficiencies in its specification, rather than actually solving the problem; but the interpreter is what it is. (Even with the program like this, the interpreter uses much more memory than it logically should, and crashes due to memory exhaustion, but luckily on small problems it manages to produce the desired output first.) In a hypothetical "perfect version of Brachylog" you could just write ~*.o.:{>1}a,, which would be 4 bytes shorter, but I needed to add extra constraints to help the interpreter out a bit. (I don't really like Brachylog much, and would rather stick to Prolog, but it needed similar hints to make the program work and they're much longer to write. So Brachylog it is.)

Explanation:

As usual, a Brachylog program is a set of constraints; by default, the first constraint constrains the input against an unknown (which I'll call A), the second constraint constrains A against a second unknown B, and so on until we reach the output. Some characters, such as {}, can change this general flow, so I use a different set of letters (e.g. X/Y) to represent unknowns in nested predicates.

>       A is smaller than the input
~l      B has length A
  1<    X is 1, Y is larger
:{1<}a  For each element X of B, it corresponds to an element Y of C
.       C, the output, and D are all identical
*       E is the product of D's elements
?       E, the input, and F are all identical
,       There's no constraint between F and G
.       G, the output, and H are all identical
=       H and I are identical, and need to be evaluated early
o       The output can be produced by sorting I

It's still unclear how the program works, so let's try simplifying the constraints a bit. C, D, G, H, and I are all the same (and equal to the output). E and F are also the same (and equal to the input). So our constraints boil down to this:

  • A is the length of B and of the output, and is smaller than the input.
  • B consists of all 1s, and isn't particularly useful (it's part of the program simply because in the existing Brachylog interpreter, :{1<}a needs its left argument to have a constrained length, or else the interpreter goes into an infinite loop).
  • The output consists entirely of numbers greater than 1 (i.e. greater than the corresponding element of B).
  • The product of the elements of the output is equal to the input.
  • The output is unchanged by sorting it (i.e. is in sorted order).

Incidentally, I didn't explicitly specify that all the elements of the output are integers, something which might seem to be required; however, Brachylog's constraint solver can't handle non-integers, so it'll conveniently produce only the solutions that involve integers.

Clearly, "the length of the output is smaller than the input" is going to be true whenever the output is a multiplicative partition of the input (because 2x > x for all nonnegative x, i.e. positive 2x). So we can disregard that constraint; it's only there to give the Brachylog interpreter a working strategy for evaluating the program. The other constraints (that the output is sorted, that its product is the input, and that its elements are all greater than 1) are the definition of a multiplicative partition, and therefore this function is basically just a direct implementation of the question.

\$\endgroup\$
6
\$\begingroup\$

Brachylog 1, 14 bytes

:{$pp~c:*ao}fd

Try it online!

Brachylog 2, 11 10 bytes, language postdates challenge

{ḋp~c×ᵐo}ᵘ

Try it online!

Maltysen answered this question in 17 bytes of Pyth, so I came up with a 16-byte Brachylog solution that worked by translating the specification of the question to Brachylog. While I was doing that, Dennis wrote a 15-byte Jelly solution. So I had to go down to 14 bytes. This is a function that takes the input as an argument, and returns a list of all partitions (rather than a generator, as with my other solution).

Some time after I wrote this answer, Dennis and I managed to cooperatively get the Jelly solution down to 11 bytes. It turns out there's a new version of Brachylog out, with a terser syntax; it postdates the challenge, so doesn't actually count, but it could manage the 11-byte total too pretty much as soon as it released; later revisions of the language (inspired by other challenges) can go as low as 10, as seen here. The two programs are identical, with the only difference being the syntax.

Unlike my other solution, which didn't make much use of "golfing primitives" but rather stated the problem directly, this one ignores pretty much all the power of Brachylog constraints and does its best Jelly impression instead, writing a chain of constraints for which the left argument is already known (and thus the constraints simply act like Jelly monads rather than full-blown constraints). It therefore uses the same algorithm as @Maltysen's Pyth solution, which is probably the easiest way to solve this using typical golfing primitives. (Interestingly, the "just state the problem" solution in my other answer would be shorter if not for bugs/deficiencies in the Brachylog interpreter, despite its lack of use of golfing primitives. Some day I need to write an "improved Brachylog" in order to get a good solution for this kind of problem; as golfing languages go, Brachylog is actually really verbose.)

The program consists of a generator, and a wrapper around it. First, here's an explanation of the generator:

$pp~c:*ao  ḋp~c×ᵐo
$p         ḋ        Prime factor decomposition of the input
  p         p       Generate all permutations
   ~c        ~c     Generate all inverse concatenations (i.e. partitions)
     :*a       ×ᵐ   Take the product of each list element in each partition
        o        o  Sort each partition

This almost solves the problem, but we end up generating many of the partitions many times each. So we need a wrapper to deduplicate the solutions:

:{…}fd
:{…}f     Convert generator to list
     d    Remove duplicate elements

{…}ᵘ      Convert generator to list of unique elements
\$\endgroup\$
  • \$\begingroup\$ Why not edit your exsting answer? \$\endgroup\$ – Downgoat Dec 27 '16 at 5:00
  • 3
    \$\begingroup\$ @Downgoat: The two answers use entirely different approaches; the algorithms are different, the language features that are used are mostly independent, and the like. It wouldn't make sense to replace the older one with the newer one (and I might well have posted the new one even if it were longer). This meta post suggests that posting separate answers is preferable in this sort of situation. \$\endgroup\$ – user62131 Dec 27 '16 at 5:05
  • 1
    \$\begingroup\$ I don't know if you know this but you can retrieve the output by setting the argument on TIO to be a variable (i.e. an uppercase letter). For example. \$\endgroup\$ – Fatalize Jan 2 '17 at 15:50
5
\$\begingroup\$

Mathematica, 61 bytes

±1={{}}
±n_:=Union@@(Sort/@Append[n/#]/@±#&/@Most@Divisors@n)

Defines a (recursive) unary operator ± which returns the list of partitions.

\$\endgroup\$
  • \$\begingroup\$ Doesn't mathematica not require the semicolon at the end? \$\endgroup\$ – Pavel Dec 27 '16 at 0:57
  • \$\begingroup\$ @Pavel no, the semicolon just suppresses output in the interactive notebook. Thanks for pointing this out, btw, I accidentally left a semicolon at the end. \$\endgroup\$ – Martin Ender Dec 27 '16 at 7:34
4
\$\begingroup\$

Pyth - 17 bytes

Takes all permutations of the prime factorization, then partitions each one and then products all the partitions, then only retains distinct partitions.

{mS-*Md1s./M.p+1P

Test Suite.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 70 bytes

f=lambda n,k=2,l=[]:n/k and(n%k<1)*f(n/k,k,l+[k])+f(n,k+1,l)or 1/n*[l]

Outputs a list of sorted lists. For example f(20) is [[2, 2, 5], [2, 10], [4, 5], [20]].

\$\endgroup\$
  • \$\begingroup\$ As Python's built-in integer type has no limits, floating point is not an acceptable solution as inaccuracies will break the answer for too large inputs. \$\endgroup\$ – orlp Dec 27 '16 at 9:14
  • \$\begingroup\$ @orlp Ok, back to Python 2 then. \$\endgroup\$ – xnor Dec 27 '16 at 9:46
  • \$\begingroup\$ TL;DR I think 998 is not a too large input ;-) IMO a real cool code, more like latency O(n) and comparing to the Python 2 competitor might be more O(n^4) style - while f(998) might blow memory or hardware could die within run time of est. 80 days with the other algorithm, this one here converges after approx. 7 milli secs on my machine to yield the result [[2, 499], [998]]. IMO the problem could be more that for N > 998 the RecursionError: maximum recursion depth exceeded in comparison stops the above Python 3 code ... happy golfing :-) \$\endgroup\$ – Dilettant Dec 27 '16 at 12:12
  • \$\begingroup\$ @Dilettant Not sure if O(n^4) is even enough for my Python2 submission :D Considering the test case 998, my code will run 9 times, and calculate (n+r-1)! / r! / (n-1)! amount of tuples each time, where r is growing linearly from 2, and n is 9 - 2. But hey, at least you don't have to tweak the recursion limit... \$\endgroup\$ – Yytsi Dec 27 '16 at 14:39
  • \$\begingroup\$ @TuukkaX Caveat: I did not analyze the code, just skimmed over and compared the development of run times among the two candidates for some N up to 41 then thought I just commit the comment ;-) stacks and recursion often meat easy, but then call for how deep type questions in unpleasant situations ... hope I coined it fuzzy enough for the amount of research that went in. \$\endgroup\$ – Dilettant Dec 27 '16 at 14:44
3
\$\begingroup\$

Jelly, 14 13 11 bytes

Ḋx³ŒPQP=¥Ðf

Try it online!

I was fairly sure @Dennis's Jelly solution could be improved. Unfortunately, I didn't manage to beat the Brachylog record, but I did manage to tie it. Update: With @Dennis' help, it's improved now; I guess Jelly takes back the crown.

This program is incredibly inefficient, having O(2n2) performance (which is why the test case above shows it for input 4). It completes quickly on 4, very slowly on 5, and may not be practically possible to run for larger numbers.

Interestingly, the Brachylog was improved by going from a solution that described the problem (which Brachylog is good at) to a solution that used an algorithm based on factorising the input (which Jelly is good at); meanwhile, the Jelly solution was improved by moving away from its strengths, and going back to a solution that just describes the problem.

Explanation:

Ḋx³ŒPQP=¥Ðf
Ḋ              List of integers from 2 to the input (apparently undocumented)
 x³            Make a number of copies of each that's equal to the input
   ŒP          Take all (possibly noncontiguous) subsequences of that list (!)
     Q         Remove duplicates
         Ðf    Filter, keeping elements where:
      P=         their product is equal to {the original input, by default}
        ¥      Parse preceding two links as a unit

Because the output of Ḋx is sorted, each subsequence must also be sorted, and thus we don't have to sort them individually. So the "the same output in different orders is a duplicate" part of the problem, and the "all values in the output are > 1" part of the problem, get solved by the generation. Apart from that, what we're basically doing here is "find all lists for which P=³", which we do (in an incredibly inefficient way) by generating all the lists in question and then filtering out the incorrect ones.

(Clearly, someone needs to go invent a hybrid of Jelly and Brachylog, plus a really good constraint solver, so that we could write something along the lines of {P=³}~ plus some deduplication code, and solve the program in a much shorter length. That might be some distance away, though.)

\$\endgroup\$
  • \$\begingroup\$ Please, someone find a character of savings here. I'd love a "byte war" in which the entries keep on getting one byte shorter every time. There's enough bytes wasted on structural parts of the program here that it seems like this might be improvable. \$\endgroup\$ – user62131 Dec 27 '16 at 2:17
  • 1
    \$\begingroup\$ Heh, I was just about to post something strikingly similar. (Should refresh more often.) 2r can become , and P=³$$ can become P=¥. \$\endgroup\$ – Dennis Dec 27 '16 at 2:32
  • \$\begingroup\$ P=¥ doesn't work when I try it in the interpreter, although I'm not entirely sure why (logically, it should work, and it was one of the things I tried while writing the post; I just tried it again to make sure, it definitely doesn't do what I'd expected). does, though, so I guess there's our one-byte saving :-) \$\endgroup\$ – user62131 Dec 27 '16 at 2:40
  • 1
    \$\begingroup\$ Didn't pay attention to another detail. You'd have to replace µ with ¹ as well, as µ makes the repeated range the new left argument. \$\endgroup\$ – Dennis Dec 27 '16 at 2:44
  • \$\begingroup\$ Oh, of course. So now we're down to 11, with much fewer characters, which is making me feel much better. (I used ³ rather than ¹ just for the variety.) \$\endgroup\$ – user62131 Dec 27 '16 at 2:47
2
\$\begingroup\$

JavaScript (ES6), 74 67 bytes

f=(n,m=2,a=[])=>n>1?m>n?[]:f(n,m+1,a).concat(f(n/m,m,[...a,m])):[a]

for (var i = 1; i < 31; i++) console.log(JSON.stringify(f(i)));

Directly solves the problem recursively: for each integer m from 2 to n, we take each of the partitions of n / m with a minimum element of m (to avoid duplicate partitions) and append m. (For any m that does not divide n, this gives the empty array, as no arrangement of integers multiplies to a decimal.) We define a base case of the empty array for 1 so as to avoid infinite recursion.

\$\endgroup\$
1
\$\begingroup\$

Python2, 198 191 172 180 bytes

from itertools import*
n=input()
for i in range(2,len(bin(n))):
 for P in combinations_with_replacement(range(2,n),i):
  if reduce(lambda a,b:a*b,P)==n:print(P)
print[(n,),()][n<2]

A full program. This could be improved a lot, so suggestions are deeply welcome!

Outputs from the range 1 to 31 (inclusive):

(1,)
(2,)
(3,)
(2, 2), (4,)
(5,)
(2, 3), (6,)
(7,)
(2, 4), (2, 2, 2), (8,)
(3, 3), (9,)
(2, 5), (10,)
(11,)
(2, 6), (3, 4), (2, 2, 3), (12,)
(13,)
(2, 7), (14,)
(3, 5), (15,)
(2, 8), (4, 4), (2, 2, 4), (2, 2, 2, 2), (16,)
(17,)
(2, 9), (3, 6), (2, 3, 3), (18,)
(19,)
(2, 10), (4, 5), (2, 2, 5), (20,)
(3, 7), (21,)
(2, 11), (22,)
(23,)
(2, 12), (3, 8), (4, 6), (2, 2, 6), (2, 3, 4), (2, 2, 2, 3), (24,)
(5, 5), (25,)
(2, 13), (26,)
(3, 9), (3, 3, 3), (27,)
(2, 14), (4, 7), (2, 2, 7), (28,)
(29,)
(2, 15), (3, 10), (5, 6), (2, 3, 5), (30,)
(31,)
\$\endgroup\$
  • \$\begingroup\$ Does this even work? There is test case 4 -> {2, 2}, {4} in question, I don't see such output in your log. \$\endgroup\$ – Borsunho Dec 26 '16 at 23:41
  • \$\begingroup\$ @Borsunho As I roller the old version back, I forgot to add +1 to int(math.log(n,2)), which caused that. +2 bytes and it will work. Thanks! \$\endgroup\$ – Yytsi Dec 26 '16 at 23:53
  • \$\begingroup\$ You haven't imported math but are using math.log. \$\endgroup\$ – orlp Dec 26 '16 at 23:57
  • \$\begingroup\$ @orlp I have...? On the third line. \$\endgroup\$ – Yytsi Dec 26 '16 at 23:57
  • \$\begingroup\$ @TuukkaX Excuse, me, I only looked at the topmost lines for imports, as they're almost always there... That being said, len(bin(n))-2 is shorter than int(math.log(n,2)). \$\endgroup\$ – orlp Dec 26 '16 at 23:58
1
\$\begingroup\$

Jelly, 15 bytes

ÆfŒ!ŒṖ€;/P€€Ṣ€Q

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This answer is rich! \$\endgroup\$ – Luis Mendo Dec 27 '16 at 1:55
1
\$\begingroup\$

Clojure, 91 bytes

(defn f[n](conj(set(for[i(range 2 n):when(=(mod n i)0)j(f(/ n i))](sort(flatten[i j]))))n))

Example runs:

(map f [20 84])
(#{20 (2 2 5) (4 5) (2 10)} #{(7 12) (2 2 3 7) (2 3 14) (2 2 21) (2 6 7) (6 14) (3 4 7) (3 28) (4 21) (2 42) 84})

The value itself is returned as a single number (not a list), others come out as lists. The n at the end could be replaced by [n] to make it a sequence as well, or (list n) to make it a list.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 4 bytes

Ò.œP

Try it online!

Explanation:

             # implicit input (example: 12)
Ò            # prime factorization of the input ([2, 2, 3])
 .œ          # partitions ([[[2], [2], [3]], [[2], [2, 3]], [[2, 2], [3]], [[2, 2, 3]]])
   P         # vectorized product ([[2, 2, 3], [2, 6], [4, 3], [12]])
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

Union@Cases[Tuples[Range@#,#],{a__,__}/;1a==#&&2<=a:>{a}]&

Try it online!

Quite slow even for small values due to the large number of tuples generated.

Union@                      (*unique*)
 Cases[Tuples[Range@#,#],   (*select tuples of up to (input) numbers 1..(input)*)
  {a__,__}/;                (*which start with a subsequence which:*)
   1a==#&&                  (*- has a product equal to the input, and*)
    2<=a                    (*- is sorted in ascending order and does not contain 1*)
  :>{a}]&                   (*use that subsequence rather than the whole tuple*)

For a more usable version based on the same concept,

Union@Cases[Tuples[Divisors@#,PrimeOmega@#+1],{a__,__}/;1a==#&&2<=a:>{a}]&

Try it online!

\$\endgroup\$
0
\$\begingroup\$

J, 35 bytes

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:

Based on the solution to a time-constrained factorization challenge.

This version is much more inefficient and runs in factorial time based on the number of prime factors. Creates partitions by generating factoradic numbers.

Try it online! (Don't try large values online!)

Explanation

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:  Input: integer n
                                 q:  Prime factorization
(                              )@    Operate on them
                              #        Length
                            !@         Factorial
                         i.@           Range [0, i)
                     #\                Range [1, i]
                       #:              Mixed based conversion - Creates factoradic values
     ]                                 Get factors
            (    )"$~                  For each factoradic value
               /.                        Partition the factors based on equal
                                         digits in the factoradic value
             */                          Get the product of each block
        /:~@                             Sort it
      <@                                 Box it
 [:~.                                  Deduplicate
\$\endgroup\$
0
\$\begingroup\$

D, 95 bytes

void g(int n,int[]r){for(int i=r[0];i*i<=n;i++)(n%i)?0:g(n/i,i~r);r.back=n;r.writeln;}g(n,[2]);

Just a recursive solution. In g(n,r), r is the partition so far, and n is the value still left to break into factors. To get each unordered partition only once, we sort the factors in r in non-increasing order. The last element of r starts at 2 as the least possible factor, and gets overwritten by n in each copy just before each output operation.

For n = 60, the output is as follows:

[3, 2, 2, 5]
[2, 2, 15]
[3, 2, 10]
[5, 2, 6]
[2, 30]
[4, 3, 5]
[3, 20]
[4, 15]
[5, 12]
[6, 10]
[60]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Use the templates, Gassa, use the templates: void g(T)(T n,T[]r){for(T i=r[0];i*i<=n;i++)n%i0:r;r.back=n;r.writeln;}g(n,[2]) \$\endgroup\$ – Zacharý Aug 20 '17 at 12:06
  • \$\begingroup\$ Anyways, this isn't even a valid answer, as you need to import std.stdio and std.range, input 1 should print nothing, not [1]. \$\endgroup\$ – Zacharý Aug 20 '17 at 13:35
0
\$\begingroup\$

D, 109 bytes

import std.stdio;void g(T)(T n,T[]r=[2]){if(n-1){for(T i=r[0];i*i<=n;i++)n%i?0:g(n/i,i~r);r[$-1]=n;r.write;}}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.