Есть довольно любопытное число, которое иногда появляется в математических задачах или загадках. Псевдофакториал (N) является наименьшим (то есть самым низким) общим кратным чисел от 1 до N; другими словами, это наименьшее число, в котором все числа от 1 до N являются факторами.
Например, псевдофакториал (7) = 3 * 4 * 5 * 7, что совпадает с 7! за исключением того, что 2 и 6 были удалены, потому что они содержатся в других терминах.
Напишите программу для расчета псевдофакториала (N) и, как всегда, выигрывает самый короткий код.
Вот краткий список для вашего использования. Больше тестовых примеров можно найти в OEIS под A003418 .
Факториал:
- 1
- 2
- 6
- 24
- 120
- 720
- 5040
Pseudofactorial:
- 1
- 2
- 6
- 12
- 60
- 60
- 420
code-golf
math
number-theory
factorial
Тони Рут
источник
источник
2
и6
были удалены из списка магазинов. Можете ли вы уточнить правила?Ответы:
Дьялог АПЛ , 3 байта
APL бьет Jelly ‽
⍳
1 хотя аргумент∧/
LCM черезисточник
Желе , 4 байта
Попробуйте онлайн! или проверьте все контрольные примеры .
Как это работает
источник
C (с x86), 52 байта
Проверяет числа от 1 и выше. Для каждого числа делим его на все числа от n до 1 и суммируем остатки. Останавливается, когда сумма равна 0.
Использование:
Не очевидно, как он возвращает значение (нет
return
заявления).Соглашение о вызовах для x86 говорит, что функция должна возвращать свое значение в
eax
регистр. Удобно, когда инструкция деленияidiv
ожидает вводаeax
и выводит результат вeax
(частное) иedx
(остаток). Последняя итерация делитсяk
на1
, поэтомуeax
будет содержать правильное значение при выходе из функции.Это работает только с оптимизацией (в режиме отладки выводит
421
).источник
int
по умолчанию (включая возвращаемое значение). Он работает для аргументов функции, если они объявлены с использованием так называемого синтаксиса «старого стиля». Объявление с явно определенными типами будет:int d(n,k,b,t) int n,k,b,t; {...}
cdecl
иstdcall
используют один и тот же метод для возвращаемого значения, так что я думаюx86
, достаточноHaskell, 20 байтов
Пример использования:
map f [1..7]
->[1,2,6,12,60,60,420]
.lcm
Трик в Haskell.источник
Python + SymPy, 45 байт
Довольно очевидный.
Python 2,
5754 байтаПроверьте это на Ideone .
Как это работает
Входные данные хранятся в переменных i и r .
exec
выполняет следующий код r раз.Хотя i изменяется от r до 1 , мы добавляем начальное значение r (хранимое в t ) столько раз, сколько необходимо r , чтобы создать кратное i . Результат, очевидно, кратен т .
Таким образом, конечное значение r кратно всем целым числам в диапазоне [1, ..., n] , где n - это входное значение.
источник
exec
трюков есть 78-байтовое решение:from fractions import*;lambda n:reduce(lambda x,y:x*y/gcd(x,y),range(1,n+1),1)
используется тот факт, чтоlcm(x,y) = x*y/gcd(x,y)
.Python, 46 байт
Ищете несколько
c
изg(n-1)
непосредственно. Раньше у меня было, однако, что этот метод ошибочно нашел бы 0 как кратное всего, ноor
короткое замыкание или(c%n<1)*c
пропуститc==0
также, потому что 0 - Falsey.50 байтов:
Как и решение Денниса , но как рекурсивная функция. Вычислив
g(n-1)
, ищет наименьшего кратногоi*n
изn
что также кратноg(n-1)
. Действительно медленно.Спасибо Деннису за 4 байта, глядя на кратные
n
вместоg(n-1)
.источник
J, 9 байт
Прямой подход. Создает диапазон чисел
[0, ..., n-1]
, затем добавляет по одному к каждому и уменьшает его с помощью LCM.использование
источник
MATL , 4 байта
Попробуйте онлайн!
объяснение
источник
Mathematica, 13 байт
источник
LCM
иRange
с@*
?LCM
работает поэлементно в списке, который будет переданRange
, то есть это просто вернет lcm ( x ) для x от 1 до n . Кроме того, отсутствует,&
что закрыло бы анонимную функцию. Что-то вродеLCM@@Range@#&
на 13 байт будет работать.Юлия, 11 байт
Попробуйте онлайн!
источник
Pyth - 8 байт
Проверяет все числа, пока не найдет тот, который делится на
[1..N]
.Тестовый пакет .
источник
Октава, 27 байт
Создает анонимную функцию, которая может быть вызвана как
ans(N)
.Демо онлайн
объяснение
Это решение создает список всех чисел между
1
andx
(1:x
), преобразует их в массив ячеек с помощьюnum2cell
. Затем{:}
индексация создает список с разделителями-запятыми, который передается вlcm
качестве нескольких входных аргументов для вычисления наименьшего общего кратного. 1 всегда передается в качестве первого аргумента,lcm
потому чтоlcm
всегда требуется как минимум два входных аргумента.источник
lcm
в Octave допускается более 2 входов! ИнтересноMATLAB, 49 байтов
источник
bsxfun
Perl 6 , 13 байт
Блок анонимного кода, который создает диапазон от 1 до ввода (включительно), а затем уменьшает его с помощью
&infix:<lcm>
.Пример:
источник
JavaScript (ES6),
9288807469 байт:Спасибо @ConorOBrien и @Neil
источник
b?g(b,a%b):a
сохраняет байт.y*++i/g(y,i)
сохраняет еще несколько байтов.05AB1E, 20 байтов
объяснение
Попробуйте онлайн
источник
Минколанг 0,15 , 12 байт
У меня есть два 12-байтовых решения, и я включил их оба.
Попробуй это здесь!
объяснение
Примерно так же просто, как и получается.
Попробуй это здесь!
объяснение
Третье решение может быть получено из этого: удалить a
1
и добавить ad
после текущегоd
. В обоих случаях требуется дополнительное число, потому что цикл for выполняется один слишком много раз, а выполнение цикла за один раз занимает два байта (1-
непосредственно перед[
).источник
Рубин, 25 байт
Рубин, 25 байт
источник
g=
.Язык GameMaker, 60 байт
Исходя из логики ответа анатолыга.
источник
PHP,
615248 байтблагодаря @ user59178, 4 байта сэкономлено 4 байта путем объединения циклов.
Рекурсия в PHP громоздка из-за
function
ключевого слова; поэтому я использую итерацию.И с «маленькими» хитростями я теперь даже победил Арнаулда .
принимает входные данные из аргумента командной строки. Беги с
-r
.сломать
ungolfed
На самом деле это две петли в одной:
Примечание: скопировано из моего ответа на дубликате
источник
Japt, 10 байт
Нет LCM встроенный.
Попытайся
источник
Пайк, 3 байта, неконкурентный
Попробуй это здесь!
источник
Хун , 67 байт
Создайте список
[1..n]
, сверните список с помощью lcm. К сожалению, у Hoon stdlib нет готового, который я могу использовать: /источник
𝔼𝕊𝕄𝕚𝕟, 7 символов / 9 байтов
Try it here (ES6 only).
Просто LCM включающего диапазона от 1 до ввода.
источник
AWK, 42 байта
Использование командной строки:
Я не видел
AWK
решения и дубликат вопроса, который только что был опубликован вчера, поэтому я подумал, что все это вместе. Это довольно медленное решение для19
или больше на моей коробке, но это работает.источник
QBIC ,
3532 байтаЭто привело меня сюда.
Объяснение:
Вот версия, которая прекращает тестирование,
q
когдаb
не разделяет ее. Кроме того , порядок проверкиb
«против sq
восстанавливается в предположении , что более высокиеb
» s будет труднее разделить на (взять2
,3
,4
например: если%2=0
,%4
может быть!0
. И наоборот , не так много ...).источник
Аксиома, 35 байт
код теста и результаты
я просто делаю решение Найти наименьшее положительное целое число, которое имеет все целые числа от 1 до n как факторы, потому что вы говорите, что это дублирует, я публикую его здесь
источник
Пари / ГП , 14 байтов
Попробуйте онлайн!
источник
8 , 23 байта
Код
Этот код оставляет полученный псевдофакториал на TOS
Использование и пример
Или более четко
источник