Calcular a função do Landau

19

A função de Landau g(n) ( OEIS A000793 ) fornece a ordem máxima de um elemento do grupo simétrico Sn . Aqui, a ordem de uma permutação π é o menor número inteiro positivo k modo que πk é a identidade - que é igual ao múltiplo menos comum dos comprimentos dos ciclos na decomposição do ciclo de permutação. Por exemplo, g(14)=84 que é alcançado, por exemplo, por (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14).

Portanto, g(n) é também igual ao valor máximo de lcm(a1,,ak) em que a1++ak=n com a1,,ak inteiros positivos.

Problema

Escreva uma função ou programa que calcule a função do Landau.

Entrada

Um número inteiro positivo n .

Resultado

g(n) , a ordem máxima de um elemento do grupo simétricoSn .

Exemplos

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

Ponto

Este é o : O programa mais curto em bytes vence. (No entanto, as implementações mais curtas em vários idiomas são bem-vindas.)

Observe que não há requisitos impostos no tempo de execução; portanto, sua implementação não precisa necessariamente ser capaz de gerar todos os resultados do exemplo acima em um tempo razoável.

As brechas padrão são proibidas.

Daniel Schepler
fonte

Respostas:

10

Wolfram Language (Mathematica) , 44 bytes

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

Experimente online!

Wolfram Language (Mathematica) , 31 bytes

@DanielSchepler tem uma solução melhor:

Max[LCM@@@IntegerPartitions@#]&

Experimente online!

romano
fonte
Não Max[Apply@LCM/@IntegerPartitions@#]&estou familiarizado com o idioma - mas parece funcionar para mim e daria 36 bytes se estiver correto.
Daniel Schepler
2
@DanielSchepler yes, super! Por que você não propõe isso como uma solução separada? Você mesmo pode fazer Max[LCM@@@IntegerPartitions@#]&para 31 bytes , porque @@@faz Applyno nível 1.
Roman
4

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

Experimente online!

Uma função recursiva que rastreia o restante nda partição e o LCM em execução d. Observe que isso significa que não precisamos rastrear os números reais na partição ou quantos deles usamos. Tentamos cada parte possível n-m, substituindo npelo que resta me dpor lcm(d,n-m). Tomamos o máximo desses resultados recursivos e de dsi mesmos . Quando nada resta n=0, o resultado é apenasd .

O mais complicado é que o Python não possui nenhum built-in para LCM, GCD ou fatoração principal. Para isso lcm(d,m-n), geramos uma lista de múltiplos de de obtemos o valor atingindo o módulo mínimo n-m, ou seja, com key=(n-m).__rmod__. Como mindará o valor anterior em caso de empate, esse é sempre o primeiro múltiplo diferente de zero dque é divisível por n-m, portanto, seu LCM. Temos apenas múltiplos de daté a d*(n-m)garantia de atingir o LCM, mas é mais curto para escrever d<<n(que éd*2**n ) o que é suficiente, sendo os limites superiores do Python exclusivos.

A mathbiblioteca do Python 3 tem gcd(mas não lcm) depois do 3.5, que é alguns bytes mais curto. Agradecemos a @Joel por reduzir a importação.

Python 3.5 ou superior , 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])

Experimente online!

Usando numpy's lcmé ainda mais curto.

Python com numpy , 77 bytes

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

Experimente online!

xnor
fonte
Usar from math import*é 85 bytes e usar import math+ math.gcd(...)é 84 bytes. O mesmo se aplica a numpy.
Joel
@ Joel Obrigado, eu esqueci disso.
xnor 31/08
@ Joel Obrigado, eu tinha me esquecido de atualizar a contagem de bytes, ambos são 77. numpyO comprimento de 5 é o ponto de equilíbrioimport* .
xnor 31/08
Certo. Nesse caso, prefiro usar import numpyporque numpy.maxsubstituiria o built-in do Python max(o mesmo para min) se from numpy import*for usado. Não causa problemas aqui, mas todos sabemos que import*não é uma boa prática de programação em geral.
Joel
@Joel Embora import*seja sem dúvida uma má prática, não acho que ele substitua o Python mine max, portanto, a confusão seria alguém esperando a função de numpy e obtendo a base.
xnor 31/08
3

Geléia , 7 bytes

Œṗæl/€Ṁ

Experimente online!

Um link monádico usando um número inteiro como argumento e retornando um número inteiro.

Explicação

Œṗ      | Integer partitions
  æl/€  | Reduce each using LCM
      Ṁ | Maximum
Nick Kennedy
fonte
3

JavaScript (ES6), 92 bytes

lcm(uma1,...,umak)uma1+...+umakn

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

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

Experimente online!

Quão?

Nós definimos:

{g(1)=0 0g(n)=j=1Npjkjparan>1en=j=1Npjkj

(este é A008475 )

Em seguida, usamos a fórmula (de A000793 ):

f(n)=maxg(k)nk

Arnauld
fonte
3

Perl 6 , 50 bytes

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

Experimente online!

Verifica todas as permutações diretamente, como a solução Ruby do histocrat.

Explicação

                                     &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 Podemos usar qualquer sequência de n itens distintos para a verificação, portanto, simplesmente fazemos a própria permutação.

2 Se o terminal for um contêiner, o ...operador de sequência será compatível com o primeiro item. Portanto, temos que passar uma lista de elemento único.

Nwellnhof
fonte
2

Ruby , 77 bytes

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

Experimente online!

(1..) A sintaxe do intervalo infinito é muito nova para o TIO, portanto, o link define um limite superior arbitrário.

Isso usa a definição direta - enumere todas as permutações possíveis e, em seguida, teste cada uma delas mudando aaté que ela retorne à sua posição original (o que também significa convenientemente que eu posso apenas alterar a matriz original em cada loop).

histocrata
fonte
2

Gaia , 25 23 22 bytes

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

Experimente online!

Não ter partições LCM ou inteiras torna essa abordagem bastante longa.

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


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

Haskell, 70 67 bytes

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

Experimente online!

Edit: -3 bytes graças a @xnor.

nimi
fonte
Eu acho que deveria funcionar mapM(:[1..n]), já que o elemento extra é inofensivo.
xnor 31/08
1

Python 3 + numpy, 115 102 99 bytes

-13 bytes graças a @Daniel Shepler

-3 bytes a mais de @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))

Experimente online!

Método da força bruta: encontre todas as seqüências possíveis a, b, c, ... em que a + b + c + ... = n e escolha a que tiver o lcm mais alto.

Hiatsu
fonte
Aliás, eu tenho uma solução numpy Python 3 + executando 87 bytes.
Daniel Schepler
Não sei o suficiente sobre o entorpecido para descobrir como fazer isso, então sugiro que você publique sua solução separadamente.
Hiatsu
Bem, eu estava planejando esperar um pouco para publicá-lo.
Daniel Schepler
Acabei de perceber que você postou esse desafio. Desculpe, farei o meu melhor.
Hiatsu 30/08
1
Se você alterar cpara retornar um conjunto e memorizar, ele não funciona mal (apesar de admitir que faz um pouco de besteira
Daniel Schepler em
0

Pitão , 24 15 bytes

eSm.U/*bZibZd./

Experimente 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: preste atenção e notei que o Pyth realmente possui um GCD embutido ( i).

ar4093
fonte