Функция Ландау ( OEIS A000793 ) дает максимальный порядок элемента симметрической группы . Здесь порядок перестановки является наименьшим положительным целым числом таким, что является тождеством, равным наименьшему общему кратному длин циклов в разложении циклов перестановки. Например, что достигается, например, с помощью (1,2,3) (4,5,6,7) (8,9,10,11,12,13,14).
Таким образом, также равно максимальное значение , где 1 + ⋯ + к = п с в 1 , ... , к положительным целым числам.
проблема
Напишите функцию или программу, которая вычисляет функцию Ландау.
вход
Положительное целое число .
Выход
- максимальный порядок элемента симметрической группы .
Примеры
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
Гол
Это код-гольф : выигрывает самая короткая программа в байтах. (Тем не менее, самые короткие реализации на нескольких языках приветствуются.)
Обратите внимание, что нет никаких требований, налагаемых на время выполнения; следовательно, ваша реализация не обязательно должна иметь возможность генерировать все приведенные выше примеры результатов в любое разумное время.
Стандартные лазейки запрещены.
источник
Max[Apply@LCM/@IntegerPartitions@#]&
кажется, работает для меня и даст 36 байт, если это правильно.Max[LCM@@@IntegerPartitions@#]&
для 31 байта , потому что@@@
делаетApply
на уровне 1.Python , 87 байт
Попробуйте онлайн!
Рекурсивная функция, которая отслеживает оставшееся
n
до раздела и работающий LCMd
. Обратите внимание, что это означает, что нам не нужно отслеживать фактические числа в разделе или сколько из них мы использовали. Мы пробуем каждую возможную следующую часть,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 байта
Попробуйте онлайн!
Использование
numpy
slcm
еще короче.Питон с NumPy , 77 байт
Попробуйте онлайн!
источник
from math import*
составляет 85 байт, а значениеimport math
+math.gcd(...)
- 84 байта. То же самое относится и кnumpy
.numpy
Длина 5 - точка безубыточности дляimport*
.import numpy
потомуnumpy.max
что переопределит встроенный Pythonmax
(то же самое дляmin
), еслиfrom numpy import*
используется. Это не вызывает проблем, но мы все знаем, чтоimport*
это не очень хорошая практика программирования в целом.import*
нет сомнений , плохая практика, я не думаю , что это на самом деле переписывает в Pythonmin
иmax
, таким образом , путаница будет кто - то ожидал функции Numpy и получение базового один.Haskell , 44 байта
Попробуйте онлайн!
источник
Желе , 7 байт
Попробуйте онлайн!
Монадическая ссылка, принимающая целое число в качестве аргумента и возвращающая целое число.
объяснение
источник
JavaScript (ES6), 92 байта
Попробуйте онлайн!
JavaScript (ES6), 95 байт
Попробуйте онлайн!
Как?
Мы определяем:
(это A008475 )
Тогда мы используем формулу (из A000793 ):
источник
Perl 6 , 50 байт
Попробуйте онлайн!
Непосредственно проверяет все перестановки, например, решение @ histocrat's Ruby.
объяснение
1 Мы можем использовать любую последовательность из n различных элементов для проверки, поэтому мы просто берем саму перестановку.
2 Если конечная точка является контейнером,
...
оператор последовательности сопоставляет первый элемент. Таким образом, мы должны передать одноэлементный список.источник
Рубин , 77 байт
Попробуйте онлайн!
(1..)
Синтаксис бесконечного диапазона является слишком новым для TIO, поэтому ссылка устанавливает произвольную верхнюю границу.При этом используется прямое определение - перечисление всех возможных перестановок, затем проверка каждой путем изменения,
a
пока она не вернется в исходное положение (что также удобно означает, что я могу просто изменить исходный массив в каждом цикле).источник
Gaia ,
252322 байтаПопробуйте онлайн!
Отсутствие LCM или целочисленных разделов делает этот подход довольно длинным.
источник
Haskell,
7067 байтПопробуйте онлайн!
Изменить: -3 байта благодаря @xnor.
источник
mapM(:[1..n])
, так как дополнительный элемент безвреден.Python 3 + numpy,
11510299 байт-13 байт благодаря @Даниэль Шеплер
-3 больше байтов от @Daniel Shepler
Попробуйте онлайн!
Метод грубой силы: найдите все возможные последовательности a, b, c, ..., где a + b + c + ... = n, затем выберите последовательность с наибольшим lcm.
источник
c
чтобы вернуть набор и запомнить, это совсем не плохо (хотя по общему признанию это немного разглаживаетPyth ,
2415 байтПопробуйте онлайн!
-9 байт: обратил внимание и заметил, что Pyth на самом деле имеет встроенную функцию GCD (
i
).источник