Dividing Divisive DivisorsList 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
Why didn't Thor use the All powerful spear instead of Stormbreaker?
Why does F + F' = 1?
How was Carlo's plan supposed to work?
Why are some Mac apps not available on AppStore?
How accurate is the new appraisal system?
What is going on: C++ std::move on std::shared_ptr increases use_count?
Does the word “uzi” need to be capitalized?
How do I politely hint customers to leave my store, without pretending to need leave store myself?
How flexible are number-of-pages submission guidelines for conferences?
How important is the DUP support (at the moment) to the current ruling party in UK?
How should we understand "unobscured by flying friends" in this context?
How to create a list of dictionaries from a dictionary with lists of different lengths
How can I protect myself in case of a human attack like the murders of the hikers Jespersen and Ueland in Morocco?
My favorite color is blue what is your favorite color?
Job offer without any details but asking me to withdraw other applications - is it normal?
How do I restrict an interpolated function to only take values > 0?
Why would thermal imaging be used to locate the Chandrayaan-2 lander?
Determining if file in projected or geographic coordinates using ArcGIS Desktop?
Is BitLocker useful in the case of stolen laptop?
What happens when a caster loses concentration on a banished creature?
For how long could UK opposition parties prevent new elections?
Do any aircraft carry boats?
Does the mana ability restriction of Pithing Needle refer to the cost or the effect of an activated ability?
Are there take-over requests in aviation?
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
$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
$endgroup$
$begingroup$
May we output each tuple in reverse order? (e.g.12,3,3)
$endgroup$
– Arnauld
7 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
6 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
4 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
3 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
$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
edited 3 hours ago
flawr
asked 9 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
7 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
6 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
4 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
3 hours ago
add a comment |
$begingroup$
May we output each tuple in reverse order? (e.g.12,3,3)
$endgroup$
– Arnauld
7 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
6 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
4 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
3 hours ago
$begingroup$
May we output each tuple in reverse order? (e.g.
12,3,3)$endgroup$
– Arnauld
7 hours ago
$begingroup$
May we output each tuple in reverse order? (e.g.
12,3,3)$endgroup$
– Arnauld
7 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
6 hours ago
$begingroup$
@Arnauld Yes, I think as long as it is sorted in ascending or descending order it should be ok!
$endgroup$
– flawr
6 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
4 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
4 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
3 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
3 hours ago
add a comment |
7 Answers
7
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!
$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)
$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
8 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 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
$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)
$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
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 hours ago
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
$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
$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!
$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
7 Answers
7
active
oldest
votes
7 Answers
7
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!
$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!
$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!
$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!
edited 15 mins ago
answered 3 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)
$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
8 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 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)
$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
8 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 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)
$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 8 hours ago
GrimyGrimy
6,97016 silver badges33 bronze badges
6,97016 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
8 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 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
8 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 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
8 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
8 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 hours ago
$begingroup$
Fails for n=1 (see comments on question)
$endgroup$
– Nick Kennedy
2 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
$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
$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
$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
edited 6 hours ago
answered 8 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)
$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
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 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)
$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
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 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)
$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)
edited 8 hours ago
answered 8 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
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 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
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 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
8 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
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 hours ago
$begingroup$
13 and faster. Feels like it can be shorter still.
$endgroup$
– Grimy
8 hours ago
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
$endgroup$
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
$endgroup$
add a comment |
$begingroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
$endgroup$
Jelly, 17 bytes
ÆfŒ!Œb€ẎP€€QḍƝẠ$Ƈ
Try it online!
answered 2 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
$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
$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
$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
edited 5 hours ago
answered 8 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!
$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!
$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!
$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 16 mins ago
attinatattinat
2,3652 silver badges11 bronze badges
2,3652 silver badges11 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
7 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
6 hours ago
$begingroup$
Can we limit input to integers >= 2? If not this would invalidate some of the existing answers?
$endgroup$
– Nick Kennedy
4 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
3 hours ago