17
\$\begingroup\$

Given a positive integer \$n\$ you can always find a tuple \$(k_1,k_2,...,k_m)\$ of integers \$k_i \geqslant 2\$ such that \$k_1 \cdot k_2 \cdot ... \cdot k_m = n\$ and $$k_1 | k_2 \text{ , } k_2 | k_3 \text{ , } \ldots \text{ , }k_{m-1}|k_m.$$ Here \$a|b\$ means \$b\$ is a multiple of \$a\$, say "a divides b". If \$n>1\$ all entries \$k_i\$ must be at least \$2\$. For \$n=1\$ we have no such factor and therefore we get an empty tuple.

In case you're curious where this comes from: This decomposition is known as invariant factor decomposition in number theory and it is used in the classification of finitely generated Abelian groups.

Challenge

Given \$n\$ output all such tuples \$(k_1,k_2,...,k_m)\$ for the given \$n\$ exactly once, in whatever order you like. The standard output formats are allowed.

Examples

  1: () (empty tuple)
  2: (2)
  3: (3)
  4: (2,2), (4)
  5: (5)
  6: (6)
  7: (7)
  8: (2,2,2), (2,4), (8)
  9: (3,3), (9)
 10: (10)
 11: (11)
 12: (2,6), (12)
108: (2,54), (3,3,12), (3,6,6), (3,36), (6,18), (108)

Related: http://oeis.org/A000688, List all multiplicative partitions of n

\$\endgroup\$
  • \$\begingroup\$ May we output each tuple in reverse order? (e.g. 12,3,3) \$\endgroup\$ – Arnauld Sep 9 at 14:50
  • 1
    \$\begingroup\$ @Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok! \$\endgroup\$ – flawr Sep 9 at 15:33
  • \$\begingroup\$ Can we limit input to integers >= 2? If not this would invalidate some of the existing answers? \$\endgroup\$ – Nick Kennedy Sep 9 at 17:43
  • 1
    \$\begingroup\$ No, the specs say clearly that any positive integer can be given as input which includes \$n=1\$. If I change it now everyone who actually adheres to the specs would have to change their answer. \$\endgroup\$ – flawr Sep 9 at 19:21
5
\$\begingroup\$

Haskell, 66 62 60 bytes

f n=[n|n>1]:[k:l:m|k<-[2..n],l:m<-f$div n k,mod(gcd n l)k<1]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 13 bytes

Òœ€.œP€`êʒüÖP

Try it online!

Ò                      # prime factorization of the input
 œ€.œ                  # all partitions
     P                 # product of each sublist
      €`               # flatten
        ê              # sorted uniquified
         ʒ             # filter by:
          üÖ           #  pairwise divisible-by (yields list of 0s or 1s)
            P          #  product (will be 1 iff the list is all 1s)
\$\endgroup\$
  • \$\begingroup\$ Nice way of using Òœ€.œP to get the sublists. I indeed had trouble finding something shorter as well.. If only there was a builtin similar to Åœ but for product instead of sum. ;) \$\endgroup\$ – Kevin Cruijssen Sep 9 at 14:00
  • \$\begingroup\$ Fails for n=1 (see comments on question) \$\endgroup\$ – Nick Kennedy Sep 9 at 19:34
3
\$\begingroup\$

Jelly, 17 bytes

ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8),  73  70 bytes

Prints the tuples in descending order \$(k_m,k_{m-1},...,k_1)\$.

f=(n,d=2,a=[])=>n>1?d>n||f(n,d+1,a,d%a[0]||f(n/d,d,[d,...a])):print(a)

Try it online!

Commented

f = (             // f is a recursive function taking:
  n,              //   n   = input
  d = 2,          //   d   = current divisor
  a = []          //   a[] = list of divisors
) =>              //
  n > 1 ?         // if n is greater than 1:
    d > n ||      //   unless d is greater than n,
    f(            //   do a recursive call with:
      n,          //     -> n unchanged
      d + 1,      //     -> d + 1
      a,          //     -> a[] unchanged
      d % a[0] || //     unless the previous divisor does not divide the current one,
      f(          //     do another recursive call with:
        n / d,    //       -> n / d
        d,        //       -> d unchanged
        [d, ...a] //       -> d preprended to a[]
      )           //     end of inner recursive call
    )             //   end of outer recursive call
  :               // else:
    print(a)      //   this is a valid list of divisors: print it
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 17 15 14 bytes

ѦIиæʒPQ}êʒüÖP

Very slow for larger test cases.

-1 byte thanks to @Grimy.

Try it online.

Explanation:

Ñ               # Get all divisors of the (implicit) input-integer
 ¦              # Remove the first value (the 1)
  Iи            # Repeat this list (flattened) the input amount of times
                #  i.e. with input 4 we now have [2,4,2,4,2,4,2,4]
    æ           # Take the powerset of this list
     ʒ  }       # Filter it by:
      PQ        #  Where the product is equal to the (implicit) input
         ê      # Then sort and uniquify the filtered lists
          ʒ     # And filter it further by:
           ü    #  Loop over each overlapping pair of values
            Ö   #   And check if the first value is divisible by the second value
             P  #  Check if this is truthy for all pairs

                # (after which the result is output implicitly)
\$\endgroup\$
  • \$\begingroup\$ @Grimy Thanks. And good call on the divisors. It's still very slow for \$n=8\$, but all bits help, and if it doesn't cost any additional bytes to improve the performance, then why not use it. :) \$\endgroup\$ – Kevin Cruijssen Sep 9 at 13:44
  • 1
    \$\begingroup\$ 13 and faster. Feels like it can be shorter still. \$\endgroup\$ – Grimy Sep 9 at 13:56
1
\$\begingroup\$

JavaScript, 115 bytes

f=(n,a=[],i=1)=>{for(;i++<n;)n%i||(a=a.concat(f(n/i).filter(e=>!(e[0]%i)).map(e=>[i].concat(e))));return n>1?a:[a]}

I will write an explanation later

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

Wolfram Language (Mathematica), 78 76 72 71 67 bytes

If[#>(p=1##2),Join@@If[i∣##,##~#0~i,{}]~Table~{i,2,#/p},{{##2}}]&

Try it online!

Recursive search tree.


Brute force solution, 64 bytes:

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

Trivial modification of my Mathematica solution to List all multiplicative partitions of n.

Since this needs to check \$n^n\$ tuples, try a more efficient version using the same logic.

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

Japt, 22 bytes

â Åï c à f@¥XשXäv eÃâ

Try it

â Åï c à f@¥XשXäv eÃâ     :Implicit input of integer U
â                          :Divisors
  Å                        :Slice off the first element, removing the 1
   ï                       :Cartesian product
     c                     :Flatten
       à                   :Combinations
         f                 :Filter by
          @                :Passing each sub-array X through the following function
           ¥               :  Test U for equality with
            X×             :  X reduced by multiplication
              ©            :  Logical AND with
               Xä          :  Consecutive pairs of X
                 v         :  Reduced by divisibility
                   e       :  All truthy?
                    Ã      :End filter
                     â     :Deduplicate
\$\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.