Funkcja Landaua $g(n)$ ( OEIS A000793 ) podaje maksymalny porządek elementu grupy symetrycznej $S_n$ . Tutaj porządek permutacji $\pi$ jest najmniejszą dodatnią liczbą całkowitą $k$ tak że $\pi^k$ jest identycznością - która jest równa najmniejszej wspólnej wielokrotności długości cykli w rozkładzie cyklu permutacji. Na przykład $g(14) = 84$ co osiąga się na przykład przez (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14).

Dlatego też, $g(n)$ jest równa maksymalnej wartości $\operatorname{lcm}(a_1, \ldots, a_k)$ gdzie 1 + ⋯ + k = n z o 1 , ... , K dodatnimi liczbami całkowitymi.$a_1 + \cdots + a_k = n$$a_1, \ldots, a_k$

Problem

Napisz funkcję lub program, który oblicza funkcję Landaua.

Wejście

Dodatnia liczba całkowita $n$ .

Wynik

$g(n)$ , maksymalna kolejność elementu grupy symetrycznej$S_n$ .

Przykłady

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

Wynik

To jest golf-golf : Wygrywa najkrótszy program w bajtach. (Niemniej mile widziane są najkrótsze wdrożenia w wielu językach).

Pamiętaj, że nie ma żadnych wymagań dotyczących czasu działania; dlatego twoja implementacja niekoniecznie musi być w stanie wygenerować wszystkie powyższe wyniki przykładowe w rozsądnym czasie.

Standardowe luki są zabronione.

05AB1E , 6 bajtów

Åœ€.¿Z

Wypróbuj online!

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

Wolfram Language (Mathematica) , 44 bajty

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

Wypróbuj online!

Wolfram Language (Mathematica) , 31 bajtów

@DanielSchepler ma lepsze rozwiązanie:

Max[LCM@@@IntegerPartitions@#]&

Wypróbuj online!

Python , 87 bajtów

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

Wypróbuj online!

Funkcja rekurencyjna, która śledzi pozostałe ndo partycji i działającego LCM d. Zauważ, że oznacza to, że nie musimy śledzić faktycznych liczb na partycji ani tego, ile z nich wykorzystaliśmy. Staramy każdy możliwy następna część, n-mzastępując ntym, co pozostało m, i dz lcm(d,n-m). Bierzemy maksimum tych rekurencyjnych wyników i dsiebie. Kiedy nic nie pozostaje n=0, wynik jest po prostu d.

Problem polega na tym, że Python nie ma żadnych wbudowanych funkcji LCM, GCD ani faktoryzacji liczb pierwszych. Aby to zrobić lcm(d,m-n), generujemy listę wielokrotności di bierzemy wartość osiągającą minimalny moduł n-m, czyli key=(n-m).__rmod__. Ponieważ minpoda wcześniejszą wartość w przypadku remisu, jest to zawsze pierwsza niezerowa wielokrotność dpodzielna przez n-m, więc ich LCM. My tylko wielokrotności d, aby d*(n-m)zagwarantować trafienie w LCM, ale krótsze jest pisanie d<<n(co jest d*2**n), co wystarcza, gdy górne granice Pythona są wyłączne.

mathBiblioteka Pythona 3 ma gcd(ale nie lcm) po wersji 3.5, która jest kilka bajtów krótsza. Dzięki @Joel za skrócenie importu.

Python 3.5+ , 84 bajty

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

Wypróbuj online!

Korzystanie numpyz lcmjest jeszcze krótsze.

Python z numpy , 77 bajtów

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

Wypróbuj online!

Haskell , 44 bajty

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

Wypróbuj online!

Galaretka , 7 bajtów

Œṗæl/€Ṁ

Wypróbuj online!

Łącze monadyczne przyjmujące za argument liczbę całkowitą i zwracające liczbę całkowitą.

Wyjaśnienie

Œṗ      | Integer partitions
  æl/€  | Reduce each using LCM
      Ṁ | Maximum

JavaScript (ES6), 92 bajty

$\operatorname{lcm}(a_1,\ldots,a_k)$$a_1+\ldots+a_k$$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

Wypróbuj online!

JavaScript (ES6), 95 bajtów

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)

Wypróbuj online!

W jaki sposób?

Definiujemy:

(to jest A008475 )

Następnie używamy formuły (z A000793 ):

Perl 6 , 50 bajtów

{max .map:{+(.[$_],{.[@^a]}...$_,)}}o&permutations

Wypróbuj online!

Sprawdza bezpośrednio wszystkie permutacje, takie jak rozwiązanie Ruby @ histocrat.

Wyjaśnienie

                                     &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

¹ Do sprawdzenia możemy użyć dowolnej sekwencji n różnych elementów, więc po prostu bierzemy permutację.

² Jeśli punktem końcowym jest kontener, ...operator sekwencji dopasowuje inteligentnie do pierwszego elementu. Musimy więc przekazać listę pojedynczego elementu.

Rubinowy , 77 bajtów

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

Wypróbuj online!

(1..) składnia nieskończonego zakresu jest zbyt nowa dla TIO, więc link ustawia dowolną górną granicę.

Wykorzystuje to bezpośrednią definicję - wylicz wszystkie możliwe kombinacje, a następnie przetestuj każdą z nich, mutując, aaż wróci do swojej pierwotnej pozycji (co również wygodnie oznacza, że ​​mogę po prostu mutować oryginalną tablicę w każdej pętli).

Gaia , 25 23 22 bajtów

,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉

Wypróbuj online!

Brak partycji LCM lub liczb całkowitych powoduje, że takie podejście jest dość długie.

,:Π¤d¦&⊢⌉/		;* helper function: LCM of 2 inputs


1w&ḍΣ¦¦			;* push integer partitions
         ¦		;* for each
       ⇈⊢		;* Reduce by helper function
	  ⌉		;* and take the max

Haskell, 70 67 bajtów

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

Wypróbuj online!

Edycja: -3 bajty dzięki @xnor.

Python 3 + numpy, 115 102 99 bajtów

-13 bajtów dzięki @Daniel Shepler

-3 więcej bajtów od @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))

Wypróbuj online!

Metoda brutalnej siły: znajdź wszystkie możliwe sekwencje a, b, c, ... gdzie a + b + c + ... = n, a następnie wybierz tę o najwyższym lcm.

Pyth , 24 15 bajtów

eSm.U/*bZibZd./

Wypróbuj 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 bajtów: zwróciłem uwagę i zauważyłem, że Pyth ma wbudowaną funkcję GCD ( i).