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 $S_n$ . Aqui, a ordem de uma permutação $\pi$ é o menor número inteiro positivo $k$ modo que $\pi^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 $\operatorname{lcm}(a_1, \ldots, a_k)$ em que $a_1 + \cdots + a_k = n$ com $a_1, \ldots, a_k$ 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étrico $S_n$ .

Exemplos

Ponto

Este é o código-golf : 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.

code-golf math arithmetic permutations integer-partitions Daniel Schepler
fonte

Respostas:

9

05AB1E , 6 bytes

Åœ€.¿Z

Experimente online!

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

Grimmy
fonte

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

4

Haskell , 44 bytes

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

Experimente online!

xnor
fonte

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

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

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:

{\begin{cases} g (1) = 0 0 \\ g (n) = \sum_{j = 1}^{N} {p_{j}}^{k_{j}} para n > 1 e n = \prod_{j = 1}^{N} {p_{j}}^{k_{j}} \end{cases}

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

(este é A008475 )

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

f (n) = max_{g (k) \leq n} k

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

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

¹ Podemos usar qualquer sequência de n itens distintos para a verificação, portanto, simplesmente fazemos a própria permutação.

² 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