Dividing Divisive DivisorsList all multiplicative partitions of nGive the smallest number that has N...
SCOTUS - Can Congress overrule Marbury v. Madison by statute?
Was Robin Hood's point of view ethically sound?
How can "life" insurance prevent the cheapening of death?
Has any object launched from Earth gone into the Sun?
What is this dollar sign ($) icon in my Menu Bar?
How would two worlds first establish an exchange rate between their currencies
Why does F + F' = 1?
Job offer without any details but asking me to withdraw other applications - is it normal?
Does the word “uzi” need to be capitalized?
How to create a list of dictionaries from a dictionary with lists of different lengths
Why is the the worst case for this function O(n^2)?
2.5 year old daughter refuses to take medicine
Usage of Offrir and Donner
Is there a "right" way to interpret a novel? If so, how do we make sure our novel is interpreted correctly?
Stack class in Java 8
How to circle together certain entries of a matrix?
Expected value until a success?
How was Carlo's plan supposed to work?
Why was "leaping into the river" a valid trial outcome to prove one's innocence?
Do Milankovitch Cycles fully explain climate change?
Why didn't Thor use the All powerful spear instead of Stormbreaker?
"Not enough RAM " error in PIC16F877a
How would a village use its river that it shares with another village downstream?
Dividing Divisive Divisors
Dividing Divisive Divisors
List all multiplicative partitions of nGive the smallest number that has N divisorsCircles dividing the planeCount the divisors of a numberCalculate the Number, Divisors EditionFind the positive divisors!Testing for admissible sequencesSum my Fibonaccified divisors!Product of DivisorsSwap program halves to test divisorsDirichlet Convolution
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$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 ant 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 sequence 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
code-golf math sequence number-theory abstract-algebra
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
$endgroup$
add a comment |
$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 ant 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 sequence 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
code-golf math sequence number-theory abstract-algebra
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
$endgroup$
$begingroup$
May we output each tuple in reverse order? (e.g.12,3,3)
$endgroup$
– Arnauld
9 hours ago
1
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
9 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
6 hours ago
$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
5 hours ago
add a comment |
$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 ant 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 sequence 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
code-golf math sequence number-theory abstract-algebra
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
$endgroup$
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 ant 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 sequence 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
code-golf math sequence number-theory abstract-algebra
code-golf math sequence number-theory abstract-algebra
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
edited 5 hours ago
flawr
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
asked 11 hours ago
flawrflawr
29.8k7 gold badges81 silver badges209 bronze badges
29.8k7 gold badges81 silver badges209 bronze badges
$begingroup$
May we output each tuple in reverse order? (e.g.12,3,3)
$endgroup$
– Arnauld
9 hours ago
1
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
9 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
6 hours ago
$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
5 hours ago
add a comment |
$begingroup$
May we output each tuple in reverse order? (e.g.12,3,3)
$endgroup$
– Arnauld
9 hours ago
1
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
9 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
6 hours ago
$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
5 hours ago
$begingroup$
May we output each tuple in reverse order? (e.g.
12,3,3)$endgroup$
– Arnauld
9 hours ago
$begingroup$
May we output each tuple in reverse order? (e.g.
12,3,3)$endgroup$
– Arnauld
9 hours ago
1
1
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
9 hours ago
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
9 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
6 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
6 hours ago
$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
5 hours ago
$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
5 hours ago
add a comment |
8 Answers
8
active
oldest
votes
$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!
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
$endgroup$
add a comment |
$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)
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
$endgroup$
$begingroup$
Nice way of usingÒœ€.œPto 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
10 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
add a comment |
$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
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
$endgroup$
add a comment |
$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)
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
$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
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
$endgroup$
add a comment |
$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
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 78 bytes
i_~f~a_:1:=##&@@If[a∣#,If[#<i,Append@#/@f[i/#,#],!{i}],{}]&/@Rest@Divisors@i
Try it online!
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
$endgroup$
add a comment |
$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
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f191529%2fdividing-divisive-divisors%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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!
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
$endgroup$
add a comment |
$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!
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
$endgroup$
add a comment |
$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!
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
$endgroup$
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!
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
edited 2 hours ago
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
answered 5 hours ago
niminimi
33.9k3 gold badges27 silver badges91 bronze badges
33.9k3 gold badges27 silver badges91 bronze badges
add a comment |
add a comment |
$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)
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
$endgroup$
$begingroup$
Nice way of usingÒœ€.œPto 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
10 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
add a comment |
$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)
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
$endgroup$
$begingroup$
Nice way of usingÒœ€.œPto 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
10 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
add a comment |
$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)
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
$endgroup$
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)
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
answered 10 hours ago
GrimyGrimy
6,98016 silver badges33 bronze badges
6,98016 silver badges33 bronze badges
$begingroup$
Nice way of usingÒœ€.œPto 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
10 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
add a comment |
$begingroup$
Nice way of usingÒœ€.œPto 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
10 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
$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
10 hours ago
$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
10 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
5 hours ago
add a comment |
$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
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
$endgroup$
add a comment |
$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
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
$endgroup$
add a comment |
$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
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
$endgroup$
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
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
edited 8 hours ago
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
answered 10 hours ago
ArnauldArnauld
92.2k7 gold badges108 silver badges376 bronze badges
92.2k7 gold badges108 silver badges376 bronze badges
add a comment |
add a comment |
$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)
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
$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
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
add a comment |
$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)
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
$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
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
add a comment |
$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)
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
$endgroup$
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)
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
edited 10 hours ago
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
answered 11 hours ago
Kevin CruijssenKevin Cruijssen
50.7k7 gold badges85 silver badges247 bronze badges
50.7k7 gold badges85 silver badges247 bronze badges
$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
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
add a comment |
$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
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
$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
10 hours ago
$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
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
10 hours ago
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
$endgroup$
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
$endgroup$
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
$endgroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
answered 4 hours ago
Erik the OutgolferErik the Outgolfer
36.2k4 gold badges30 silver badges113 bronze badges
36.2k4 gold badges30 silver badges113 bronze badges
add a comment |
add a comment |
$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
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
$endgroup$
add a comment |
$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
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
$endgroup$
add a comment |
$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
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
$endgroup$
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
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
edited 7 hours ago
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
answered 10 hours ago
ShaggyShaggy
21.4k3 gold badges21 silver badges72 bronze badges
21.4k3 gold badges21 silver badges72 bronze badges
add a comment |
add a comment |
$begingroup$
Wolfram Language (Mathematica), 78 bytes
i_~f~a_:1:=##&@@If[a∣#,If[#<i,Append@#/@f[i/#,#],!{i}],{}]&/@Rest@Divisors@i
Try it online!
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 78 bytes
i_~f~a_:1:=##&@@If[a∣#,If[#<i,Append@#/@f[i/#,#],!{i}],{}]&/@Rest@Divisors@i
Try it online!
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 78 bytes
i_~f~a_:1:=##&@@If[a∣#,If[#<i,Append@#/@f[i/#,#],!{i}],{}]&/@Rest@Divisors@i
Try it online!
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
$endgroup$
Wolfram Language (Mathematica), 78 bytes
i_~f~a_:1:=##&@@If[a∣#,If[#<i,Append@#/@f[i/#,#],!{i}],{}]&/@Rest@Divisors@i
Try it online!
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
answered 2 hours ago
attinatattinat
2,3752 silver badges11 bronze badges
2,3752 silver badges11 bronze badges
add a comment |
add a comment |
$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
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
$endgroup$
add a comment |
$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
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
$endgroup$
add a comment |
$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
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
$endgroup$
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
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
answered 1 hour ago
NaruyokoNaruyoko
3091 silver badge8 bronze badges
3091 silver badge8 bronze badges
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f191529%2fdividing-divisive-divisors%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
May we output each tuple in reverse order? (e.g.
12,3,3)$endgroup$
– Arnauld
9 hours ago
1
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
9 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
6 hours ago
$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
5 hours ago