# Dividing Divisive Divisors

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)

• May we output each tuple in reverse order? (e.g. 12,3,3) Sep 9 '19 at 14:50
• @Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok! Sep 9 '19 at 15:33
• Can we limit input to integers >= 2? If not this would invalidate some of the existing answers? Sep 9 '19 at 17:43
• 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. Sep 9 '19 at 19:21

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! # 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)  • 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. ;) Sep 9 '19 at 14:00 • Fails for n=1 (see comments on question) Sep 9 '19 at 19:34 # Jelly, 17 bytes ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ


Try it online!

# 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||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 || //     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


# 05AB1E, 1715 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)

• @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. :) Sep 9 '19 at 13:44
• 13 and faster. Feels like it can be shorter still. Sep 9 '19 at 13:56

# JavaScript, 115 bytes

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


I will write an explanation later

# Wolfram Language (Mathematica), 7876 ... 61 51 bytes

Do[i∣##&&##~#0~i,{i,2,-#/-##2/. 1:>Print@{##2}}]&


Try it online!

Recursive search tree.

Prints the list of decompositions.

# Husk, 18 15 bytes

fΛ¦ufo=¹ΠṖmΠtṖp


Try it online!

-3 bytes from Zgarb.

• oΛIẊ¦ can be just Λ¦. ΛV can take binary functions and check the condition on adjacent pairs. Oct 15 '20 at 8:02
• Clean. I'll change it. Oct 15 '20 at 8:02

# Japt, 22 19 bytes

ÆâÃcÅà â f@¶XcXäv)×


Try it

ÆâÃcÅà â f@¶XcXäv)×     :Implicit input of integer U
Æ                       :Map the range [0,U)
â                      :  Divisors of U
Ã                     :End map
c                    :Flatten after
Å                   :  Slicing the first element off each
à                  :Combinations
â                :Deduplicate
f              :Filter by
@             :Passing each X through the following function
¶            :  Test U for equality with
Xc          :  Concatenate to X
Xä        :    Consecutive pairs of X
v       :    Reduced by testing divisibility
)      :  End concat
×     :  Reduce by multiplication


# Jelly, 14 bytes

ḊœċRẎḍƝẠ×P=¥ʋƇ


Try it online!

## How it works

ḊœċRẎḍƝẠ×P=¥ʋƇ - Main link. Takes n on the left
Ḋ              - Dequeue; Yield [2, 3, ..., n]
R           - Range, Yield [1, 2, ..., n]
œċ            - For each integer, 1 ≤ i ≤ n, yield combinations with
replacement of length i from the dequeued range
Ẏ          - Tighten into a single list of lists
ʋƇ - Keep those for which the following is true:
×  ¥   -   Both of the following are true:
Ɲ        -     Over overlapping pairs:
ḍ         -       Is the left divisible by the right?
Ạ       -     Is all true?
×      -   And:
P     -     The product
=    -     Equals n?