Рассчитать функцию Ландау

19

Функция Ландау грамм(N) ( OEIS A000793 ) дает максимальный порядок элемента симметрической группы SN . Здесь порядок перестановки π является наименьшим положительным целым числом К таким, что πК является тождеством, равным наименьшему общему кратному длин циклов в разложении циклов перестановки. Например, грамм(14)знак равно84 что достигается, например, с помощью (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14).

Таким образом, грамм(N) также равно максимальное значение LCM(a1,...,aК) , где 1 + + к = п с в 1 , ... , к положительным целым числам.a1++aКзнак равноNa1,...,aК

проблема

Напишите функцию или программу, которая вычисляет функцию Ландау.

вход

Положительное целое число N .

Выход

грамм(N) - максимальный порядок элемента симметрической группыSN .

Примеры

n    g(n)
1    1
2    2
3    3
4    4
5    6
6    6
7    12
8    15
9    20
10   30
11   30
12   60
13   60
14   84
15   105
16   140
17   210
18   210
19   420
20   420

Гол

Это : выигрывает самая короткая программа в байтах. (Тем не менее, самые короткие реализации на нескольких языках приветствуются.)

Обратите внимание, что нет никаких требований, налагаемых на время выполнения; следовательно, ваша реализация не обязательно должна иметь возможность генерировать все приведенные выше примеры результатов в любое разумное время.

Стандартные лазейки запрещены.

Даниэль Шеплер
источник

Ответы:

10

Wolfram Language (Mathematica) , 44 байта

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 31 байт

У @DanielSchepler есть лучшее решение:

Max[LCM@@@IntegerPartitions@#]&

Попробуйте онлайн!

Роман
источник
Не очень знаком с языком - но, Max[Apply@LCM/@IntegerPartitions@#]&кажется, работает для меня и даст 36 байт, если это правильно.
Даниэль Шеплер
2
@DanielSchepler да супер! Почему вы не предлагаете это как отдельное решение? Вы даже можете сделать Max[LCM@@@IntegerPartitions@#]&для 31 байта , потому что @@@делает Applyна уровне 1.
Роман
4

Python , 87 байт

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

Попробуйте онлайн!

Рекурсивная функция, которая отслеживает оставшееся nдо раздела и работающий LCM d. Обратите внимание, что это означает, что нам не нужно отслеживать фактические числа в разделе или сколько из них мы использовали. Мы пробуем каждую возможную следующую часть, n-mзаменяя nна то, что осталось m, и dна lcm(d,n-m). Мы берем максимум этих рекурсивных результатов и dсебя. Когда ничего не остается n=0, результат просто d.

Хитрость в том, что в Python нет встроенных модулей для LCM, GCD или простой факторизации. Для этого lcm(d,m-n)мы генерируем список кратных значений dи принимаем значение, достигающее минимального значения по модулю n-m, то есть с key=(n-m).__rmod__. Так minкак в случае связывания будет дано более раннее значение, это всегда первое ненулевое кратное, dкоторое делится на n-m, поэтому их LCM. Мы только кратны d, чтобы d*(n-m)быть гарантированно попадавшими в LCM, но написать короче d<<n(что есть d*2**n) достаточно, чтобы верхние границы Python были исключительными.

mathБиблиотека Python 3 имеетgcd (но не lcm) после 3.5, что на несколько байт короче. Спасибо @Joel за сокращение импорта.

Python 3.5+ , 84 байта

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

Попробуйте онлайн!

Использование numpys lcmеще короче.

Питон с NumPy , 77 байт

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

Попробуйте онлайн!

XNOR
источник
Значение from math import*составляет 85 байт, а значение import math+ math.gcd(...)- 84 байта. То же самое относится и к numpy.
Джоэл
@Joel Спасибо, я забыл об этом.
XNOR
@Joel Спасибо, я забыл обновить количество байтов, они оба 77. numpyДлина 5 - точка безубыточности для import*.
XNOR
Правильно. В этом случае я предпочитаю использовать, import numpyпотому numpy.maxчто переопределит встроенный Python max(то же самое для min), если from numpy import*используется. Это не вызывает проблем, но мы все знаем, что import*это не очень хорошая практика программирования в целом.
Джоэл
@Joel Хотя import*нет сомнений , плохая практика, я не думаю , что это на самом деле переписывает в Python minи max, таким образом , путаница будет кто - то ожидал функции Numpy и получение базового один.
xnor
3

Желе , 7 байт

Œṗæl/€Ṁ

Попробуйте онлайн!

Монадическая ссылка, принимающая целое число в качестве аргумента и возвращающая целое число.

объяснение

Œṗ      | Integer partitions
  æl/€  | Reduce each using LCM
      Ṁ | Maximum
Ник Кеннеди
источник
3

JavaScript (ES6), 92 байта

LCM(a1,...,aК)a1+...+aК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

Попробуйте онлайн!


JavaScript (ES6), 95 байт

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)

Попробуйте онлайн!

Как?

Мы определяем:

{грамм(1)знак равно0грамм(N)знак равноΣJзнак равно1NпJКJзаN>1иNзнак равноΠJзнак равно1NпJКJ

(это A008475 )

Тогда мы используем формулу (из A000793 ):

е(N)знак равноМаксимумграмм(К)NК

Arnauld
источник
3

Perl 6 , 50 байт

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

Попробуйте онлайн!

Непосредственно проверяет все перестановки, например, решение @ histocrat's Ruby.

объяснение

                                     &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

1 Мы можем использовать любую последовательность из n различных элементов для проверки, поэтому мы просто берем саму перестановку.

2 Если конечная точка является контейнером, ...оператор последовательности сопоставляет первый элемент. Таким образом, мы должны передать одноэлементный список.

nwellnhof
источник
2

Рубин , 77 байт

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

Попробуйте онлайн!

(1..) Синтаксис бесконечного диапазона является слишком новым для TIO, поэтому ссылка устанавливает произвольную верхнюю границу.

При этом используется прямое определение - перечисление всех возможных перестановок, затем проверка каждой путем изменения, aпока она не вернется в исходное положение (что также удобно означает, что я могу просто изменить исходный массив в каждом цикле).

histocrat
источник
2

Gaia , 25 23 22 байта

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

Попробуйте онлайн!

Отсутствие LCM или целочисленных разделов делает этот подход довольно длинным.

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


1w&ḍΣ¦¦			;* push integer partitions
         ¦		;* for each
       ⇈⊢		;* Reduce by helper function
	  ⌉		;* and take the max
Giuseppe
источник
2

Haskell, 70 67 байт

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

Попробуйте онлайн!

Изменить: -3 байта благодаря @xnor.

Ними
источник
Я думаю, что это должно работать mapM(:[1..n]), так как дополнительный элемент безвреден.
xnor
1

Python 3 + numpy, 115 102 99 байт

-13 байт благодаря @Даниэль Шеплер

-3 больше байтов от @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))

Попробуйте онлайн!

Метод грубой силы: найдите все возможные последовательности a, b, c, ..., где a + b + c + ... = n, затем выберите последовательность с наибольшим lcm.

Hiatsu
источник
Между прочим, у меня есть решение на Python 3+, работающее на 87 байтах.
Даниэль Шеплер
Я не знаю достаточно о numpy, чтобы понять, как это сделать, поэтому я предлагаю вам опубликовать свое решение отдельно.
Хиацу
Ну, я планировал немного подождать, чтобы опубликовать это.
Даниэль Шеплер
Я только что понял, что вы отправили этот вызов. Извините, я сделаю все возможное.
Хиацу
1
Если вы измените, cчтобы вернуть набор и запомнить, это совсем не плохо (хотя по общему признанию это немного разглаживает
Даниэль Шеплер
0

Pyth , 24 15 байт

eSm.U/*bZibZd./

Попробуйте онлайн!

             ./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 байт: обратил внимание и заметил, что Pyth на самом деле имеет встроенную функцию GCD ( i).

ar4093
источник