Calculate Landau's function

Question

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 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.

Answer 1

05AB1E, 6 bytes

Åœ€.¿Z

Try it online!

    Ŝ       # integer partitions of the input
      €.¿    # lcm of each
         Z   # maximum

Answer 2

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!

Answer 3

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!

Answer 4

Haskell, 44 bytes

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

Try it online!

Answer 5

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

Answer 6

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$$

Answer 7

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

¹ We can use any sequence of n distinct items for the check, so we simply take the permutation itself.

² If the endpoint is a container, the ... sequence operator smartmatches against the first item. So we have to pass a single-element list.

Answer 8

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).

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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).