Calculate Landau's functionRace of the DigitsCounting groups of a given sizeSort by MultiplyingTransform a matrixPrint the “even” permutations of symmetric group Sn in cyclic notationFill in an increasing sequence with as many numbers as possibleKolakoski-like self-referencing sequencesIllustrate the Least Common MultipleEx-Increasing Set SequenceFill up to duplicate ranges
Did the Apollo Guidance Computer really use 60% of the world's ICs in 1963?
Can two aircraft be allowed to stay on the same runway at the same time?
How were US credit cards verified in-store in the 1980's?
What is the motivation behind designing a control stick that does not move?
How do I portray irrational anger in first person?
Is Borg adaptation only temporary?
Who declared the Last Alliance to be the "last" and why?
Is this homebrew "Faerie Fire Grenade" unbalanced?
Under GDPR, can I give permission once to allow everyone to store and process my data?
Why are JWST optics not enclosed like HST?
Can authors email you PDFs of their textbook for free?
Sum and average calculator
“all of who” or “all of whom”?
Ask one verbal question to figure out who is blind and who is mute among three persons
How can I portray a character with no fear of death, without them sounding utterly bored?
What is the practical impact of using System.Random which is not cryptographically random?
Do universities maintain secret textbooks?
Does the telecom provider need physical access to the SIM card to clone it?
How to animate a function plot
Could a complex system of reaction wheels be used to propel a spacecraft?
Which is the correct version of Mussorgsky's Pictures at an Exhibition?
Unexpected behavior after assignment of function object to function wrapper
Where could I find a math pen pal?
Properly unlinking hard links
Calculate Landau's function
Race of the DigitsCounting groups of a given sizeSort by MultiplyingTransform a matrixPrint the “even” permutations of symmetric group Sn in cyclic notationFill in an increasing sequence with as many numbers as possibleKolakoski-like self-referencing sequencesIllustrate the Least Common MultipleEx-Increasing Set SequenceFill up to duplicate ranges
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Landau's function $g(n)$ (OEIS A000793) gives the maximum order of an element of the symmetric group $S_n$. Here, the order of a permutation $pi$ is the smallest positive integer $k$ such that $pi^k$ is the identity - which is equal to the least common multiple of the lengths of the cycles in the permutation's cycle decomposition. For example, $g(14) = 84$ which is achieved for example by (1,2,3)(4,5,6,7)(8,9,10,11,12,13,14).
Therefore, $g(n)$ is also equal to the maximum value of $operatornamelcm(a_1, ldots, a_k)$ where $a_1 + cdots + a_k = n$ with $a_1, ldots, a_k$ positive integers.
Problem
Write a function or program that calculates Landau's function.
Input
A positive integer $n$.
Output
$g(n)$, the maximum order of an element of the symmetric group $S_n$.
Examples
n g(n)
1 1
2 2
3 3
4 4
5 6
6 6
7 12
8 15
9 20
10 30
11 30
12 60
13 60
14 84
15 105
16 140
17 210
18 210
19 420
20 420
Score
This is code-golf: Shortest program in bytes wins. (Nevertheless, shortest implementations in multiple languages are welcome.)
Note that there are no requirements imposed on run-time; therefore, your implementation does not necessarily need to be able to generate all the above example results in any reasonable time.
Standard loopholes are forbidden.
code-golf math arithmetic permutations integer-partitions
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
$endgroup$
add a comment |
$begingroup$
Landau's function $g(n)$ (OEIS A000793) gives the maximum order of an element of the symmetric group $S_n$. Here, the order of a permutation $pi$ is the smallest positive integer $k$ such that $pi^k$ is the identity - which is equal to the least common multiple of the lengths of the cycles in the permutation's cycle decomposition. For example, $g(14) = 84$ which is achieved for example by (1,2,3)(4,5,6,7)(8,9,10,11,12,13,14).
Therefore, $g(n)$ is also equal to the maximum value of $operatornamelcm(a_1, ldots, a_k)$ where $a_1 + cdots + a_k = n$ with $a_1, ldots, a_k$ positive integers.
Problem
Write a function or program that calculates Landau's function.
Input
A positive integer $n$.
Output
$g(n)$, the maximum order of an element of the symmetric group $S_n$.
Examples
n g(n)
1 1
2 2
3 3
4 4
5 6
6 6
7 12
8 15
9 20
10 30
11 30
12 60
13 60
14 84
15 105
16 140
17 210
18 210
19 420
20 420
Score
This is code-golf: Shortest program in bytes wins. (Nevertheless, shortest implementations in multiple languages are welcome.)
Note that there are no requirements imposed on run-time; therefore, your implementation does not necessarily need to be able to generate all the above example results in any reasonable time.
Standard loopholes are forbidden.
code-golf math arithmetic permutations integer-partitions
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
$endgroup$
add a comment |
$begingroup$
Landau's function $g(n)$ (OEIS A000793) gives the maximum order of an element of the symmetric group $S_n$. Here, the order of a permutation $pi$ is the smallest positive integer $k$ such that $pi^k$ is the identity - which is equal to the least common multiple of the lengths of the cycles in the permutation's cycle decomposition. For example, $g(14) = 84$ which is achieved for example by (1,2,3)(4,5,6,7)(8,9,10,11,12,13,14).
Therefore, $g(n)$ is also equal to the maximum value of $operatornamelcm(a_1, ldots, a_k)$ where $a_1 + cdots + a_k = n$ with $a_1, ldots, a_k$ positive integers.
Problem
Write a function or program that calculates Landau's function.
Input
A positive integer $n$.
Output
$g(n)$, the maximum order of an element of the symmetric group $S_n$.
Examples
n g(n)
1 1
2 2
3 3
4 4
5 6
6 6
7 12
8 15
9 20
10 30
11 30
12 60
13 60
14 84
15 105
16 140
17 210
18 210
19 420
20 420
Score
This is code-golf: Shortest program in bytes wins. (Nevertheless, shortest implementations in multiple languages are welcome.)
Note that there are no requirements imposed on run-time; therefore, your implementation does not necessarily need to be able to generate all the above example results in any reasonable time.
Standard loopholes are forbidden.
code-golf math arithmetic permutations integer-partitions
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
$endgroup$
Landau's function $g(n)$ (OEIS A000793) gives the maximum order of an element of the symmetric group $S_n$. Here, the order of a permutation $pi$ is the smallest positive integer $k$ such that $pi^k$ is the identity - which is equal to the least common multiple of the lengths of the cycles in the permutation's cycle decomposition. For example, $g(14) = 84$ which is achieved for example by (1,2,3)(4,5,6,7)(8,9,10,11,12,13,14).
Therefore, $g(n)$ is also equal to the maximum value of $operatornamelcm(a_1, ldots, a_k)$ where $a_1 + cdots + a_k = n$ with $a_1, ldots, a_k$ positive integers.
Problem
Write a function or program that calculates Landau's function.
Input
A positive integer $n$.
Output
$g(n)$, the maximum order of an element of the symmetric group $S_n$.
Examples
n g(n)
1 1
2 2
3 3
4 4
5 6
6 6
7 12
8 15
9 20
10 30
11 30
12 60
13 60
14 84
15 105
16 140
17 210
18 210
19 420
20 420
Score
This is code-golf: Shortest program in bytes wins. (Nevertheless, shortest implementations in multiple languages are welcome.)
Note that there are no requirements imposed on run-time; therefore, your implementation does not necessarily need to be able to generate all the above example results in any reasonable time.
Standard loopholes are forbidden.
code-golf math arithmetic permutations integer-partitions
code-golf math arithmetic permutations integer-partitions
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
edited 8 hours ago
Daniel Schepler
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
asked 8 hours ago
Daniel ScheplerDaniel Schepler
7792 silver badges10 bronze badges
7792 silver badges10 bronze badges
add a comment |
add a comment |
9 Answers
9
active
oldest
votes
$begingroup$
05AB1E, 6 bytes
Åœ€.¿Z
Try it online!
Ŝ # integer partitions of the input
€.¿ # lcm of each
Z # maximum
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
$endgroup$
add a comment |
$begingroup$
Wolfram Language (Mathematica), 44 bytes
Max[PermutationOrder/@Permutations@Range@#]&
Try it online!
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
$endgroup$
$begingroup$
Not that familiar with the language - butMax[Apply@LCM/@IntegerPartitions@#]&seems to work for me and would give 36 bytes if it's correct.
$endgroup$
– Daniel Schepler
7 hours ago
1
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even doMax[LCM@@@IntegerPartitions@#]&for 31 bytes, because@@@doesApplyat level 1.
$endgroup$
– Roman
7 hours ago
add a comment |
$begingroup$
Ruby, 77 bytes
f=->na=*0...n;a.permutation.map.max
Try it online!
(1..) infinite range syntax is too new for TIO, so the link sets an arbitrary upper bound.
This uses the direct definition--enumerate all possible permutations, then test each one by mutating a until it gets back to its original position (which also conveniently means I can just mutate the original array in each loop).
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
Œṗæl/€Ṁ
Try it online!
A monadic link taking an integer as its argument and returning an integer.
Explanation
Œṗ | Integer partitions
æl/€ | Reduce each using LCM
Ṁ | Maximum
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
$endgroup$
add a comment |
$begingroup$
Gaia, 25 23 22 bytes
,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉
Try it online!
Not having LCM or integer partitions makes this approach rather long.
,:Π¤d¦&⊢⌉/ ;* helper function: LCM of 2 inputs
1w&ḍΣ¦¦ ;* push integer partitions
¦ ;* for each
⇈⊢ ;* Reduce by helper function
⌉ ;* and take the max
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
$endgroup$
add a comment |
$begingroup$
Python 3 + numpy, 115 102 99 bytes
-13 bytes thanks to @Daniel Shepler
-3 more bytes from @Daniel Shepler
import numpy
c=lambda n:[n]+[numpy.lcm(i,j)for i in range(1,n)for j in c(n-i)]
l=lambda n:max(c(n))
Try it online!
Brute force method: find all possible sequences a,b,c,... where a+b+c+...=n, then pick the one with the highest lcm.
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
$endgroup$
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
|
show 1 more comment
$begingroup$
JavaScript (ES6), 92 bytes
Computes the maximum value of $operatornamelcm(a_1,ldots,a_k)$ where $a_1+ldots+a_k$ is a partition of $n$.
f=(n,i=1,l=m=0)=>n?i>n?m:f(n-i,i,l*i/(G=(a,b)=>b?G(b,a%b):a)(l,i)||i)&f(n,i+1,l)|m:m=l>m?l:m
Try it online!
JavaScript (ES6), 95 bytes
f=(n,i=1,m)=>i>>n?m:f(n,i+1,i<m|(g=(n,k=2,p=0)=>k>n?p:n%k?p+g(n,k+1):g(n/k,k,p*k||k))(i)>n?m:i)
Try it online!
How?
We define:
$$cases
g(1)=0\
g(n)=sum_j=1^Np_j^k_jquadtextforenspace n>1enspacetextandenspace n=prod_j=1^Np_j^k_j
$$
(this is A008475)
Then we use the formula (from A000793):
$$f(n)=max_g(k)le nk$$
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
$endgroup$
add a comment |
$begingroup$
Perl 6, 50 bytes
max .map:+(.[$_],.[@^a]...$_,)o&permutations
Try it online!
Checks all permutations directly, like @histocrat's Ruby solution.
Explanation
&permutations # Permutations of [0;n)
o # Feed into block
.map: # Map permutations
... # Construct sequence
.[$_] # Start with permutation applied to itself [1]
,.[@^a] # Generate next item by applying permutation again
$_, # Until it matches original permutation [2]
+( ) # Length of sequence
max # Find maximum
1 We can use any sequence of n distinct items for the check, so we simply take the permutation itself.
2 If the endpoint is a container, the ... sequence operator smartmatches against the first item. So we have to pass a single-element list.
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
$endgroup$
add a comment |
$begingroup$
Haskell, 70 bytes
f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]
Try it online!
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 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/3.0/"u003ecc by-sa 3.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%2f191074%2fcalculate-landaus-function%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
9 Answers
9
active
oldest
votes
9 Answers
9
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
05AB1E, 6 bytes
Åœ€.¿Z
Try it online!
Ŝ # integer partitions of the input
€.¿ # lcm of each
Z # maximum
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
$endgroup$
add a comment |
$begingroup$
05AB1E, 6 bytes
Åœ€.¿Z
Try it online!
Ŝ # integer partitions of the input
€.¿ # lcm of each
Z # maximum
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
$endgroup$
add a comment |
$begingroup$
05AB1E, 6 bytes
Åœ€.¿Z
Try it online!
Ŝ # integer partitions of the input
€.¿ # lcm of each
Z # maximum
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
$endgroup$
05AB1E, 6 bytes
Åœ€.¿Z
Try it online!
Ŝ # integer partitions of the input
€.¿ # lcm of each
Z # maximum
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
answered 8 hours ago
GrimyGrimy
5,92015 silver badges30 bronze badges
5,92015 silver badges30 bronze badges
add a comment |
add a comment |
$begingroup$
Wolfram Language (Mathematica), 44 bytes
Max[PermutationOrder/@Permutations@Range@#]&
Try it online!
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
$endgroup$
$begingroup$
Not that familiar with the language - butMax[Apply@LCM/@IntegerPartitions@#]&seems to work for me and would give 36 bytes if it's correct.
$endgroup$
– Daniel Schepler
7 hours ago
1
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even doMax[LCM@@@IntegerPartitions@#]&for 31 bytes, because@@@doesApplyat level 1.
$endgroup$
– Roman
7 hours ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 44 bytes
Max[PermutationOrder/@Permutations@Range@#]&
Try it online!
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
$endgroup$
$begingroup$
Not that familiar with the language - butMax[Apply@LCM/@IntegerPartitions@#]&seems to work for me and would give 36 bytes if it's correct.
$endgroup$
– Daniel Schepler
7 hours ago
1
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even doMax[LCM@@@IntegerPartitions@#]&for 31 bytes, because@@@doesApplyat level 1.
$endgroup$
– Roman
7 hours ago
add a comment |
$begingroup$
Wolfram Language (Mathematica), 44 bytes
Max[PermutationOrder/@Permutations@Range@#]&
Try it online!
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
$endgroup$
Wolfram Language (Mathematica), 44 bytes
Max[PermutationOrder/@Permutations@Range@#]&
Try it online!
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
answered 7 hours ago
RomanRoman
1,0302 silver badges8 bronze badges
1,0302 silver badges8 bronze badges
$begingroup$
Not that familiar with the language - butMax[Apply@LCM/@IntegerPartitions@#]&seems to work for me and would give 36 bytes if it's correct.
$endgroup$
– Daniel Schepler
7 hours ago
1
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even doMax[LCM@@@IntegerPartitions@#]&for 31 bytes, because@@@doesApplyat level 1.
$endgroup$
– Roman
7 hours ago
add a comment |
$begingroup$
Not that familiar with the language - butMax[Apply@LCM/@IntegerPartitions@#]&seems to work for me and would give 36 bytes if it's correct.
$endgroup$
– Daniel Schepler
7 hours ago
1
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even doMax[LCM@@@IntegerPartitions@#]&for 31 bytes, because@@@doesApplyat level 1.
$endgroup$
– Roman
7 hours ago
$begingroup$
Not that familiar with the language - but
Max[Apply@LCM/@IntegerPartitions@#]& seems to work for me and would give 36 bytes if it's correct.$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
Not that familiar with the language - but
Max[Apply@LCM/@IntegerPartitions@#]& seems to work for me and would give 36 bytes if it's correct.$endgroup$
– Daniel Schepler
7 hours ago
1
1
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even do
Max[LCM@@@IntegerPartitions@#]& for 31 bytes, because @@@ does Apply at level 1.$endgroup$
– Roman
7 hours ago
$begingroup$
@DanielSchepler yes, super! Why don't you propose it as a separate solution? You can even do
Max[LCM@@@IntegerPartitions@#]& for 31 bytes, because @@@ does Apply at level 1.$endgroup$
– Roman
7 hours ago
add a comment |
$begingroup$
Ruby, 77 bytes
f=->na=*0...n;a.permutation.map.max
Try it online!
(1..) infinite range syntax is too new for TIO, so the link sets an arbitrary upper bound.
This uses the direct definition--enumerate all possible permutations, then test each one by mutating a until it gets back to its original position (which also conveniently means I can just mutate the original array in each loop).
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
$endgroup$
add a comment |
$begingroup$
Ruby, 77 bytes
f=->na=*0...n;a.permutation.map.max
Try it online!
(1..) infinite range syntax is too new for TIO, so the link sets an arbitrary upper bound.
This uses the direct definition--enumerate all possible permutations, then test each one by mutating a until it gets back to its original position (which also conveniently means I can just mutate the original array in each loop).
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
$endgroup$
add a comment |
$begingroup$
Ruby, 77 bytes
f=->na=*0...n;a.permutation.map.max
Try it online!
(1..) infinite range syntax is too new for TIO, so the link sets an arbitrary upper bound.
This uses the direct definition--enumerate all possible permutations, then test each one by mutating a until it gets back to its original position (which also conveniently means I can just mutate the original array in each loop).
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
$endgroup$
Ruby, 77 bytes
f=->na=*0...n;a.permutation.map.max
Try it online!
(1..) infinite range syntax is too new for TIO, so the link sets an arbitrary upper bound.
This uses the direct definition--enumerate all possible permutations, then test each one by mutating a until it gets back to its original position (which also conveniently means I can just mutate the original array in each loop).
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
answered 8 hours ago
histocrathistocrat
19.9k4 gold badges32 silver badges74 bronze badges
19.9k4 gold badges32 silver badges74 bronze badges
add a comment |
add a comment |
$begingroup$
Jelly, 7 bytes
Œṗæl/€Ṁ
Try it online!
A monadic link taking an integer as its argument and returning an integer.
Explanation
Œṗ | Integer partitions
æl/€ | Reduce each using LCM
Ṁ | Maximum
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
Œṗæl/€Ṁ
Try it online!
A monadic link taking an integer as its argument and returning an integer.
Explanation
Œṗ | Integer partitions
æl/€ | Reduce each using LCM
Ṁ | Maximum
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
$endgroup$
add a comment |
$begingroup$
Jelly, 7 bytes
Œṗæl/€Ṁ
Try it online!
A monadic link taking an integer as its argument and returning an integer.
Explanation
Œṗ | Integer partitions
æl/€ | Reduce each using LCM
Ṁ | Maximum
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
$endgroup$
Jelly, 7 bytes
Œṗæl/€Ṁ
Try it online!
A monadic link taking an integer as its argument and returning an integer.
Explanation
Œṗ | Integer partitions
æl/€ | Reduce each using LCM
Ṁ | Maximum
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
answered 8 hours ago
Nick KennedyNick Kennedy
6,3171 gold badge9 silver badges15 bronze badges
6,3171 gold badge9 silver badges15 bronze badges
add a comment |
add a comment |
$begingroup$
Gaia, 25 23 22 bytes
,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉
Try it online!
Not having LCM or integer partitions makes this approach rather long.
,:Π¤d¦&⊢⌉/ ;* helper function: LCM of 2 inputs
1w&ḍΣ¦¦ ;* push integer partitions
¦ ;* for each
⇈⊢ ;* Reduce by helper function
⌉ ;* and take the max
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
$endgroup$
add a comment |
$begingroup$
Gaia, 25 23 22 bytes
,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉
Try it online!
Not having LCM or integer partitions makes this approach rather long.
,:Π¤d¦&⊢⌉/ ;* helper function: LCM of 2 inputs
1w&ḍΣ¦¦ ;* push integer partitions
¦ ;* for each
⇈⊢ ;* Reduce by helper function
⌉ ;* and take the max
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
$endgroup$
add a comment |
$begingroup$
Gaia, 25 23 22 bytes
,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉
Try it online!
Not having LCM or integer partitions makes this approach rather long.
,:Π¤d¦&⊢⌉/ ;* helper function: LCM of 2 inputs
1w&ḍΣ¦¦ ;* push integer partitions
¦ ;* for each
⇈⊢ ;* Reduce by helper function
⌉ ;* and take the max
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
$endgroup$
Gaia, 25 23 22 bytes
,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉
Try it online!
Not having LCM or integer partitions makes this approach rather long.
,:Π¤d¦&⊢⌉/ ;* helper function: LCM of 2 inputs
1w&ḍΣ¦¦ ;* push integer partitions
¦ ;* for each
⇈⊢ ;* Reduce by helper function
⌉ ;* and take the max
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
edited 8 hours ago
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
answered 8 hours ago
GiuseppeGiuseppe
19.3k3 gold badges16 silver badges68 bronze badges
19.3k3 gold badges16 silver badges68 bronze badges
add a comment |
add a comment |
$begingroup$
Python 3 + numpy, 115 102 99 bytes
-13 bytes thanks to @Daniel Shepler
-3 more bytes from @Daniel Shepler
import numpy
c=lambda n:[n]+[numpy.lcm(i,j)for i in range(1,n)for j in c(n-i)]
l=lambda n:max(c(n))
Try it online!
Brute force method: find all possible sequences a,b,c,... where a+b+c+...=n, then pick the one with the highest lcm.
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
$endgroup$
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
|
show 1 more comment
$begingroup$
Python 3 + numpy, 115 102 99 bytes
-13 bytes thanks to @Daniel Shepler
-3 more bytes from @Daniel Shepler
import numpy
c=lambda n:[n]+[numpy.lcm(i,j)for i in range(1,n)for j in c(n-i)]
l=lambda n:max(c(n))
Try it online!
Brute force method: find all possible sequences a,b,c,... where a+b+c+...=n, then pick the one with the highest lcm.
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
$endgroup$
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
|
show 1 more comment
$begingroup$
Python 3 + numpy, 115 102 99 bytes
-13 bytes thanks to @Daniel Shepler
-3 more bytes from @Daniel Shepler
import numpy
c=lambda n:[n]+[numpy.lcm(i,j)for i in range(1,n)for j in c(n-i)]
l=lambda n:max(c(n))
Try it online!
Brute force method: find all possible sequences a,b,c,... where a+b+c+...=n, then pick the one with the highest lcm.
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
$endgroup$
Python 3 + numpy, 115 102 99 bytes
-13 bytes thanks to @Daniel Shepler
-3 more bytes from @Daniel Shepler
import numpy
c=lambda n:[n]+[numpy.lcm(i,j)for i in range(1,n)for j in c(n-i)]
l=lambda n:max(c(n))
Try it online!
Brute force method: find all possible sequences a,b,c,... where a+b+c+...=n, then pick the one with the highest lcm.
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
edited 7 hours ago
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
answered 8 hours ago
HiatsuHiatsu
1716 bronze badges
1716 bronze badges
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
|
show 1 more comment
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
Incidentally, I have a Python 3 + numpy solution running 87 bytes.
$endgroup$
– Daniel Schepler
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
I don't know enough about numpy to figure out how to do that, so I suggest you just post your solution separately.
$endgroup$
– Hiatsu
8 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
Well, I was planning to wait for a while to post it.
$endgroup$
– Daniel Schepler
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
I just realized you posted this challenge. Sorry, I'll do my best.
$endgroup$
– Hiatsu
7 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
$begingroup$
Since it came up, you should not try to run this solution for any input higher than 26, even with caching. After nearly freezing my computer for about two and a half hours, the process was killed without giving out an answer. This is not surprising, since it had to calculate the maximum of summing each of about 2^26 lists, which are not memory efficient.
$endgroup$
– Hiatsu
2 hours ago
|
show 1 more comment
$begingroup$
JavaScript (ES6), 92 bytes
Computes the maximum value of $operatornamelcm(a_1,ldots,a_k)$ where $a_1+ldots+a_k$ is a partition of $n$.
f=(n,i=1,l=m=0)=>n?i>n?m:f(n-i,i,l*i/(G=(a,b)=>b?G(b,a%b):a)(l,i)||i)&f(n,i+1,l)|m:m=l>m?l:m
Try it online!
JavaScript (ES6), 95 bytes
f=(n,i=1,m)=>i>>n?m:f(n,i+1,i<m|(g=(n,k=2,p=0)=>k>n?p:n%k?p+g(n,k+1):g(n/k,k,p*k||k))(i)>n?m:i)
Try it online!
How?
We define:
$$cases
g(1)=0\
g(n)=sum_j=1^Np_j^k_jquadtextforenspace n>1enspacetextandenspace n=prod_j=1^Np_j^k_j
$$
(this is A008475)
Then we use the formula (from A000793):
$$f(n)=max_g(k)le nk$$
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 92 bytes
Computes the maximum value of $operatornamelcm(a_1,ldots,a_k)$ where $a_1+ldots+a_k$ is a partition of $n$.
f=(n,i=1,l=m=0)=>n?i>n?m:f(n-i,i,l*i/(G=(a,b)=>b?G(b,a%b):a)(l,i)||i)&f(n,i+1,l)|m:m=l>m?l:m
Try it online!
JavaScript (ES6), 95 bytes
f=(n,i=1,m)=>i>>n?m:f(n,i+1,i<m|(g=(n,k=2,p=0)=>k>n?p:n%k?p+g(n,k+1):g(n/k,k,p*k||k))(i)>n?m:i)
Try it online!
How?
We define:
$$cases
g(1)=0\
g(n)=sum_j=1^Np_j^k_jquadtextforenspace n>1enspacetextandenspace n=prod_j=1^Np_j^k_j
$$
(this is A008475)
Then we use the formula (from A000793):
$$f(n)=max_g(k)le nk$$
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
$endgroup$
add a comment |
$begingroup$
JavaScript (ES6), 92 bytes
Computes the maximum value of $operatornamelcm(a_1,ldots,a_k)$ where $a_1+ldots+a_k$ is a partition of $n$.
f=(n,i=1,l=m=0)=>n?i>n?m:f(n-i,i,l*i/(G=(a,b)=>b?G(b,a%b):a)(l,i)||i)&f(n,i+1,l)|m:m=l>m?l:m
Try it online!
JavaScript (ES6), 95 bytes
f=(n,i=1,m)=>i>>n?m:f(n,i+1,i<m|(g=(n,k=2,p=0)=>k>n?p:n%k?p+g(n,k+1):g(n/k,k,p*k||k))(i)>n?m:i)
Try it online!
How?
We define:
$$cases
g(1)=0\
g(n)=sum_j=1^Np_j^k_jquadtextforenspace n>1enspacetextandenspace n=prod_j=1^Np_j^k_j
$$
(this is A008475)
Then we use the formula (from A000793):
$$f(n)=max_g(k)le nk$$
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
$endgroup$
JavaScript (ES6), 92 bytes
Computes the maximum value of $operatornamelcm(a_1,ldots,a_k)$ where $a_1+ldots+a_k$ is a partition of $n$.
f=(n,i=1,l=m=0)=>n?i>n?m:f(n-i,i,l*i/(G=(a,b)=>b?G(b,a%b):a)(l,i)||i)&f(n,i+1,l)|m:m=l>m?l:m
Try it online!
JavaScript (ES6), 95 bytes
f=(n,i=1,m)=>i>>n?m:f(n,i+1,i<m|(g=(n,k=2,p=0)=>k>n?p:n%k?p+g(n,k+1):g(n/k,k,p*k||k))(i)>n?m:i)
Try it online!
How?
We define:
$$cases
g(1)=0\
g(n)=sum_j=1^Np_j^k_jquadtextforenspace n>1enspacetextandenspace n=prod_j=1^Np_j^k_j
$$
(this is A008475)
Then we use the formula (from A000793):
$$f(n)=max_g(k)le nk$$
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
edited 6 hours ago
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
answered 8 hours ago
ArnauldArnauld
91.5k7 gold badges107 silver badges373 bronze badges
91.5k7 gold badges107 silver badges373 bronze badges
add a comment |
add a comment |
$begingroup$
Perl 6, 50 bytes
max .map:+(.[$_],.[@^a]...$_,)o&permutations
Try it online!
Checks all permutations directly, like @histocrat's Ruby solution.
Explanation
&permutations # Permutations of [0;n)
o # Feed into block
.map: # Map permutations
... # Construct sequence
.[$_] # Start with permutation applied to itself [1]
,.[@^a] # Generate next item by applying permutation again
$_, # Until it matches original permutation [2]
+( ) # Length of sequence
max # Find maximum
1 We can use any sequence of n distinct items for the check, so we simply take the permutation itself.
2 If the endpoint is a container, the ... sequence operator smartmatches against the first item. So we have to pass a single-element list.
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
$endgroup$
add a comment |
$begingroup$
Perl 6, 50 bytes
max .map:+(.[$_],.[@^a]...$_,)o&permutations
Try it online!
Checks all permutations directly, like @histocrat's Ruby solution.
Explanation
&permutations # Permutations of [0;n)
o # Feed into block
.map: # Map permutations
... # Construct sequence
.[$_] # Start with permutation applied to itself [1]
,.[@^a] # Generate next item by applying permutation again
$_, # Until it matches original permutation [2]
+( ) # Length of sequence
max # Find maximum
1 We can use any sequence of n distinct items for the check, so we simply take the permutation itself.
2 If the endpoint is a container, the ... sequence operator smartmatches against the first item. So we have to pass a single-element list.
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
$endgroup$
add a comment |
$begingroup$
Perl 6, 50 bytes
max .map:+(.[$_],.[@^a]...$_,)o&permutations
Try it online!
Checks all permutations directly, like @histocrat's Ruby solution.
Explanation
&permutations # Permutations of [0;n)
o # Feed into block
.map: # Map permutations
... # Construct sequence
.[$_] # Start with permutation applied to itself [1]
,.[@^a] # Generate next item by applying permutation again
$_, # Until it matches original permutation [2]
+( ) # Length of sequence
max # Find maximum
1 We can use any sequence of n distinct items for the check, so we simply take the permutation itself.
2 If the endpoint is a container, the ... sequence operator smartmatches against the first item. So we have to pass a single-element list.
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
$endgroup$
Perl 6, 50 bytes
max .map:+(.[$_],.[@^a]...$_,)o&permutations
Try it online!
Checks all permutations directly, like @histocrat's Ruby solution.
Explanation
&permutations # Permutations of [0;n)
o # Feed into block
.map: # Map permutations
... # Construct sequence
.[$_] # Start with permutation applied to itself [1]
,.[@^a] # Generate next item by applying permutation again
$_, # Until it matches original permutation [2]
+( ) # Length of sequence
max # Find maximum
1 We can use any sequence of n distinct items for the check, so we simply take the permutation itself.
2 If the endpoint is a container, the ... sequence operator smartmatches against the first item. So we have to pass a single-element list.
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
edited 3 hours ago
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
answered 4 hours ago
nwellnhofnwellnhof
8,1101 gold badge12 silver badges29 bronze badges
8,1101 gold badge12 silver badges29 bronze badges
add a comment |
add a comment |
$begingroup$
Haskell, 70 bytes
f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]
Try it online!
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
$endgroup$
add a comment |
$begingroup$
Haskell, 70 bytes
f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]
Try it online!
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
$endgroup$
add a comment |
$begingroup$
Haskell, 70 bytes
f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]
Try it online!
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
$endgroup$
Haskell, 70 bytes
f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]
Try it online!
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
answered 2 hours ago
niminimi
33.8k3 gold badges27 silver badges91 bronze badges
33.8k3 gold badges27 silver badges91 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%2f191074%2fcalculate-landaus-function%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
