Pseudofactorial

39

Есть довольно любопытное число, которое иногда появляется в математических задачах или загадках. Псевдофакториал (N) является наименьшим (то есть самым низким) общим кратным чисел от 1 до N; другими словами, это наименьшее число, в котором все числа от 1 до N являются факторами.

Например, псевдофакториал (7) = 3 * 4 * 5 * 7, что совпадает с 7! за исключением того, что 2 и 6 были удалены, потому что они содержатся в других терминах.

Напишите программу для расчета псевдофакториала (N) и, как всегда, выигрывает самый короткий код.

Вот краткий список для вашего использования. Больше тестовых примеров можно найти в OEIS под A003418 .

Факториал:

  1. 1
  2. 2
  3. 6
  4. 24
  5. 120
  6. 720
  7. 5040

Pseudofactorial:

  1. 1
  2. 2
  3. 6
  4. 12
  5. 60
  6. 60
  7. 420
Тони Рут
источник
6
Я не уверен, что понимаю, почему 2и 6были удалены из списка магазинов. Можете ли вы уточнить правила?
Maltysen
2
@Mattysen, psuedofactorial (N) - это наименьшее число, которое имеет числа от 1 до N в качестве факторов (наименьшее общее число из этих чисел). Это техническое определение, но то, как я его написал, показало, что оно похоже на факториал.
Тони Рут
2
oeis.org/A003418
Нейл
4
Добро пожаловать в Программирование Пазлов и Code Golf! Это хороший первый вызов!
Алекс А.
1
Ваш первый вызов достиг вершины HNQ. Ницца!
Даниэль М.

Ответы:

19

Дьялог АПЛ , 3 байта

∧/⍳

APL бьет Jelly

1 хотя аргумент

∧/ LCM через

Адам
источник
10
Этот интербанг такой сексуальный.
Shooqie
1
О человек, которого вы победили Деннис ...
Мама Ролл Fun
1
Впечатляет, но как эти 3 байта ?
перестал поворачиваться против часовой стрелки с
2
ru.wikipedia.org/wiki/APL_(codepage)
Утренняя монахиня
8

C (с x86), 52 байта

d(n,k,b,t){for(b=k=1;b;++k)for(t=n,b=0;t;b+=k%t--);}

Проверяет числа от 1 и выше. Для каждого числа делим его на все числа от n до 1 и суммируем остатки. Останавливается, когда сумма равна 0.

Использование:

main()
{
    printf("%d\n", d(7)); // outputs 420
}

Не очевидно, как он возвращает значение (нет returnзаявления).

Соглашение о вызовах для x86 говорит, что функция должна возвращать свое значение в eaxрегистр. Удобно, когда инструкция деления idivожидает ввода eaxи выводит результат в eax(частное) и edx(остаток). Последняя итерация делится kна 1, поэтому eaxбудет содержать правильное значение при выходе из функции.

Это работает только с оптимизацией (в режиме отладки выводит 421).

anatolyg
источник
Как вы обходитесь без объявления типа n, k, b и t?
Тони Рут
C имеет правило default-int - все пропущенные типы intпо умолчанию (включая возвращаемое значение). Он работает для аргументов функции, если они объявлены с использованием так называемого синтаксиса «старого стиля». Объявление с явно определенными типами будет:int d(n,k,b,t) int n,k,b,t; {...}
anatolyg
если вы пользуетесь соглашением о вызовах, то на самом деле это должно быть отмечено «C (cdecl)», а не просто «C»
Стив Кокс
@SteveCox Обе cdeclи stdcallиспользуют один и тот же метод для возвращаемого значения, так что я думаю x86, достаточно
anatolyg
7

Haskell, 20 байтов

f x=foldr1 lcm[1..x]

Пример использования: map f [1..7]-> [1,2,6,12,60,60,420].

lcmТрик в Haskell.

Ними
источник
6

Python + SymPy, 45 байт

import sympy
lambda n:sympy.lcm(range(1,n+1))

Довольно очевидный.


Python 2, 57 54 байта

i=r=input();exec't=r\nwhile r%i:r+=t\ni-=1;'*r;print r

Проверьте это на Ideone .

Как это работает

Входные данные хранятся в переменных i и r .

execвыполняет следующий код r раз.

t=r
while r%i:r+=t
i-=1

Хотя i изменяется от r до 1 , мы добавляем начальное значение r (хранимое в t ) столько раз, сколько необходимо r , чтобы создать кратное i . Результат, очевидно, кратен т .

Таким образом, конечное значение r кратно всем целым числам в диапазоне [1, ..., n] , где n - это входное значение.

Деннис
источник
1
Без использования сторонних библиотек или 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).
Бакуриу
6

Python, 46 байт

g=lambda n,c=0:n<1or(c%n<1)*c or g(n,c+g(n-1))

Ищете несколько cиз g(n-1)непосредственно. Раньше у меня было, однако, что этот метод ошибочно нашел бы 0 как кратное всего, но orкороткое замыкание или (c%n<1)*cпропустит c==0также, потому что 0 - Falsey.


