19
\$\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 \$\operatorname{lcm}(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 : 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.

\$\endgroup\$

12 Answers 12

9
\$\begingroup\$

05AB1E, 6 bytes

Åœ€.¿Z

Try it online!

    Ŝ       # integer partitions of the input
      €.¿    # lcm of each
         Z   # maximum
\$\endgroup\$
10
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

Max[PermutationOrder/@Permutations@Range@#]&

Try it online!

Wolfram Language (Mathematica), 31 bytes

@DanielSchepler has a better solution:

Max[LCM@@@IntegerPartitions@#]&

Try it online!

\$\endgroup\$
  • \$\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 Aug 30 at 17:22
  • 2
    \$\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 Aug 30 at 17:39
4
\$\begingroup\$

Python, 87 bytes

f=lambda n,d=1:max([f(m,min(range(d,d<<n,d),key=(n-m).__rmod__))for m in range(n)]+[d])

Try it online!

A recursive function that tracks the remaining n to partition and the running LCM d. Note that this means we don't need to track the actual numbers in the partition or how many of them we've used. We try each possible next part, n-m, replacing n with what's left m, and d with lcm(d,n-m). We take the maximum of those recursive results and d itself. When nothing remains n=0, the result ist just d.

The tricky thing is that Python doesn't have any built-ins for LCM, GCD, or prime factorization. To do lcm(d,m-n), we generate a list of multiples of d, and take the value attaining the minimum modulo n-m, that is with key=(n-m).__rmod__. Since min will give the earlier value in case of a tie, this is always the first nonzero multiple of d that's divisible by n-m, so their LCM. We only multiples of d up to d*(n-m) to be guaranteed to hit the LCM, but it's shorter to write d<<n (which is d*2**n) which suffices with Python's upper bounds being exclusive.

Python 3's math library has gcd (but not lcm) after 3.5, which is a few bytes shorter. Thanks to @Joel for shortening the import.

Python 3.5+, 84 bytes

import math
f=lambda n,d=1:max([f(m,d*(n-m)//math.gcd(n-m,d))for m in range(n)]+[d])

Try it online!

Using numpy's lcm is yet shorter.

Python with numpy, 77 bytes

from numpy import*
f=lambda n,d=1:max([f(m,lcm(d,n-m))for m in range(n)]+[d])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Using from math import* is 85 bytes and using import math + math.gcd(...) is 84 bytes. The same applies to numpy. \$\endgroup\$ – Joel Aug 31 at 3:21
  • \$\begingroup\$ @Joel Thanks, I forgot about that. \$\endgroup\$ – xnor Aug 31 at 3:25
  • \$\begingroup\$ @Joel Thanks, I had forgotten to update the byte count, they're both 77. numpy's length of 5 is the break-even point for import*. \$\endgroup\$ – xnor Aug 31 at 3:30
  • \$\begingroup\$ Right. In that case I prefer to use import numpy because numpy.max would override Python's built-in max (same for min) if from numpy import* is used. It does not cause problems here but we all know that import* is not a good programming practice in general. \$\endgroup\$ – Joel Aug 31 at 3:34
  • \$\begingroup\$ @Joel While import* is no doubt bad practice, I don't think it actually overwrites Python's min and max, so the confusion would be someone expecting numpy's function and getting the base one. \$\endgroup\$ – xnor Aug 31 at 3:39
4
\$\begingroup\$

Haskell, 44 bytes

(%1)
n%t=maximum$t:[(n-d)%lcm t d|d<-[1..n]]

Try it online!

\$\endgroup\$
3
\$\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
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 92 bytes

Computes the maximum value of \$\operatorname{lcm}(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}^{N}{p_j}^{k_j}\quad\text{for}\enspace n>1\enspace\text{and}\enspace n=\prod_{j=1}^{N}{p_j}^{k_j} }$$

(this is A008475)

Then we use the formula (from A000793):

$$f(n)=\max_{g(k)\le n}k$$

\$\endgroup\$
3
\$\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.

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

Ruby, 77 bytes

f=->n{a=*0...n;a.permutation.map{|p|(1..).find{a.map!{|i|p[i]}==a.sort}}.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).

\$\endgroup\$
2
\$\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
\$\endgroup\$
2
\$\begingroup\$

Haskell, 70 67 bytes

f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]

Try it online!

Edit: -3 bytes thanks to @xnor.

\$\endgroup\$
  • \$\begingroup\$ I think it should work to do mapM(:[1..n]), since the extra element is harmless. \$\endgroup\$ – xnor Aug 31 at 2:18
1
\$\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.

\$\endgroup\$
  • \$\begingroup\$ Incidentally, I have a Python 3 + numpy solution running 87 bytes. \$\endgroup\$ – Daniel Schepler Aug 30 at 17:01
  • \$\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 Aug 30 at 17:03
  • \$\begingroup\$ Well, I was planning to wait for a while to post it. \$\endgroup\$ – Daniel Schepler Aug 30 at 17:08
  • \$\begingroup\$ I just realized you posted this challenge. Sorry, I'll do my best. \$\endgroup\$ – Hiatsu Aug 30 at 17:11
  • 1
    \$\begingroup\$ If you change c to return a set and memoize it doesn't do badly at all (though admittedly it does ungolf a bit): tio.run/##RY1BCsIwEEX3PUWWM1CLoiuhV/AKEsfUTkkmIU3AWnr2Ggvq7vM@//… \$\endgroup\$ – Daniel Schepler Aug 30 at 22:55
0
\$\begingroup\$

Pyth, 24 15 bytes

eSm.U/*bZibZd./

Try it online!

             ./Q  # List of partitions of the input
  m               # map that over lambda d:
   .U       d     # reduce d (with starting value first element of the list) on lambda b,Z:
     /*bZgbZ      # (b * Z) / GCD(b, Z)
 S                # this gives the list of lcms of all partitions. Sort this
e                 # and take the last element (maximum)

-9 bytes: paid attention and noticed that Pyth actually has a GCD builtin (i).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.