Pseudofaktoryczny

39

Jest dość osobliwa liczba, która pojawia się czasami w problemach matematycznych lub zagadkach. Pseudoczynnik (N) jest najmniejszą (tj. Najniższą) wspólną wielokrotnością liczb od 1 do N; innymi słowy, jest to najniższa liczba, która ma wszystkie liczby od 1 do N jako czynniki.

Na przykład pseudofactorial (7) = 3 * 4 * 5 * 7, czyli tyle samo, co 7! z wyjątkiem tego, że 2 i 6 zostały usunięte, ponieważ są zawarte w innych warunkach.

Napisz program do obliczania pseudofactorial (N) i jak zawsze wygrywa najkrótszy kod.

Oto krótka lista do użytku. Więcej przypadków testowych można znaleźć w OEIS pod A003418 .

Factorial:

  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
Tony Ruth
źródło
6
Nie jestem pewien, czy rozumiem dlaczego 2i 6zostały usunięte z listy wielokrotności. Czy możesz wyjaśnić zasady?
Maltysen
2
@Mattysen, psuedofactorial (N) to najmniejsza liczba, która ma liczby od 1 do N jako czynniki (najmniejszą wspólną wielokrotność tych liczb). To jest definicja techniczna, ale sposób, w jaki ją napisałem, sugerował, że jest podobny do silni.
Tony Ruth,
4
Witamy w Programowaniu Puzzle i Code Golf! To miłe pierwsze wyzwanie!
Alex A.
1
Twoje pierwsze wyzwanie osiągnęło szczyt HNQ. Miły!
Daniel M.

Odpowiedzi:

19

Dyalog APL , 3 bajty

∧/⍳

APL bije Jelly

1 choć argument

∧/ LCM w poprzek

Adám
źródło
10
Ten interrobang jest taki seksowny.
shooqie
1
O człowieku, pokonałeś Dennisa ...
Mama Fun Roll
1
Imponujące, ale jak te 3 bajty ?
przestał się obracać w lewo o
8

C (z x86), 52 bajty

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

Sprawdza liczby od 1 w górę. Dla każdej liczby dzieli ją przez wszystkie liczby od n do 1 i sumuje pozostałe. Zatrzymuje się, gdy suma wynosi 0.

Stosowanie:

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

Nie jest oczywiste, w jaki sposób zwraca wartość (nie ma returninstrukcji).

Konwencja wywoływania dla x86 mówi, że funkcja musi zwrócić swoją wartość w eaxrejestrze. Dogodnie instrukcja dzielenia idivoczekuje, że zostanie wprowadzona eax, i wyświetli wynik w eax(ilorazie) i edx(reszcie). Ostatnia iteracja dzieli księ 1, więc eaxbędzie zawierać prawidłową wartość po wyjściu z funkcji.

Działa to tylko z optymalizacjami na (w trybie debugowania, wyświetla 421).

anatolig
źródło
Jak sobie radzisz z nie deklarowaniem typu n, k, b i t?
Tony Ruth,
C ma regułę default-int - domyślnie wszystkie pominięte typy int(w tym wartość zwracana). Działa dla argumentów funkcji, jeśli są one zadeklarowane przy użyciu tak zwanej składni „starego stylu”. Deklaracja z wyraźnie określonymi typami byłabyint d(n,k,b,t) int n,k,b,t; {...}
anatolyg
jeśli korzystasz z konwencji wywoływania, to powinna ona być naprawdę oznaczona jako „C (cdecl)”, a nie tylko „C”
Steve Cox
@SteveCox Zarówno cdecli stdcallużywają tej samej metody do zwracania wartości, więc myślę, że x86to wystarczy
anatolyg
7

Haskell, 20 bajtów

f x=foldr1 lcm[1..x]

Przykład użycia: map f [1..7]-> [1,2,6,12,60,60,420].

lcmTrik w Haskell.

nimi
źródło
6

Python + SymPy, 45 bajtów

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

Dość oczywiste.


Python 2, 57 54 bajtów

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

Przetestuj na Ideone .

Jak to działa

Dane wejściowe są przechowywane w zmiennych ı i R .

execwykonuje następujący kod r razy.

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

