Calcular la función de Landau

19

La función de Landau ( OEIS A000793 ) da el orden máximo de un elemento del grupo simétrico . Aquí, el orden de una permutación es el número entero positivo más pequeño tal que es la identidad, que es igual al mínimo común múltiplo de las longitudes de los ciclos en la descomposición del ciclo de la permutación. Por ejemplo, que se logra, por ejemplo, con (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14). $g(n)$ $S_n$ $\pi$ $k$ $\pi^k$ $g(14) = 84$

Por lo tanto, también es igual al valor máximo de donde con enteros positivos. $g(n)$ $\operatorname{lcm}(a_1, \ldots, a_k)$ $a_1 + \cdots + a_k = n$ $a_1, \ldots, a_k$

Problema

Escriba una función o programa que calcule la función de Landau.

Entrada

Un entero positivo . $n$

Salida

$g(n)$ , el orden máximo de un elemento del grupo simétrico . $S_n$

Ejemplos

Puntuación

Esto es code-golf : el programa más corto en bytes gana. (Sin embargo, las implementaciones más cortas en varios idiomas son bienvenidas).

Tenga en cuenta que no hay requisitos impuestos en tiempo de ejecución; por lo tanto, su implementación no necesariamente necesita poder generar todos los resultados del ejemplo anterior en un tiempo razonable.

Las lagunas estándar están prohibidas.

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

Respuestas:

9

05AB1E , 6 bytes

Åœ€.¿Z

Pruébalo en línea!

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

Mugriento
fuente

10

Wolfram Language (Mathematica) , 44 bytes

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

Pruébalo en línea!

Wolfram Language (Mathematica) , 31 bytes

@DanielSchepler tiene una mejor solución:

Max[LCM@@@IntegerPartitions@#]&

Pruébalo en línea!

romano
fuente

No estoy tan familiarizado con el idioma, pero Max[Apply@LCM/@IntegerPartitions@#]&parece funcionar para mí y daría 36 bytes si es correcto.

Daniel Schepler

2

@DanielSchepler sí, super! ¿Por qué no lo propones como una solución separada? Incluso puedes hacerlo Max[LCM@@@IntegerPartitions@#]&por 31 bytes , porque lo @@@hace Applyen el nivel 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])

Pruébalo en línea!

Una función recursiva que rastrea el resto nde la partición y el LCM en ejecución d. Tenga en cuenta que esto significa que no necesitamos rastrear los números reales en la partición o cuántos de ellos hemos usado. Intentamos cada posible parte siguiente n-m, reemplazando ncon lo que queda my dcon lcm(d,n-m). Tomamos el máximo de esos resultados recursivos y de dsí mismo. Cuando no queda nada n=0, el resultado es justo d.

Lo complicado es que Python no tiene ninguna función incorporada para LCM, GCD o factorización prima. Para hacerlo lcm(d,m-n), generamos una lista de múltiplos de d, y tomamos el valor que alcanza el módulo mínimo n-m, es decir, con key=(n-m).__rmod__. Dado minque dará el valor anterior en caso de empate, este es siempre el primer múltiplo distinto de cero ddivisible por n-m, por lo que su LCM. Solo tenemos múltiplos de dhasta d*(n-m)garantizar que lleguemos al LCM, pero es más corto de escribir d<<n(que es d*2**n), lo que es suficiente con que los límites superiores de Python sean exclusivos.

La mathbiblioteca de Python 3 tiene gcd(pero no lcm) después de 3.5, que es unos pocos bytes más cortos. Gracias a @Joel por acortar la importación.

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

Pruébalo en línea!

Usar numpy's lcmes aún más corto.

Python con numpy , 77 bytes

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

Pruébalo en línea!

xnor
fuente

Usar from math import*es de 85 bytes y usar import math+ math.gcd(...)es de 84 bytes. Lo mismo se aplica a numpy.

Joel

@ Joel Gracias, me olvidé de eso.

xnor

Gracias @ Joel, me había olvidado de actualizar la cuenta de bytes, los dos son 77. numpy's longitud de 5 es el punto de equilibrio para import*.

xnor

Correcto. En ese caso, prefiero usarlo import numpyporque numpy.maxanularía el Python incorporado max(lo mismo para min) si from numpy import*se usa. Aquí no causa problemas, pero todos sabemos que import*no es una buena práctica de programación en general.

Joel

@Joel Aunque import*sin duda es una mala práctica, no creo que realmente sobrescriba a Python miny max, por lo tanto, la confusión sería que alguien espera la función de Numpy y obtiene la base.

xnor

4

Haskell , 44 bytes

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

Pruébalo en línea!

xnor
fuente

3

Jalea , 7 bytes

Œṗæl/€Ṁ

Pruébalo en línea!

Un enlace monádico que toma un número entero como argumento y devuelve un número entero.

Explicación

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

Nick Kennedy
fuente

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

Pruébalo en línea!

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)

Pruébalo en línea!

¿Cómo?

Definimos:

{\begin{cases} g (1) = 0 \\ g (n) = \sum_{j = 1}^{N} {p_{j}}^{k_{j}} for n > 1 and 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} }$

(esto es A008475 )

Luego usamos la fórmula (de A000793 ):

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

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

Arnauld
fuente

3

Perl 6 , 50 bytes

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

Pruébalo en línea!

Comprueba todas las permutaciones directamente, como la solución Ruby de @ histocrat.

Explicación

                                     &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 cualquier secuencia de n elementos distintos para la verificación, por lo que simplemente tomamos la permutación en sí.

² Si el punto final es un contenedor, el ...operador de secuencia coincide con el primer elemento. Entonces tenemos que pasar una lista de un solo elemento.

nwellnhof
fuente

2

Ruby , 77 bytes

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

Pruébalo en línea!

(1..) la sintaxis de rango infinito es demasiado nueva para TIO, por lo que el enlace establece un límite superior arbitrario.

Esto utiliza la definición directa: enumere todas las permutaciones posibles, luego pruebe cada una mutando ahasta que vuelva a su posición original (lo que también significa convenientemente que puedo mutar la matriz original en cada bucle).

histocrat
fuente

2

Gaia , 25 23 22 bytes

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

Pruébalo en línea!

No tener LCM o particiones enteras hace que este enfoque sea bastante largo.

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


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

Giuseppe
fuente

2

Haskell, 70 67 bytes

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

Pruébalo en línea!

Editar: -3 bytes gracias a @xnor.

nimi
fuente

Creo que debería funcionar mapM(:[1..n]), ya que el elemento extra es inofensivo.

xnor

1

Python 3 + numpy, 115 102 99 bytes

-13 bytes gracias a @Daniel Shepler

-3 bytes más 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))

Pruébalo en línea!

Método de fuerza bruta: encuentre todas las secuencias posibles a, b, c, ... donde a + b + c + ... = n, luego elija la que tenga el mcm más alto.

Hiatsu
fuente

Por cierto, tengo una solución numpy Python 3 + que ejecuta 87 bytes.

Daniel Schepler

No sé lo suficiente sobre numpy para descubrir cómo hacerlo, así que le sugiero que publique su solución por separado.

Hiatsu

Bueno, estaba planeando esperar un tiempo para publicarlo.

Daniel Schepler

Me acabo de dar cuenta de que publicaste este desafío. Lo siento, haré lo mejor que pueda.

Hiatsu

1

Si cambia cpara devolver un conjunto y memorizarlo, no funciona mal (aunque es cierto que se deshace un poco): tio.run/##RY1BCsIwEEX3PUWWM1CLoiuhV/AKEsfUTkkmIU3AWnr2Ggvq7vM@//…

Daniel Schepler

0

Pyth , 24 15 bytes

eSm.U/*bZibZd./

Pruébalo en línea!

             ./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: prestó atención y notó que Pyth en realidad tiene un GCD incorporado ( i).

ar4093
fuente