50 байтов:

g=lambda n,i=1:n<1or(i*n%g(n-1)<1)*i*n or g(n,i+1)

Как и решение Денниса , но как рекурсивная функция. Вычислив g(n-1), ищет наименьшего кратного i*nиз nчто также кратно g(n-1). Действительно медленно.

Спасибо Деннису за 4 байта, глядя на кратные nвместо g(n-1).

XNOR
источник
5

J, 9 байт

[:*./1+i.

Прямой подход. Создает диапазон чисел [0, ..., n-1], затем добавляет по одному к каждому и уменьшает его с помощью LCM.

использование

   f =: [:*./1+i.
   f 7
420
миль
источник
4

Mathematica, 13 байт

LCM@@Range@#&
Дрянная Монахиня
источник
Разве это не эквивалентно просто сочинению LCMи Rangeс @*?
Maltysen
1
LCMработает поэлементно в списке, который будет передан Range, то есть это просто вернет lcm ( x ) для x от 1 до n . Кроме того, отсутствует, &что закрыло бы анонимную функцию. Что-то вроде LCM@@Range@#&на 13 байт будет работать.
миль
3

Октава, 27 байт

@(x)lcm(1,num2cell(1:x){:})

Создает анонимную функцию, которая может быть вызвана как ans(N).

Демо онлайн

объяснение

Это решение создает список всех чисел между 1and x( 1:x), преобразует их в массив ячеек с помощью num2cell. Затем {:}индексация создает список с разделителями-запятыми, который передается в lcmкачестве нескольких входных аргументов для вычисления наименьшего общего кратного. 1 всегда передается в качестве первого аргумента, lcmпотому что lcmвсегда требуется как минимум два входных аргумента.

Suever
источник
1
Так что lcmв Octave допускается более 2 входов! Интересно
Луис Мендо
@LuisMendo Yup 2+
Suever
3

MATLAB, 49 байтов

@(x)find(~any(bsxfun(@rem,1:prod(1:x),(1:x)')),1)
Suever
источник
+1 заbsxfun
flawr
3

Perl 6 , 13 байт

{[lcm] 1..$_}

Блок анонимного кода, который создает диапазон от 1 до ввода (включительно), а затем уменьшает его с помощью &infix:<lcm>.

Пример:

#! /usr/bin/env perl6
use v6.c;

my &postfix:<p!> = {[lcm] 1..$_}

say 1p!; # 1
say 2p!; # 2
say 3p!; # 6
say 4p!; # 12
say 5p!; # 60
say 6p!; # 60
say 7p!; # 420

say 10000p!; # 5793339670287642968692270879...
# the result from this is 4349 digits long
Брэд Гилберт b2gills
источник
ideone.com/gR4SK5
Брэд Гилберт b2gills
2

JavaScript (ES6), 92 88 80 74 69 байт:

Спасибо @ConorOBrien и @Neil

y=>(g=(a,b)=>b?g(b,a%b):a,[...Array(y)].map((_,i)=>y=y*++i/g(y,i)),y)
полый вал
источник
b?g(b,a%b):aсохраняет байт.
Нил
y*++i/g(y,i)сохраняет еще несколько байтов.
Нил
1

05AB1E, 20 байтов

Lpvyi¹LÒN>¢àN>*ˆ}}¯P

объяснение

Lpv                    # for each item in isprime(range(1,N)): N=7 -> [0,1,1,0,1,0,1]
   yi                  # if prime
     ¹LÒN>¢            # count occurrences of the prime 
                         in the prime-factorization of range(1,N):
                         p=2 -> [0,1,0,2,0,1,0]
           àN>*ˆ       # add max occurrence of that prime multiplied by the prime 
                         to global array: N=7 -> [4,3,5,7]
                }}     # end if/loop
                  ¯P   # get product of global array

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

Emigna
источник
1

Минколанг 0,15 , 12 байт

У меня есть два 12-байтовых решения, и я включил их оба.

1n[i1+4$M]N.

Попробуй это здесь!

объяснение

1               Push 1
 n              Take number from input
  [             For loop that repeats n times
   i1+          Push loop counter + 1
      4$M       Pop b, a and push lcm(a,b)
         ]      Close for loop
          N.    Output as number and stop.

Примерно так же просто, как и получается.


11nLd[4$M]N.

Попробуй это здесь!

объяснение

11              Push two 1s
  n             Take number from input
   L            Pop b, a and push range from a to b, inclusive
    d           Duplicate top of stack (n)
     [4$M]      Pop b, a and push lcm(a,b), n times
          N.    Output as number and stop.

Третье решение может быть получено из этого: удалить a 1и добавить a dпосле текущего d. В обоих случаях требуется дополнительное число, потому что цикл for выполняется один слишком много раз, а выполнение цикла за один раз занимает два байта ( 1-непосредственно перед [).

Эльендия Старман
источник
1

Рубин, 25 байт

g=->n{(1..n).reduce :lcm}

Рубин, 25 байт

g=->n{n<1?1:a[n-1].lcm n}
Питер Кейджи
источник
1
Здравствуйте и добро пожаловать в PPCG! Отличный первый пост! Вам не нужно называть свою функцию, поэтому вы можете удалить g=.
NoOneIsHere
Анонимные функции разрешены.
Эрик Outgolfer
1

Язык GameMaker, 60 байт

for(b=k=1;b;++k){b=0for(t=argument0;t;b+=k mod t--)}return k

Исходя из логики ответа анатолыга.

Timtech
источник
1

PHP, 61 52 48 байт

благодаря @ user59178, 4 байта сэкономлено 4 байта путем объединения циклов.

Рекурсия в PHP громоздка из-за functionключевого слова; поэтому я использую итерацию.
И с «маленькими» хитростями я теперь даже победил Арнаулда .

while(++$k%++$i?$i>$argv[1]?0:$i=1:$k--);echo$k;

принимает входные данные из аргумента командной строки. Беги с -r.

сломать

while(++$k%++$i?    # loop $i up; if it does not divide $k
    $i>$argv[1]?0       # break if $i (smallest non-divisor of $k) is larger than input
    :$i=1               # while not, reset $i and continue loop with incremented $k
    :$k--);         # undo increment while $i divides $k
echo$k;         # print $k

ungolfed

На самом деле это две петли в одной:

while($i<=$argv[1]) # loop while $i (smallest non-divisor of $k) is not larger than input
    for($k++,       # loop $k up from 1
        $i=0;$k%++$i<1;);   # loop $i up from 1 while it divides $k
echo$k;             # print $k

Примечание: скопировано из моего ответа на дубликате

Titus
источник
0

Хун , 67 байт

|*
*
(roll (gulf 1 +<) |=({a/@ b/_1} (div (mul a b) d:(egcd a b))))

Создайте список [1..n], сверните список с помощью lcm. К сожалению, у Hoon stdlib нет готового, который я могу использовать: /

RenderSettings
источник
0

𝔼𝕊𝕄𝕚𝕟, 7 символов / 9 байтов

Мū…⩤⁽1ï

Try it here (ES6 only).

Просто LCM включающего диапазона от 1 до ввода.

Mama Fun Roll
источник
0

AWK, 42 байта

{for(x=n=1;n<=$1;)if(x%n++){x++;n=1}$0=x}1

Использование командной строки:

awk '{for(x=n=2;n<=$1;)if(x%n++){x++;n=2}$0=x}1' <<< NUM

Я не видел AWKрешения и дубликат вопроса, который только что был опубликован вчера, поэтому я подумал, что все это вместе. Это довольно медленное решение для 19или больше на моей коробке, но это работает.

Роберт Бенсон
источник
0

QBIC , 35 32 байта

Это привело меня сюда.

:{p=0[a|~q%b|p=1]]~p=0|_Xq\q=q+1

Объяснение:

:        Get cmd line param as number 'a'
{        Start an infinite DO loop
p=0      Sets a flag that shows if divisions failed
[a|      FOR (b=1; b<=a; b++)
~q%b     IF 'q' (which starts at 1 in QBIC) is not cleanly divisible by 'b'
|p=1     THEN Set the flag
]]   Close the FOR loop and the IF, leave the DO open
~p=0     IF 'q' didn't get flagged
|_Xq     THEN quit, printing 'q'
\q=q+1   ELSE raise 'q', redo
         [DO Loop implicitly closed by QBIC]

Вот версия, которая прекращает тестирование, qкогда bне разделяет ее. Кроме того , порядок проверки b«против s qвосстанавливается в предположении , что более высокие b» s будет труднее разделить на (взять 2, 3, 4например: если %2=0, %4может быть !0. И наоборот , не так много ...).

:{p=0[a,2,-1|~q%b|p=1┘b=2]]~p=0|_Xq\q=q+1
steenbergh
источник
0

Аксиома, 35 байт

f(x)==reduce(lcm,[i for i in 1..x])

код теста и результаты

(25) -> [[i,f(i)] for i in [1,6,19,22,30]]
   (25)  [[1,1],[6,60],[19,232792560],[22,232792560],[30,2329089562800]]
                                                  Type: List List Integer

я просто делаю решение Найти наименьшее положительное целое число, которое имеет все целые числа от 1 до n как факторы, потому что вы говорите, что это дублирует, я публикую его здесь

RosLuP
источник
0

8 , 23 байта

Код

1 ' lcm rot 2 swap loop

Этот код оставляет полученный псевдофакториал на TOS

Использование и пример

ok> 7 1 ' lcm rot 2 swap loop .
420

Или более четко

ok> : pseudofact 1 ' n:lcm rot 2 swap loop ;

ok> 7 pseudofact .
420
Chaos Manor
источник