Podczas gdy i zmienia się od r do 1 , dodajemy wartość początkową r (zapisaną w t ) tyle razy, ile jest to konieczne, aby samo r by utworzyć wielokrotność i . Wynikiem jest oczywiście wielokrotność t .

Ostateczna wartość r jest zatem wielokrotnością wszystkich liczb całkowitych z zakresu [1, ..., n] , gdzie n jest wejściem.

Dennis
źródło
1
Bez korzystania z bibliotek i execsztuczek stron trzecich istnieje 78-bajtowe rozwiązanie: from fractions import*;lambda n:reduce(lambda x,y:x*y/gcd(x,y),range(1,n+1),1) Wykorzystuje to lcm(x,y) = x*y/gcd(x,y).
Bakuriu
6

Python, 46 bajtów

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

Szukasz wielokrotności cz g(n-1)bezpośrednio. Myślałem wcześniej, że ta metoda niesłusznie znalazłaby 0 jako wielokrotność czegokolwiek, ale orzwarcie lub też (c%n<1)*cprzeskoczy, c==0ponieważ 0 to Falsey.


50 bajtów:

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

Podobnie jak rozwiązanie Dennisa , ale jako funkcja rekurencyjna. Mając obliczone g(n-1), szuka najmniejszego wielokrotności i*no nto również wielokrotnością g(n-1). Bardzo wolno.

Dzięki Dennis za 4 bajty, patrząc na wielokrotności nzamiast g(n-1).

xnor
źródło
5

J, 9 bajtów

