Calculer la fonction de Landau

19

La fonction de Landau $g(n)$ ( OEIS A000793 ) donne l'ordre maximum d'un élément du groupe symétrique $S_n$ . Ici, l'ordre d'une permutation $\pi$ est le plus petit entier positif $k$ tel que $\pi^k$ est l'identité - qui est égal au plus petit multiple commun des longueurs des cycles dans la décomposition du cycle de la permutation. Par exemple, $g(14) = 84$ qui est obtenu par exemple par (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14).

Par conséquent, $g(n)$ est également égal à la valeur maximale de $\operatorname{lcm}(a_1, \ldots, a_k)$ où avec entiers positifs. $a_1 + \cdots + a_k = n$ $a_1, \ldots, a_k$

Problème

Écrivez une fonction ou un programme qui calcule la fonction de Landau.

Contribution

Un entier positif . $n$

Production

$g(n)$ , l'ordre maximum d'un élément du groupe symétrique . $S_n$

Exemples

But

C'est le code-golf : le programme le plus court en octets gagne. (Néanmoins, les implémentations les plus courtes dans plusieurs langues sont les bienvenues.)

Notez qu'aucune exigence n'est imposée à l'exécution; par conséquent, votre implémentation ne doit pas nécessairement être en mesure de générer tous les résultats d'exemple ci-dessus dans un délai raisonnable.

Les failles standard sont interdites.

code-golf math arithmetic permutations integer-partitions Daniel Schepler
la source

Réponses:

9

05AB1E , 6 octets

Åœ€.¿Z

Essayez-le en ligne!

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

Grimmy
la source

10

Wolfram Language (Mathematica) , 44 octets

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

Essayez-le en ligne!

Wolfram Language (Mathematica) , 31 octets

@DanielSchepler a une meilleure solution:

Max[LCM@@@IntegerPartitions@#]&

Essayez-le en ligne!

romain
la source

Pas très familier avec la langue - mais Max[Apply@LCM/@IntegerPartitions@#]&semble fonctionner pour moi et donnerait 36 octets si c'est correct.

Daniel Schepler

2

@DanielSchepler oui, super! Pourquoi ne le proposez-vous pas comme solution distincte? Vous pouvez même le faire Max[LCM@@@IntegerPartitions@#]&pour 31 octets , car le @@@fait Applyau niveau 1.

Roman

4

Python , 87 octets

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

Essayez-le en ligne!

Une fonction récursive qui suit le reste nà partitionner et le LCM en cours d'exécution d. Notez que cela signifie que nous n'avons pas besoin de suivre les nombres réels dans la partition ou le nombre d'entre eux que nous avons utilisés. Nous essayons chaque partie suivante possible n-m, en remplaçant npar ce qui reste m, et daveclcm(d,n-m) . Nous prenons le maximum de ces résultats récursifs et dlui - même. Quand rien ne reste n=0, le résultat est juste d.

La chose délicate est que Python n'a pas de fonctionnalités intégrées pour LCM, GCD ou factorisation principale. Pour ce faire lcm(d,m-n), nous générons une liste de multiples de d, et prenons la valeur atteignant le modulo minimum n-m, c'est-à-dire avec key=(n-m).__rmod__. Puisque mindonnera la valeur précédente en cas d'égalité, il s'agit toujours du premier multiple non nul de dcelui qui est divisible par n-m, donc leur LCM. Nous n'avons que des multiples dpouvant d*(n-m)être garantis pour atteindre le LCM, mais il est plus court d'écrire d<<n(ce qui est d*2**n), ce qui suffit, les limites supérieures de Python étant exclusives.

La mathbibliothèque de Python 3 a gcd(mais pas lcm) après 3.5, ce qui est quelques octets plus court. Merci à @Joel d'avoir raccourci l'importation.

Python 3.5+ , 84 octets

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

Essayez-le en ligne!

L'utilisation de numpy's lcmest encore plus courte.

Python avec numpy , 77 octets

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

Essayez-le en ligne!

xnor
la source

L'utilisation from math import*est de 85 octets et l'utilisation de import math+ math.gcd(...)est de 84 octets. La même chose s'applique à numpy.

Joel

@ Joel Merci, j'ai oublié ça.

xnor

@Joel Merci, j'avais oublié de mettre à jour le nombre d'octets, ils sont tous les deux 77. numpyLa longueur de 5 est le point mort pour import*.

xnor

Droite. Dans ce cas, je préfère utiliser import numpycar numpy.maxremplacerait le Python intégré max(idem pour min) s'il from numpy import*est utilisé. Cela ne pose pas de problème ici mais nous savons tous que ce import*n'est pas une bonne pratique de programmation en général.

Joel

@Joel Bien que ce import*soit sans aucun doute une mauvaise pratique, je ne pense pas que cela écrase réellement Python minet max, donc la confusion serait que quelqu'un attende la fonction de numpy et obtienne celle de base.

xnor

4

Haskell , 44 octets

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

Essayez-le en ligne!

xnor
la source

3

Gelée , 7 octets

Œṗæl/€Ṁ

Essayez-le en ligne!

Un lien monadique prenant un entier comme argument et renvoyant un entier.

Explication

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

Nick Kennedy
la source

3

JavaScript (ES6), 92 octets

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

Essayez-le en ligne!

JavaScript (ES6), 95 octets

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)

Essayez-le en ligne!

Comment?

Nous définissons:

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

(c'est A008475 )

Ensuite, nous utilisons la formule (de A000793 ):

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

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

Arnauld
la source

3

Perl 6 , 50 octets

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

Essayez-le en ligne!

Vérifie toutes les permutations directement, comme la solution Ruby de @ histocrat.

Explication

                                     &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

¹ Nous pouvons utiliser n'importe quelle séquence de n éléments distincts pour la vérification, nous prenons donc simplement la permutation elle-même.

² Si le point de terminaison est un conteneur, l' ...opérateur de séquence s'accorde avec le premier élément. Nous devons donc passer une liste à un seul élément.

nwellnhof
la source

2

Rubis , 77 octets

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

Essayez-le en ligne!

(1..) la syntaxe de plage infinie est trop nouvelle pour TIO, donc le lien définit une limite supérieure arbitraire.

Cela utilise la définition directe - énumérer toutes les permutations possibles, puis tester chacune en mutant ajusqu'à ce qu'elle revienne à sa position d'origine (ce qui signifie également que je peux simplement muter le tableau d'origine dans chaque boucle).

histocrate
la source

2

Gaia , 25 23 22 octets

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

Essayez-le en ligne!

L'absence de LCM ou de partitions entières rend cette approche assez longue.

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


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

Giuseppe
la source

2

Haskell, 70 67 octets

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

Essayez-le en ligne!

Edit: -3 octets grâce à @xnor.

nimi
la source

Je pense que cela devrait fonctionner mapM(:[1..n]), car l'élément supplémentaire est inoffensif.

xnor

1

Python 3 + numpy, 115 102 99 octets

-13 octets grâce à @Daniel Shepler

-3 octets supplémentaires 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))

Essayez-le en ligne!

Méthode de la force brute: trouvez toutes les séquences possibles a, b, c, ... où a + b + c + ... = n, puis choisissez celle avec le plus grand lcm.

Hiatsu
la source

Par ailleurs, j'ai une solution Python 3 + numpy exécutant 87 octets.

Daniel Schepler

Je ne sais pas assez sur numpy pour comprendre comment faire, donc je vous suggère de publier votre solution séparément.

Hiatsu

Eh bien, je comptais attendre un moment pour le poster.

Daniel Schepler

Je viens de réaliser que vous avez publié ce défi. Désolé, je ferai de mon mieux.

Hiatsu

1

Si vous changez cpour renvoyer un ensemble et le mémorisez, cela ne fait pas mal du tout (mais il est vrai que cela se dégrade un peu): tio.run/##RY1BCsIwEEX3PUWWM1CLoiuhV/AKEsfUTkkmIU3AWnr2Ggvq7vM@//…

Daniel Schepler

0

Pyth , 24 15 octets

eSm.U/*bZibZd./

Essayez-le en ligne!

             ./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 octets: fait attention et remarqué que Pyth a en fait un GCD builtin ( i).

ar4093
la source