Hitung fungsi Landau

19

Fungsi Landau $g(n)$ ( OEIS A000793 ) memberikan urutan maksimum elemen grup simetris $S_n$ . Di sini, urutan permutasi $\pi$ adalah bilangan bulat positif terkecil $k$ sehingga $\pi^k$ adalah identitas - yang sama dengan kelipatan paling umum dari panjang siklus dalam dekomposisi siklus permutasi. Misalnya, $g(14) = 84$ yang dicapai misalnya dengan (1,2,3) (4,5,6,7) (8,9,10,11,12,12,13,14).

Oleh karena itu, $g(n)$ juga sama dengan nilai maksimum $\operatorname{lcm}(a_1, \ldots, a_k)$ di mana $a_1 + \cdots + a_k = n$ dengan $a_1, \ldots, a_k$ bilangan bulat positif.

Masalah

Tulis fungsi atau program yang menghitung fungsi Landau.

Memasukkan

Bilangan bulat positif $n$ .

Keluaran

$g(n)$ , urutan maksimum unsur dari kelompok simetris $S_n$ .

Contohnya

Skor

Ini adalah kode-golf : Program terpendek dalam byte menang. (Namun demikian, implementasi terpendek dalam berbagai bahasa dipersilahkan.)

Perhatikan bahwa tidak ada persyaratan yang dikenakan saat run-time; oleh karena itu, implementasi Anda tidak harus dapat menghasilkan semua hasil contoh di atas dalam waktu yang wajar.

Celah standar dilarang.

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

Jawaban:

9

05AB1E , 6 byte

Åœ€.¿Z

Cobalah online!

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

Grimmy
sumber

10

Bahasa Wolfram (Mathematica) , 44 byte

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

Cobalah online!

Bahasa Wolfram (Mathematica) , 31 byte

@DanielSchepler memiliki solusi yang lebih baik:

