Berechnen Sie die Funktion von Landau

19

Die Landausche Funktion ( OEIS A000793 ) gibt die maximale Ordnung eines Elements der symmetrischen Gruppe . Hier ist die Ordnung einer Permutation die kleinste positive ganze Zahl so dass die Identität ist - die gleich dem kleinsten gemeinsamen Vielfachen der Länge der Zyklen in der Zykluszerlegung der Permutation ist. Zum Beispiel ist was zum Beispiel durch (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14) erreicht wird. $g(n)$ $S_n$ $\pi$ $k$ $\pi^k$ $g(14) = 84$

Daher ist auch gleich dem Maximalwert von wobei mit positiven ganzen Zahlen. $g(n)$ $\operatorname{lcm}(a_1, \ldots, a_k)$ $a_1 + \cdots + a_k = n$ $a_1, \ldots, a_k$

Problem

Schreiben Sie eine Funktion oder ein Programm, das die Funktion von Landau berechnet.

Eingang

Eine positive ganze Zahl . $n$

Ausgabe

$g(n)$ die maximale Ordnung eines Elements der symmetrischen Gruppe . $S_n$

Beispiele

Ergebnis

Das ist Code-Golf : Das kürzeste Programm in Bytes gewinnt. (Trotzdem sind kürzeste Implementierungen in mehreren Sprachen erwünscht.)

Beachten Sie, dass keine Anforderungen an die Laufzeit gestellt werden. Daher muss Ihre Implementierung nicht unbedingt in der Lage sein, alle oben genannten Beispielergebnisse in einer angemessenen Zeit zu generieren.

Standardlücken sind verboten.

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

Antworten:

9

05AB1E , 6 Bytes

Åœ€.¿Z

Probieren Sie es online!

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

Grimmig
quelle

10

Wolfram Language (Mathematica) , 44 Byte

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

Probieren Sie es online!

Wolfram Language (Mathematica) , 31 Byte

@DanielSchepler hat eine bessere Lösung:

Max[LCM@@@IntegerPartitions@#]&

Probieren Sie es online!

römisch
quelle

Nicht so gut mit der Sprache vertraut - Max[Apply@LCM/@IntegerPartitions@#]&scheint aber für mich zu funktionieren und würde 36 Bytes geben, wenn es korrekt ist.

Daniel Schepler

2

@ DanielSchepler ja, super! Warum schlagen Sie es nicht als separate Lösung vor? Sie können dies sogar Max[LCM@@@IntegerPartitions@#]&für 31 Bytes tun , da @@@dies Applybei Stufe 1 der Fall ist.

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

Probieren Sie es online!

Eine rekursive Funktion, die die verbleibende nPartition und den laufenden LCM verfolgt d. Beachten Sie, dass dies bedeutet, dass wir nicht die tatsächlichen Zahlen in der Partition verfolgen müssen oder wie viele von ihnen wir verwendet haben. Wir probieren jeden möglichen nächsten Teil aus und n-mersetzen ihn ndurch den Rest mund ddurch lcm(d,n-m). Wir nehmen das Maximum dieser rekursiven Ergebnisse und dsich. Wenn nichts bleibt n=0, ist das Ergebnis gerecht d.

Das Schwierige ist, dass Python keine eingebauten Funktionen für LCM, GCD oder Primfaktor-Faktorisierung hat. Dazu erstellen lcm(d,m-n)wir eine Liste mit Vielfachen von dund nehmen den Wert, der das Minimum-Modulo n-merreicht, mit dem key=(n-m).__rmod__. Da minim Falle eines Gleichstands der frühere Wert angegeben wird, ist dies immer das erste Nicht-Null-Vielfache d, das durch teilbar ist n-m, also deren LCM. Wir haben nur ein Vielfaches von ddem d*(n-m), was garantiert ist, um das LCM zu treffen, aber es ist kürzer zu schreiben d<<n( d*2**nwas genügt) , wenn Pythons obere Schranken exklusiv sind.

Die mathBibliothek von Python 3 hat gcd(aber nicht lcm) nach 3.5, was einige Bytes kürzer ist. Vielen Dank an @Joel für die Verkürzung des Imports.

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

Probieren Sie es online!

Mit numpy‚s lcmist noch kürzer.

Python mit Zahl , 77 Bytes

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

Probieren Sie es online!

xnor
quelle

Using from math import*ist 85 Bytes und using import math+ math.gcd(...)ist 84 Bytes. Gleiches gilt für numpy.

Joel

@ Joel Danke, das habe ich vergessen.

31.

@ Joel Danke, ich hatte vergessen, die Byteanzahl zu aktualisieren, sie sind beide 77. numpyDie Länge von 5 ist der Break-Even-Punkt für import*.

31.

Recht. In diesem Fall bevorzuge ich die Verwendung, import numpyda numpy.maxsie Pythons eingebautes max(dasselbe für min) außer Kraft setzt, wenn from numpy import*es verwendet wird. Es verursacht hier keine Probleme, aber wir alle wissen, dass dies import*im Allgemeinen keine gute Programmierpraxis ist.

Joel

@Joel Es import*ist zwar zweifellos eine schlechte Übung, aber ich glaube nicht, dass sie Pythons minund überschreibt. Die maxVerwirrung ist also, dass jemand die Funktion von NumPy erwartet und die Basis erhält.

31.

4

Haskell , 44 Bytes

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

Probieren Sie es online!

xnor
quelle

3

Gelee , 7 Bytes

Œṗæl/€Ṁ

Probieren Sie es online!

Ein monadischer Link, dessen Argument eine Ganzzahl ist und der eine Ganzzahl zurückgibt.

Erläuterung

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

Nick Kennedy
quelle

3

JavaScript (ES6), 92 Byte

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

Probieren Sie es online!

JavaScript (ES6), 95 Byte

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)

Probieren Sie es online!

Wie?

Wir definieren:

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

(das ist A008475 )

Dann verwenden wir die Formel (ab A000793 ):

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

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

Arnauld
quelle

3

Perl 6 , 50 Bytes

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

Probieren Sie es online!

Überprüft alle Permutationen direkt, z. B. die Ruby-Lösung von @ histocrat.

Erläuterung

                                     &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

¹ Wir können eine beliebige Folge von n verschiedenen Elementen für die Prüfung verwenden, also nehmen wir einfach die Permutation selbst.

² Wenn der Endpunkt ein Container ist, ...stimmt der Sequenzoperator mit dem ersten Element überein. Wir müssen also eine Einzelelementliste übergeben.

nwellnhof
quelle

2

Ruby , 77 Bytes

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

Probieren Sie es online!

(1..) Die unendliche Bereichssyntax ist für TIO zu neu, daher legt der Link eine willkürliche Obergrenze fest.

Hierfür wird die direkte Definition verwendet - alle möglichen Permutationen auflisten und jede durch Mutation testen, abis sie wieder an ihrer ursprünglichen Position ist (was auch bequem bedeutet, dass ich das ursprüngliche Array in jeder Schleife einfach mutieren kann).

Histokrat
quelle

2

Gaia , 25 23 22 Bytes

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

Probieren Sie es online!

Ohne LCM- oder Integer-Partitionen ist dieser Ansatz ziemlich lang.

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


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

Giuseppe
quelle

2

Haskell, 70 67 Bytes

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

Probieren Sie es online!

Edit: -3 Bytes dank @xnor.

nimi
quelle

Ich denke, es sollte funktionieren mapM(:[1..n]), da das zusätzliche Element harmlos ist.

31.

1

Python 3 + Anzahl, 115 102 99 Bytes

-13 Bytes dank @Daniel Shepler

-3 weitere Bytes von @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))

Probieren Sie es online!

Brute-Force-Methode: Finde alle möglichen Sequenzen a, b, c, ... mit a + b + c + ... = n und wähle dann die mit den höchsten lcm.

Hiatsu
quelle

Ich habe übrigens eine Python 3 + Numpy-Lösung mit 87 Bytes.

Daniel Schepler

Ich weiß nicht genug über Numpy, um herauszufinden, wie man das macht, also schlage ich vor, dass Sie Ihre Lösung einfach separat posten.

Hiatsu

Nun, ich wollte eine Weile warten, um es zu posten.

Daniel Schepler

Ich habe gerade festgestellt, dass Sie diese Herausforderung gepostet haben. Entschuldigung, ich werde mein Bestes geben.

Hiatsu

1

Wenn Sie ändern ceinen Satz zurück und memoize es nicht schlecht überhaupt nicht tun (obwohl zugegebenermaßen tut es ungolf ein bisschen): tio.run/##RY1BCsIwEEX3PUWWM1CLoiuhV/AKEsfUTkkmIU3AWnr2Ggvq7vM@//...

Daniel Schepler

0

Pyth , 24 15 Bytes

eSm.U/*bZibZd./

Probieren Sie es 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: beachtet und bemerkt, dass Pyth tatsächlich eine eingebaute GCD hat ( i).

ar4093
quelle