[:*./1+i.

Proste podejście. Tworzy zakres liczb [0, ..., n-1], a następnie dodaje po jednym do każdego z nich i zmniejsza go za pomocą LCM.

Stosowanie

   f =: [:*./1+i.
   f 7
420
mile
źródło
5

MATL , 4 bajty

:&Zm

Wypróbuj online!

Wyjaśnienie

:      % Take input N implicitly. Generate range [1 2 ... N]
&Zm    % LCM of the numbers in that array. Display implicitly
Luis Mendo
źródło
4

Mathematica, 13 bajtów

LCM@@Range@#&
Leaky Nun
źródło
Nie jest to równoznaczne z tylko komponowanie LCMi Rangeze @*?
Maltysen
1
LCMoperuje elementami na liście, która byłaby przekazywana Range, co oznacza, że ​​zwróciłoby to po prostu lcm ( x ) dla x od 1 do n . Brakuje &również anonimowej funkcji. Działa coś w rodzaju LCM@@Range@#&13 bajtów.
mil
3

Pyth - 8 bajtów

Sprawdza wszystkie liczby, aż znajdzie numer, który można podzielić [1..N].

f!s%LTSQ

Pakiet testowy .

Maltysen
źródło
3

Oktawa, 27 bajtów

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

Tworzy anonimową funkcję, którą można wywołać jako ans(N).

Demo online

Wyjaśnienie

To rozwiązanie tworzy listę wszystkich liczb pomiędzy 1i x( 1:x), konwertuje je na tablicę komórkową za pomocą num2cell. Następnie {:}indeksowanie tworzy listę rozdzielaną przecinkami, która jest przekazywana lcmjako wiele argumentów wejściowych w celu obliczenia najmniejszej wspólnej wielokrotności. 1 jest zawsze przekazywany jako pierwszy argument, lcmponieważ lcmzawsze wymaga co najmniej dwóch argumentów wejściowych.

Suever
źródło
1
Tak więc lcmw Octave akceptuje więcej niż 2 wejścia! Ciekawe
Luis Mendo,
@LuisMendo Yup 2+
Suever
3

MATLAB, 49 bajtów

@(x)find(~any(bsxfun(@rem,1:prod(1:x),(1:x)')),1)
Suever
źródło
+1 zabsxfun
flawr
3

Perl 6 , 13 bajtów

{[lcm] 1..$_}

Anonimowy blok kodu, który tworzy zakres od 1 do wejścia (włącznie), a następnie zmniejsza to za pomocą &infix:<lcm>.

Przykład:

#! /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
Brad Gilbert b2gills
źródło
ideone.com/gR4SK5
Brad Gilbert b2gills
2

JavaScript (ES6), 92 88 80 74 69 bajtów:

Dzięki @ConorOBrien i @Neil

y=>(g=(a,b)=>b?g(b,a%b):a,[...Array(y)].map((_,i)=>y=y*++i/g(y,i)),y)
Lotka
źródło
b?g(b,a%b):azapisuje bajt.
Neil,
y*++i/g(y,i)oszczędza trochę więcej bajtów.
Neil,
1

05AB1E, 20 bajtów

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

Wyjaśnienie

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

Wypróbuj online

Emigna
źródło
1

Minkolang 0,15 , 12 bajtów

Mam dwa 12-bajtowe rozwiązania i uwzględniłem je oba.

1n[i1+4$M]N.

Wypróbuj tutaj!

Wyjaśnienie

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.

Mniej więcej tak proste, jak to możliwe.


11nLd[4$M]N.

Wypróbuj tutaj!

Wyjaśnienie

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.

Z tego można wyprowadzić trzecie rozwiązanie: usuń a 1i dodaj dpo bieżącym d. W obu przypadkach potrzebna jest dodatkowa liczba, ponieważ pętla for działa zbyt wiele razy, a sprawienie, by działała o jeden raz krócej, zajmuje dwa bajty ( 1-tuż przed [).

El'endia Starman
źródło
1

Rubin, 25 bajtów

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

Rubin, 25 bajtów

g=->n{n<1?1:a[n-1].lcm n}
Peter Kagey
źródło
1
Witaj i witaj w PPCG! Świetny pierwszy post! Nie musisz nazywać swojej funkcji, więc możesz ją usunąć g=.
NoOneIsHere
Funkcje anonimowe są dozwolone.
Erik the Outgolfer
1

GameMaker Language, 60 bajtów

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

Oparty na logice odpowiedzi anatolyga.

Timtech
źródło
1

PHP, 61 52 48 bajtów

zapisano 9 bajtów dzięki @ user59178, 4 bajty poprzez scalenie pętli.

Rekurencja w PHP jest nieporęczna ze względu na functionsłowo kluczowe; więc używam iteracji.
I kilkoma „sztuczkami” pokonałem teraz nawet JS Arnaulda .

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

pobiera dane wejściowe z argumentu wiersza poleceń. Uruchom z -r.

awaria

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

bez golfa

To właściwie dwie pętle w jednym:

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

Uwaga: skopiowano z mojej odpowiedzi na duplikacie

Tytus
źródło
0

Pyke, 3 bajty, niekonkurujące

S.L

Wypróbuj tutaj!

S   - range(1, input+1)
 .L - lowest_common_multiple(^)
niebieski
źródło
0

Hoon , 67 bajtów

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

Utwórz listę [1..n], złóż listę za pomocą lcm. Niestety, Hoon stdlib nie ma gotowego, którego mogę użyć: /

RenderSettings
źródło
0

AWK, 42 bajty

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

Wykorzystanie wiersza poleceń:

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

Nie widziałem AWKrozwiązania, a duplikat pytania właśnie został opublikowany wczoraj, więc pomyślałem, że zebrałem to razem. Na 19moim komputerze jest to raczej powolne rozwiązywanie lub większe, ale działa.

Robert Benson
źródło
0

QBIC , 35 32 bajtów

To mnie tu sprowadziło.

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

Wyjaśnienie:

:        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]

Oto wersja, która przestaje testować, qgdy bnie dzieli go czysto. Również kolejność testowania b„s Against qodwraca się w założeniu, że wyższe b” s trudniej będzie podzielić przez (take 2, 3, 4na przykład: jeśli %2=0, %4może być !0. Vice versa nie tak dużo ...).

:{p=0[a,2,-1|~q%b|p=1┘b=2]]~p=0|_Xq\q=q+1
Steenbergh
źródło
0

8 , 23 bajty

Kod

1 ' lcm rot 2 swap loop

Ten kod pozostawia wynikowy pseudoczynnik na TOS

Zastosowanie i przykład

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

Lub bardziej wyraźnie

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

ok> 7 pseudofact .
420
Dwór Chaosu
źródło