Max[LCM@@@IntegerPartitions@#]&

Cobalah online!

Roma
sumber

Tidak begitu akrab dengan bahasa - tetapi Max[Apply@LCM/@IntegerPartitions@#]&tampaknya bekerja untuk saya dan akan memberikan 36 byte jika itu benar.

Daniel Schepler

2

@DanielSchepler ya, super! Mengapa Anda tidak mengusulkannya sebagai solusi terpisah? Anda bahkan dapat melakukannya Max[LCM@@@IntegerPartitions@#]&selama 31 byte , karena @@@tidak Applypada level 1.

Roman

4

Python , 87 byte

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

Cobalah online!

Fungsi rekursif yang melacak sisanya nke partisi dan menjalankan LCM d. Perhatikan bahwa ini berarti kita tidak perlu melacak angka aktual di partisi atau berapa banyak dari mereka yang telah kita gunakan. Kami mencoba setiap bagian berikutnya yang mungkin n-m, mengganti ndengan yang tersisa m, dan ddenganlcm(d,n-m) . Kami mengambil hasil rekursif maksimum ditu sendiri dan itu sendiri. Ketika tidak ada yang tersisa n=0, hasilnya akan adild .

Yang sulit adalah bahwa Python tidak memiliki built-in untuk LCM, GCD, atau faktorisasi utama. Untuk melakukannya lcm(d,m-n), kami membuat daftar kelipatan d, dan mengambil nilai mencapai modulo minimum n-m, yaitu dengan key=(n-m).__rmod__. Karena minakan memberikan nilai sebelumnya dalam kasus dasi, ini selalu merupakan kelipatan nol pertama dyang habis dibagi n-m, jadi LCM mereka. Kami hanya beberapa dhingga d*(n-m)dijamin untuk mencapai LCM, tetapi lebih singkat untuk menulis d<<n(yang d*2**n) yang cukup dengan batas atas Python menjadi eksklusif.

mathPustaka Python 3 memiliki gcd(tetapi tidak lcm) setelah 3.5, yang lebih pendek beberapa byte. Terima kasih kepada @ Joel untuk mempersingkat impor.

Python 3.5+ , 84 byte

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

Cobalah online!

Menggunakan numpy's lcmbelum lebih pendek.

Python dengan numpy , 77 byte

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

Cobalah online!

Tidak
sumber

Menggunakan from math import*adalah 85 byte dan menggunakan import math+ math.gcd(...)adalah 84 byte. Hal yang sama berlaku untuk numpy.

Joel

@ Joel Terima kasih, saya lupa tentang itu.

xnor

@ Joel Terima kasih, saya lupa memperbarui jumlah byte, keduanya 77. numpyPanjang 5 adalah titik impas untuk import*.

xnor

Baik. Dalam hal ini saya lebih suka menggunakan import numpykarena numpy.maxakan menimpa built-in Python max(sama untuk min) jika from numpy import*digunakan. Ini tidak menyebabkan masalah di sini, tetapi kita semua tahu bahwa import*itu bukan praktik pemrograman yang baik secara umum.

Joel

@ Joel Meskipun import*tidak diragukan lagi praktik buruk, saya tidak berpikir itu benar-benar menimpa Python mindan max, jadi kebingungannya adalah seseorang yang mengharapkan fungsi numpy dan mendapatkan yang basis.

xnor

4

Haskell , 44 byte

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

Cobalah online!

Tidak
sumber

3

Jelly , 7 byte

Œṗæl/€Ṁ

Cobalah online!

Tautan monadik yang menggunakan integer sebagai argumennya dan mengembalikan integer.

Penjelasan

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

Nick Kennedy
sumber

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

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

Cobalah online!

Bagaimana?

Kami mendefinisikan:

{\begin{cases} g (1) = 0 \\ g (n) = \sum_{j = 1}^{N} {hal}_{j}^{k_{j}} untuk n > 1 dan n = \prod_{j = 1}^{N} {hal}_{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} }$

(ini A008475 )

Lalu kami menggunakan rumus (dari A000793 ):

f (n) = \underset{g (k) \leq n}{maks} k

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

Arnauld
sumber

3

Perl 6 , 50 byte

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

Cobalah online!

Memeriksa semua permutasi secara langsung, seperti solusi Ruby @ histocrat.

Penjelasan

                                     &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

¹ Kita dapat menggunakan urutan n item yang berbeda untuk pemeriksaan, jadi kita cukup mengambil permutasi itu sendiri.

² Jika titik akhir adalah sebuah wadah, ...operator urutan smartmatches terhadap item pertama. Jadi kita harus melewati daftar elemen tunggal.

nwellnhof
sumber

2

Ruby , 77 byte

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

Cobalah online!

(1..) sintaks rentang tak terbatas terlalu baru untuk TIO, sehingga tautan menetapkan batas atas yang sewenang-wenang.

Ini menggunakan definisi langsung - menghitung semua permutasi yang mungkin, kemudian menguji masing-masing dengan bermutasi asampai kembali ke posisi semula (yang juga berarti saya bisa bermutasi array asli di setiap loop).

histokrat
sumber

2

Gaia , 25 23 22 byte

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

Cobalah online!

Tidak memiliki LCM atau partisi integer membuat pendekatan ini agak panjang.

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


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

Giuseppe
sumber

2

Haskell, 70 67 byte

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

Cobalah online!

Edit: -3 byte terima kasih kepada @xnor.

nimi
sumber

Saya pikir itu harus dilakukan mapM(:[1..n]), karena elemen tambahan tidak berbahaya.

xnor

1

Python 3 + numpy, 115 102 99 byte

-13 byte berkat @Daniel Shepler

-3 byte lagi dari @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))

Cobalah online!

Metode brute force: temukan semua kemungkinan urutan a, b, c, ... di mana a + b + c + ... = n, lalu pilih satu dengan lcm tertinggi.

Hiatsu
sumber

Kebetulan, saya punya solusi Python 3 + numpy menjalankan 87 byte.

Daniel Schepler

Saya tidak cukup tahu tentang numpy untuk mengetahui cara melakukannya, jadi saya sarankan Anda hanya memposting solusi Anda secara terpisah.

Hiatsu

Yah, aku berencana menunggu sebentar untuk mempostingnya.

Daniel Schepler

Saya baru sadar Anda memposting tantangan ini. Maaf, saya akan melakukan yang terbaik.

Hiatsu

1

Jika Anda mengubah cuntuk mengembalikan satu set dan memo, itu tidak buruk sama sekali (meskipun diakui itu sedikit ungolf

Daniel Schepler

0

Pyth , 24 15 byte

eSm.U/*bZibZd./

Cobalah 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 byte: perhatikan dan perhatikan bahwa Pyth sebenarnya memiliki GCD builtin ( i).

ar4093
sumber