Czy ta liczba jest silna?

38

Zadanie

Biorąc pod uwagę liczbę naturalną jako dane wejściowe, Twoim zadaniem jest wyprowadzenie wartości prawdziwej lub falsey na podstawie tego, czy dane wejściowe są silnikiem dowolnej liczby naturalnej. Możesz założyć, że liczba wejściowa zawsze będzie się mieścić w zakresie liczb obsługiwanych przez Twój język, ale nie wolno nadużywać rodzimych typów liczb w celu trywializacji problemu .

Obowiązują standardowe luki .


Wkład

Otrzymasz liczbę naturalną (typu Integerlub podobną).

Możesz przyjmować dane wejściowe w dowolny sposób, z wyjątkiem zakładania, że ​​będą to predefiniowane zmienne. Odczytywanie z pliku, konsoli, okna dialogowego ( prompt), pola wprowadzania itp. Jest dozwolone. Dozwolony jest również argument wejściowy jako funkcja!


Wydajność

Twój program powinien wypisywać prawdziwą lub falsey wartość na podstawie tego, czy liczba wejściowa jest silnią dowolnej liczby naturalnej.

Upewnij się, że twoje wartości true / falsey są spójne dla wszystkich danych wejściowych, tj. Jeśli używasz pary 1 i 0 do oznaczenia odpowiednio wartości true i falsey, wówczas twój program musi wyprowadzić 1 dla wszystkich danych wejściowych, które powinny mieć wartości true i 0 dla wszystkie dane wejściowe, które powinny mieć wartości falsey.

Możesz pobierać dane wyjściowe w dowolny sposób, z wyjątkiem zapisywania ich w zmiennej. Zapis do pliku, konsoli, ekranu itp. Jest dozwolony. Funkcja returnjest również dozwolona!

Twój program nie może generować błędów dla żadnych danych wejściowych!


Przypadki testowe

Input     Output

1         Truthy (0! or 1!)
2         Truthy (2!)
3         Falsey
4         Falsey
5         Falsey
6         Truthy (3!)
7         Falsey
8         Falsey
24        Truthy (4!)
120       Truthy (5!)

Zwycięskie kryterium

To jest , więc wygrywa najkrótszy kod w bajtach!

Arjun
źródło
2
Jeśli język obsługuje tylko liczby z zakresu {0,1}, czy mogę oczekiwać, że dane wejściowe będą zawsze 1?
eush77
11
@ eush77 Nadużywanie rodzimych typów numerów w celu trywializacji problemu jest domyślnie zabronione.
Dennis,
1
ma 4 lata! prawda?
tuskiomi
Pytanie: Dlaczego nie używasz wartości domyślnych we / wy?
CalculatorFeline

Odpowiedzi:

37

Brachylog , 1 bajt

Wypróbuj online!

Wyjaśnienie

jest wbudowanym, który zapewnia następującą zależność: jego wynik jest silnią jego danych wejściowych. Po prostu dajemy mu ustaloną moc wyjściową i sprawdzamy, czy suces, czy nie, przy zmiennym wejściu.

Fatalizować
źródło
6
@BetaDecay To dlatego, że jest to sposób, w jaki jest drukowany w Prologu (ma to związek z faktem, że true.jest to stwierdzenie, a truenie jest)
Fatalize
6
To trywialne rozwiązanie, ale sprytne ze względu na sposób działania prologu.
Esolanging Fruit
5
@Nayuki Ten, który jest niestandardowy
Fatalize
17
Najpierw niestandardowe języki, potem niestandardowe kodowania ... kod golf nie żyje. W pierwszej kolejności całkowicie obaliliśmy sedno tych zabawnych problemów
Alexander
13
@Alexander Niestandardowe kodowanie nie ma znaczenia dla żadnego problemu, o którym mówisz. Mógłbym zamiast tego użyć dowolnego „istniejącego” kodowania i nadal byłby to 1 bajt. Byłoby to po prostu znacznie mniej czytelne.
Fatalize
19

Galaretka , 3 bajty

!€ċ

Wypróbuj online!

1 za tak, 0 za nie.

Jak to działa

!€ċ  argument as z
!€   [1!, 2!, 3!, ..., z!]
  ċ  count the number of occurrence of z
Leaky Nun
źródło
19

Galaretka , 4 bajty

Œ?IE

Nie jest to najkrótsza odpowiedź na żelki, ale jest raczej wydajna.

Wypróbuj online!

Jak to działa

Œ?IE  Main link. Argument: n

Œ?    Yield the n-th permutation of the positive integers, without the sorted tail.
      For 120, this yields [5, 4, 3, 2, 1], the tail being [6, 7, 8, ...].
  I   Increments; compute all forward differences.
      For 120, this yields [-1, -1, -1, -1].
   E  Check if all differences are equal.
Dennis
źródło
2
Ponieważ my kodujemy golfistów dbamy o wydajność.
Okx,
12
To radykalna poprawa złożoności kosztem jednego bajtu i sprytne użycie wbudowanego, jeśli sam mogę to powiedzieć. ¯ \ _ (ツ) _ / ¯
Dennis
Co ciekawe, zwraca wartość true dla 0, podczas gdy 3 bajtowa odpowiedź @ LeakyNun, podczas gdy ogólnie znacznie wolniejsza, poprawnie zwraca false dla 0. Czy dodatkowe bajty są potrzebne, aby zwrócić false dla 0 w odpowiedzi czasu efektywnego wykonania?
Deadcode
@Deadcode Sprawdzanie wartości 0 wymagałoby dwóch dodatkowych bajtów. Jeśli nie masz pewności, czy definicja „liczb naturalnych” w PO obejmuje 0, czy nie. Przypadki testowe nie ...
Dennis
17

ECMAScript regex 733+ 690+ 158 119 118 (117🐌) bajtów

Moje zainteresowanie regexem rozbudziło nowe życie po ponad 4,5 roku bezczynności. W związku z tym szukałem bardziej naturalnych zestawów liczb i funkcji, które pasowałyby do jednoargumentowych wyrażeń regularnych ECMAScript, wznowiłem ulepszanie mojego silnika wyrażeń regularnych i zacząłem odświeżyć również na PCRE.

Fascynuje mnie obca konstrukcja funkcji matematycznych w wyrażeniu regularnym ECMAScript. Do problemów należy podchodzić z zupełnie innej perspektywy i aż do nadejścia kluczowej wiedzy nie wiadomo, czy można je w ogóle rozwiązać. Wymusza rzucenie znacznie szerszej siatki w celu znalezienia właściwości matematycznych, które można by wykorzystać do rozwiązania konkretnego problemu.

Dopasowywanie liczb czynnikowych było problemem, o którym nawet nie pomyślałem w 2014 r. - lub gdybym tylko chwilowo odrzucił to jako zbyt mało prawdopodobne, aby było to możliwe. Ale w zeszłym miesiącu zdałem sobie sprawę, że można to zrobić.

Podobnie jak w przypadku innych postów z wyrażeniami regularnymi ECMA, dam ostrzeżenie: zdecydowanie zalecam naukę rozwiązywania pojedynczych problemów matematycznych w wyrażeniach regularnych ECMAScript. To była dla mnie fascynująca podróż i nie chcę zepsuć jej nikomu, kto mógłby potencjalnie chcieć spróbować samemu, szczególnie tym, którzy interesują się teorią liczb. W tym wcześniejszym poście znajduje się lista zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.

Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła Ci się jakaś zaawansowana magia wyrażeń regularnych . Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript, jak opisano w linku powyżej.

To był mój pomysł:

Problem z dopasowaniem tego zestawu liczb, jak w większości innych, polega na tym, że w ECMA zwykle nie jest możliwe śledzenie dwóch zmieniających się liczb w pętli. Czasami można je multipleksować (np. Moce tej samej bazy można jednoznacznie sumować), ale zależy to od ich właściwości. Więc nie mogłem po prostu zacząć od liczby wejściowej i podzielić ją przez stopniowo rosnącą dywidendę, aż osiągnę 1 (a przynajmniej tak myślałem).

Potem przeprowadziłem badania na temat mnogości czynników pierwszych w liczbach czynnikowych i dowiedziałem się, że istnieje na to formuła - i prawdopodobnie mógłbym ją zaimplementować w wyrażeniu regularnym ECMA!

Po tym, jak dusiłem go przez chwilę i w międzyczasie skonstruowałem kilka wyrażeń regularnych, podjąłem się zadania napisania wyrażenia regularnego. Zajęło to kilka godzin, ale skończyło się ładnie. Jako dodatkowy bonus algorytm może zwrócić odwrotność silni jako dopasowanie. Nie można było tego uniknąć; z samej natury tego, w jaki sposób należy go wdrożyć w ECMA, konieczne jest odgadnięcie, czym jest odwrotna silnia, zanim zrobi się cokolwiek innego.

Minusem było to, że ten algorytm stworzył bardzo długi regex ... ale byłem zadowolony, że ostatecznie wymagał techniki stosowanej w moim regexie mnożenia 651 bajtów (tej, która okazała się przestarzała, ponieważ inna metoda stworzyła 50 bajt regex). Miałem nadzieję, że pojawi się problem wymagający tej sztuczki: działanie na dwóch liczbach, które są potęgami tej samej bazy, w pętli, poprzez ich jednoznaczne połączenie i rozdzielenie ich przy każdej iteracji.

Ale ze względu na trudność i długość tego algorytmu zastosowałem molekularne wyczekiwanie (formy (?*...)) do jego wdrożenia. Jest to funkcja nie w ECMAScript ani żadnym innym głównym mechanizmie regex, ale ta, którą zaimplementowałem w moim silniku . Bez przechwytywania wewnątrz molekularnego spojrzenia, jest funkcjonalnie równoważny atomowemu spojrzeniu naprzód, ale przy przechwytywaniu może być bardzo potężny. Silnik wróci do poprzedniej wersji i można go użyć do ustalenia wartości, która przechodzi przez wszystkie możliwości (do późniejszego testowania) bez zużywania znaków z danych wejściowych. Korzystanie z nich może zapewnić znacznie czystszą implementację. (Za wyglądem o zmiennej długości ma co najmniej tyle samo mocy, co molekularne spojrzenie w przód, ale ten ostatni sprawia, że ​​bardziej proste i eleganckie wdrożenia).

Tak więc długości 733 i 690 bajtów w rzeczywistości nie reprezentują inkarnacji rozwiązania zgodnych z ECMAScript - stąd „+” po nich; z pewnością możliwe jest przeniesienie tego algorytmu do czystego ECMAScript (co znacznie zwiększyłoby jego długość), ale nie poradziłem sobie z tym ... ponieważ myślałem o znacznie prostszym i bardziej zwartym algorytmie! Taki, który można łatwo wdrożyć bez uprzedzeń molekularnych. Jest także znacznie szybszy.

Ten nowy, podobnie jak poprzedni, musi odgadnąć odwrotną silnię, przechodząc przez wszystkie możliwości i testując je pod kątem dopasowania. Dzieli N przez 2, aby zrobić miejsce na pracę, którą musi wykonać, a następnie tworzy pętlę, w której wielokrotnie dzieli dane wejściowe przez dzielnik, który zaczyna się od 3 i zwiększa za każdym razem. (Jako takie, 1! I 2! Nie mogą być dopasowane przez główny algorytm i muszą być traktowane osobno.) Dzielnik jest śledzony przez dodanie go do bieżącego ilorazu; te dwie liczby można jednoznacznie rozdzielić, ponieważ przy założeniu M! == N, bieżący iloraz będzie nadal podzielny przez M, dopóki nie wyniesie M.

Wyrażenie regularne wykonuje dzielenie według zmiennej w najbardziej wewnętrznej części pętli. Algorytm podziału jest taki sam, jak w moich innych wyrażeniach regularnych (i podobny do algorytmu mnożenia): dla A≤B, A * B = C, jeśli istnieje, tylko jeśli C% A = 0 i B jest największą liczbą, która spełnia B≤C i C% B = 0 i (CB- (A-1))% (B-1) = 0, gdzie C to dywidenda, A to dzielnik, a B to iloraz. (Podobny algorytm można zastosować w przypadku, gdy A ≥B, a jeśli nie wiadomo, jak A porównuje się do B, wystarczy jeden dodatkowy test podzielności.)

Uwielbiam więc to, że problem mógł zostać zredukowany do jeszcze mniejszej złożoności niż mój zoptymalizowany golfowo regex Fibonacciego , ale wzdycham z rozczarowaniem, że moja technika multipleksowania mocy tej samej bazy będzie musiała poczekać na inny problem to faktycznie tego wymaga, ponieważ ten nie. To historia mojego algorytmu mnożenia 651 bajtów, który został zastąpiony przez 50-bajtowy!

Edycja: Udało mi się upuścić 1 bajt (119 → 118), używając sztuczki znalezionej przez Grimy'ego, która może dodatkowo skrócić podział w przypadku, gdy iloraz gwarantowany jest większy lub równy dzielnikowi.

Bez zbędnych ceregieli, oto regex:

Wersja prawda / fałsz (118 bajtów):

^((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\3$|^xx?$

Wypróbuj online!

Zwraca odwrotną silnię lub brak dopasowania (124 bajty):

^(?=((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\3$)\3|^xx?$

Wypróbuj online!

Zwraca odwrotną silnię lub brak dopasowania w ECMAScript +\K (120 bajtów):

^((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\K\3$|^xx?$

I wersja z odstępami z komentarzami:

  ^
  (?=                           # Remove this lookahead and the \3 following it, while
                                # preserving its contents unchanged, to get a 119 byte
                                # regex that only returns match / no-match.
    ((x*)x*)(?=\1$)             # Assert that tail is even; \1 = tail / 2;
                                # \2 = (conjectured N for which tail == N!)-3; tail = \1
    (?=(xxx\2)+$)               # \3 = \2+3 == N; Assert that tail is divisible by \3
    # The loop is seeded: X = \1; I = 3; tail = X + I-3
    (
      (?=\2\3*(x(?!\3)xx(x*)))  # \5 = I; \6 = I-3; Assert that \5 <= \3
      \6                        # tail = X
      (?=\5+$)                  # Assert that tail is divisible by \5
      (?=
        (                       # \7 = tail / \5
          (x*)                  # \8 = \7-1
          (?=\5(\8*$))          # \9 = tool for making tail = \5\8
          x
        )
        \7*$
      )
      x\9                       # Prepare the next iteration of the loop: X = \7; I += 1;
                                # tail = X + I-3
      (?=x\6\3+$)               # Assert that \7 is divisible by \3
    )*
    \2\3$
  )
  \3                            # Return N, the inverse factorial, as a match
|
  ^xx?$                         # Match 1 and 2, which the main algorithm can't handle

Pełna historia moich optymalizacji golfowych tych wyrażeń regularnych znajduje się na github:

regex dla dopasowania liczb silniowych - metoda porównywania wielokrotności, z molekularnym lookahead.txt
regex dla dopasowania silni liczb.txt (ta pokazana powyżej)

((x*)x*)((x*)+)((x+)+)n=3!\233=0

Mechanizm wyrażeń regularnych .NET nie emuluje tego zachowania w trybie ECMAScript, a zatem 117 wyrażeń regularnych działa:

Wypróbuj online! (wersja spowolnienia wykładniczego z silnikiem regex .NET + emulacja ECMAScript)

Deadcode
źródło
14

JavaScript (ES6), 30 29 28 bajtów

Oczekuje dodatniej liczby całkowitej. Zwraca -1za fałsz i -2za prawdę.

f=(n,k=2)=>n>1?f(n/k,k+1):~n

console.log(1,  '-->',f(1))   // Truthy (0! or 1!)
console.log(2,  '-->',f(2))   // Truthy (2!)
console.log(3,  '-->',f(3))   // Falsey
console.log(4,  '-->',f(4))   // Falsey
console.log(5,  '-->',f(5))   // Falsey
console.log(6,  '-->',f(6))   // Truthy (3!)
console.log(7,  '-->',f(7))   // Falsey
console.log(8,  '-->',f(8))   // Falsey
console.log(24, '-->',f(24))  // Truthy (4!)
console.log(120,'-->',f(120)) // Truthy (5!)

Uwaga : Ta funkcja obsługuje dość duże dane wejściowe (powinieneś to przeczytać jako: „dość duży dla JS”). Powinien działać bezpiecznie do 2 53 - 1 . Na pewno zawiedzie, zaczynając od N = 121 645 100,408,831,992 , przy czym dane wejściowe są zaokrąglane do 19! = 121 645 100 408 832 000 z powodu kodowania IEEE-754. Nie mogą być inne fałszywie dodatnich wyników przed 121,645,100,408,831,991 powodu błędów zaokrągleń, ale nie wiem na pewno.

Arnauld
źródło
Fajnie - naprawdę podoba się użycie ~na końcu.
Steve Bennett
Czy możesz edytować, abym mógł cofnąć głosowanie? (Jeśli chcesz wiedzieć, dlaczego przegłosowałem, to dlatego, że zapomniałem o nietypowych zasadach I / O tego pytania.)
CalculatorFeline
@Arnauld Undownvoted.
CalculatorFeline
11

Python 3 , 39 38 bajtów

f=lambda n,i=1:n>1and f(n/i,i+1)or n<1

Funkcji rekurencyjnej przy całkowitej, nwracając wartość logiczną inversley reprezentującą wynik (truthy: False, falsey: True)

Wypróbuj online!

Wielokrotnie dzieli nprzez i, z początkową wartością 1, aż reszta będzie mniejsza lub równa, 1a następnie przetestuje, czy ta reszta jest mniejsza niż 1, tylko silnia zakończy się resztą równą 1i <będzie bajtem krótszym niż ==.

Jonathan Allan
źródło
@ovs zostaliśmy ograniczeni do dwóch spójnych wyników. To niestety zwraca 1wszystkie czynniki, z wyjątkiem 1których zwraca True.
Jonathan Allan
11

Java 8, 46 bajtów

i->{int j=1,c=0;for(;j<i;j*=++c);return j==i;}

Jest to oparte na wpisie Romana Gräfa, z którego udało mi się zrzucić kilkanaście bajtów. Sugerowałbym to tam, ale nie mam jeszcze wystarczającej reputacji, aby komentować! Mój zmodyfikowany kod biegacza testowego:

import java.util.function.Function;
import java.util.stream.IntStream;

public class IsFactorial {
    public static Function<Integer, Boolean> isFactorial = i->{int j=1,c=0;for(;j<i;j*=++c);return j==i;};
    public static int[] truthyCases = {1,2,6,24,120};
    public static int[] falsyCases = {3,4,5,7,8};
    public static void main(String[] args){
        System.out.println(
            IntStream.of(truthyCases).allMatch(i->isFactorial.apply(i)) &&
            IntStream.of(falsyCases).allMatch(i->!isFactorial.apply(i)));
    }
}
Computronium
źródło
9

Siatkówka , 50 38 bajtów

12 bajtów zaoszczędzonych dzięki @Neil, łącząc skrócenie pętli i pozbycie się ;

.+
1¶$&$*
+`^(1+)¶(\1)+$
1$1¶$#2$*
¶.$

Wypróbuj online!

Dane wyjściowe 1dla wartości true i 0false.

.+ dopasowuje cały numer

1¶$&$*zamieniając go na 1następującą po nim nową linię, a dopasowanie konwertowane na unarne

Pozostały program dzieli liczbę jednostkową w dolnym wierszu przez sukcesywne zwiększanie liczb całkowitych dodatnich, śledzony w górnym wierszu, podczas gdy jest to możliwe.

+` zapętlić, aż łańcuch pozostanie taki sam

  • ^(1+)¶(\1)+$dopasuj górną linię wiele 1si wielokrotność wielu 1s w dolnej linii i zamień ją na

  • 1$1¶$#2$*górna linia wiele 1s z inną 1, to znaczy zwiększenie liczby reprezentowanej przez górną linię o 1, po której następuje nowa linia i liczba dopasowań górnej linii w dolnym wierszu (tj. liczba dopasowań drugiej grupy przechwytywania ) wiele 1s, to znaczy dzielenie dolnej liczby przez górną liczbę

Gdy nie będzie to już możliwe,

¶.$podaj liczbę dopasowań tego wyrażenia regularnego, tj. czy istnieje samotny 1w dolnej linii, co dzieje się tylko wtedy, gdy liczba jest silnia


Jeśli zamiast wartości true / falsy dozwolone jest no-crash / crash, mogę uzyskać 36 34 bajtów.

^
1¶
{`.+$
$*
^(1+)¶(\1)+$
1$1¶$#2

Jest to zgodne z tym samym podejściem, ale łączy $*linie trzecią i czwartą. Trzecia linia dalej jest częścią tej samej pętli, {jest skrótem od tego, +(gdzie (grupuje pozostałe linie w pętli. Czynniki kończą się w programie wyłamującym się z pętli, podczas gdy czynniki nie-czynnikowe utkną w pętli na zawsze, dopóki Retina nie zgłosi wyjątku przepełnienia spowodowanego przez ostatnią awarię wymiany, tym samym posiadając dno w jedności zamiast w systemie dziesiętnym, i pierwszą zamianę pętli konwertuje dolną linię z dziesiętnej na unarną, więc szybko się wysadza.

Kritixi Lithos
źródło
Zapisz bajt, usuwając 1go tak, jak to sugeruje, gdy $*jest na końcu zamiany.
Neil,
Jeszcze lepiej, połącz $*z pozostałymi dwiema liniami.
Neil,
3
Jestem pod wrażeniem, że znalazłeś sposób na awarię Retiny warunkowo. :)
Martin Ender,
2
Czy możesz dodać wyjaśnienie?
CalculatorFeline
8

05AB1E , 4 bajty

L!QO

Wypróbuj online!

Wyjaśnienie

L      # range [1 ... input]
 !     # calculate factorial of each
  Q    # compare with input for equality
   O   # sum
Emigna
źródło
1
Czy nie trzeba najpierw kopiować danych wejściowych, ponieważ są one Lusuwane? Ponadto, Å!daje listę silnia mniejsza lub równa wejścia.
Neil A.
@NeilA. Na szczęście dane wejściowe są ponownie wyświetlane, jeśli na stosie nie ma wystarczającej liczby argumentów do operacji, więc nie potrzebuję Dtutaj. Dobry chwyt Å!. Zawsze zapominam o poleceniach z listy. Nie zapisuje żadnych bajtów, ale na pewno jest bardziej wydajny.
Emigna
Nie wiedziałem o ponownym wprowadzaniu danych wejściowych ... to z pewnością pozwoli zaoszczędzić wiele bajtów.
Neil A.
@NeilA. Jest to dość nowa funkcja. Myślę, że został dodany mniej niż miesiąc temu.
Emigna
8

C ++, 102 100 92 bajtów

#include<cmath>
int a(int n){int i=n,j=0;for(;i;)j|=lround(exp(lgamma(i--+1)))==n;return j;}

Pętle przez wszystkie wartości od 0do ni oblicza silnię, a następnie sprawdza, czy jest równa n.

Dzięki Christoph! (zapisane 8 bajtów)

Technocoder
źródło
Cześć! Witamy w PPCG! Ładna pierwsza odpowiedź! Powodzenia na przyszłość!
Arjun,
Ładna pierwsza odpowiedź! Można zaoszczędzić kilka bajtów takiego: int a(int n){int i=n,j=0;for(;i;)j|=lround(exp(lgamma(i--+1)))==n;return j;}. lroundi lgammasą już w C ++ 11, więc może po prostu #include<cmath>. Może jeszcze bardziej poprawisz moje sugestie :)
Christoph
7

Haskell , 43 26 bajtów

f n=elem n$scanl1(*)[1..n]

Wypróbuj online!

  • Zaoszczędź 17 bajtów, dzięki Laikoni
sudee
źródło
2
f n=elem n$scanl1(*)[1..n]jest absurdalnie nieefektywny, ale krótszy.
Laikoni
Czy nie ma żadnych zasad dotyczących wydajności kodu?
sudee
1
Brak, którego jestem świadomy. code-golf prosi o rozwiązanie w jak najmniejszej liczbie bajtów bez żadnych deklaracji wydajności. Również na moim komputerze funkcja działa 40430bez zauważalnej zwłoki.
Laikoni
Miałem na myśli coś w stylu „rozwiązanie powinno zakończyć się w rozsądnym terminie”, ale myślę, że tak czy inaczej spełnia wymagania. Dzięki!
sudee
1
Ładne i proste. Myślałem, że mogę zrobić lepiej z podziałem powiedzmy, divModprzez [1..]kolejno, aż do osiągnięcia zerowego pozostałą z ilorazu 1 (silnia) lub pozostający niezerową (non-czynnikowej), ale nie wydaje się być dobrym rozwiązaniem. Znalazłam to słodkie rozwiązanie 46-znakowy, ale: f|let x%n=mod n x==0&&(x+1)%div n x||n==1=(1%).
Jon Purdy
6

Haskell , 38 bajtów

m#n=n<2||mod n m<1&&(m+1)#div n m
(2#)

Wypróbuj online! Przykładowe zastosowania: (2#) 24. Zwraca Truelub False.

To najkrótszy możliwy, jaki udało mi się uzyskać, jednocześnie będąc bardzo wydajnym. Nawet dla liczb tak dużych jak

145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000

wynik jest natychmiast podawany. Rozwiązanie działa, dzieląc dane wejściowe n, m = 2,3,4,5,...dopóki wynik nie będzie jeden lub nnie będzie można go podzielić m.

Tutajn! znajdziesz krótsze, ale nieefektywne, 26-bajtowe rozwiązanie obliczające dane wejściowe, które nie są silnikami .

Laikoni
źródło
5

MATL , 5 bajtów

t:Ypm

Wypróbuj online!

Wyjaśnienie

t     % Implicit input. Duplicate
:     % Range from 1 to that
Yp    % Cumulative product
m     % Ismember. Implicit display
Luis Mendo
źródło
5

Fouriera , 40 39 bajtów

I~Q1~N(i^~i*N~N{Q}{1~Xo}N>Q{1}{1~X0o}X)

Wypróbuj na FourIDE!

Zasadniczo mnoży liczbę N przez rosnącą liczbę, aż N będzie równa (wyjście 1) lub większa niż (wyjście 0) wejście.

Objaśnienie Pseudokod:

Q = Input
N = 1
While X != 1
    i += 1
    N = N*i
    If N = Q Then
        Print 1
        X = 1
    End If
    If N > Q Then
        Print 0
        X = 1
    End If
End While
Rozpad beta
źródło
5

Japt , 8 6 bajtów

ol x¥U

Wypróbuj online!

Daje to 0 dla false i 1 dla true.

Wyjaśnienie

 ol x¥ U
Uol x==U
Uo       # Create the range [0 ... input]
  l      # Replace each element by its factorial
     ==U # Compare each element to the input (yielding 1 if equal and 0 otherwise)
    x    # And sum the result
Luke
źródło
1
Naprawdę powinienem dodać wbudowane „zawiera”: P
ETHprodukcje
1
Och, hej, możesz zmienić aU ¦Jna x¥U(mapuj Xdo X==Ui sumuj), chociaż to nie zadziała w TIO.
ETHprodukcje
Nie powiedzie się 2ponieważ posiadał otylko daje [0,1]. Oto poprawka z oszczędnością 1 bajtu.
Shaggy
4

Perl 5, 31 bajtów

$a=<>;$a/=++$i while$a>1;exit$a

Dane wejściowe są pobierane przez STDIN, dane wyjściowe są przekazywane za pomocą kodu wyjścia (1 dla silnia, 0 dla bez silnia).

Dane wejściowe są dzielone przez kolejne liczby całkowite, aż będzie to 1 lub jakaś ułamek mniejszy niż jeden, co zostanie obcięte w wyniku.

faubi
źródło
-5 bajtów TIO
Nahuel Fouilleul
4

Perl 6 , 29 bajtów

{($_,{$_/++$}...2>*).tail==1}

Sprawdź to

Rozszerzony:

{   # bare block lambda with implicit parameter 「$_」

  (              # generate a sequence

    $_,          # starting with the input

    {
      $_ / ++$   # divide previous element by an ever increasing number
                 # 1,2,3,4,5,6,7,8 ... *
    }

    ...          # keep generating until

    2 > *        # 2 is greater than what was generated
                 # ( 1 or a fractional number )

  ).tail == 1    # check if it ended at 1
}
Brad Gilbert b2gills
źródło
17 bajtów: {$_∈[\*] 1..$_}. Innym interesującym podejściem jest 2>*.polymod(1..*).sum.
nwellnhof,
4

setlX , 32 bajty

f:=n|=>exists(x in{0..n}|n==x!);

Tworzy funkcję o nazwie, w fktórej wykorzystujesz potencjalną silnię jako parametr.

Działa z dowolną wielkością całkowitą, ale jest dość nieefektywna.

(tak przy okazji: to mój pierwszy udział w łamigłówce programistycznej)

BlueWizard
źródło
4

C (gcc), 33 bajty

e;f(n){n=n%++e?n==!(e=0):f(n/e);}

Zauważ, że niektórzy autorzy definiują „liczbę naturalną” jako liczbę całkowitą dodatnią . Dlatego nie obchodzi mnie to, że f(0)powoduje nieskończoną rekurencję.

Hagen von Eitzen
źródło
Można upuścić do 32 bajtów: Wypróbuj online! lub 31 bajtów, zwracając wartość niezerową dla false: Wypróbuj online!
Deadcode
4

C # (.NET Core) , 68 bajtów

bool f(System.Numerics.BigInteger n,int k=2)=>n<2||n%k<1&f(n/k,k+1);

Wypróbuj online!

Nie jest to najkrótsze rozwiązanie, ale działa z naprawdę dużymi liczbami. Łącze TIO zawiera przykład z 10000!.

Oto krótsza wersja, która używa, intktóra ma maksymalną wartość 2147483647 .

C # (.NET Core) , 45 bajtów

bool f(int n,int k=2)=>n<2||n%k<1&f(n/k,k+1);

Wypróbuj online!

Podziękowania dla @KevinCruijssen za grę w golfa w sumie 3 bajty z obu odpowiedzi!

dana
źródło
2
&&Można golfed się &i spływu ;nie musi być liczona dla funkcji lambda. Czy nie może ulong k=2być uint k=2w 50-bajtowej odpowiedzi?
Kevin Cruijssen
1
Dobry chwyt w &walce z przeciwnikiem &&. Myślałem, że mam przepełnienie stosu, ale wydaje się, że to mimo wszystko działa. ulongma 64 bity, a uint32. Wygląda na to, że inni używają, intwięc może użyję tego w krótkiej wersji. Jeśli chodzi o trailing ;, są to pełne funkcje, a nie lambda, więc myślę, że muszę je uwzględnić?
dana
To naprawdę dziwne, jak .NET może rozwiązać /i %pomiędzy ulongi uint, ale nie ulongi int. Nie wiedziałem o tym :)
dana
1
@Oliver - kiedy doublezaczniesz widzieć zaokrąglanie w pewnym momencie - na przykład 24! i 120! zawieść. Choć System.Numerics.BigIntegerma największą precyzję, intjest najkrótszą odpowiedzią :)
dana
1
@Deadcode - masz rację około 0 :) Na podstawie przykładów w wyzwaniu zinterpretowałem „liczby naturalne” jako 1,2, ... Zgadzam się, że w prawdziwym świecie lepiej jest użyć &&operatora zwarcia . Ale to jest golf golfowy;) Cieszę się, że podoba ci się ten 10000!przykład!
dana
4

C ++ (clang), 51 bajtów

Rekurencja wygrywa w miarę gry w golfa.

51 bajtów, zero to prawda:

int f(int n,int i=2){return n<2?!n:n%i|f(n/i,i+1);}

Poświęca to dość dużą prędkość za 1 bajt oszczędności. Wymień |się ||zrobić to szybko, ze względu na oceny zwarciowej logiczną OR.

Wypróbuj online!(51-bajtowa wersja wolna)
Wypróbuj online! (52 bajtowa wersja szybka)

Wolna wersja gry bez golfa:

int isFactorial(int n, int i=2)
// returns 0 for true, and nonzero for false
{
    if (n < 2) // same as "if (n==0 || n==1)" in our natural number input domain
    {
        if (n==0)
            return 1; // not factorial
        else // n==1
            return 0; // is factorial (could be either 0! or 1!)
    }

    // Because any nonzero value represents "false", using "|" here is equivalent
    // to "||", provided that the chain of recursion always eventually ends. And
    // it does always end, because whether or not "n" is factorial, the "n / i"
    // repeated division will eventually give the value of zero or one, satisfying
    // the above condition of termination.
    return (n % i) | isFactorial(n / i, i+1);
}

Szybka wersja bez golfisty:

int isFactorial(int n, int i=2)
// returns 0 for true, and nonzero for false
{
    if (n < 2) // same as "if (n==0 || n==1)" in our natural number input domain
    {
        if (n==0)
            return 1; // not factorial
        else // n==1
            return 0; // is factorial (could be either 0! or 1!)
    }

    if (n % i != 0)
        return 1; // not factorial
    else
        return isFactorial(n / i, i+1);
}

Istnieje wiele sposobów na zmianę tego.

52 bajty, niezerowa jest prawda:

int f(int n,int i=2){return n<2?n:n%i?0:f(n/i,i+1);}

Wypróbuj online!

52 bajty, zero to prawda:

int f(int n,int i=2){return!n?1:n%i?n-1:f(n/i,i+1);}

Wypróbuj online!

Zanim uciekłem się do rekurencji, próbowałem stworzyć kilka wersji iteracyjnych i były one bliskie.

54 bajty, niezerowa jest prawda:

int f(int n){for(int i=2;n>1;)n=n%i?0:n/i++;return n;}

Wypróbuj online!

54 bajty, zero jest prawdą (na podstawie przesłania Javy 8 Romana Gräfa ):

int f(int n){int a=1,i=0;for(;a<n;a*=++i);return a-n;}

Wypróbuj online!

Teraz, na dole beczki, wersje rekurencyjne bez n==0obsługi (uważam, że są one nieprawidłowe, ponieważ 0 jest liczbą naturalną, a każda definicja, w której nie uwzględnia „liczb naturalnych” o bardzo ograniczonym użyciu). W poniższych wersjach nieskończona rekurencja f(0)albo wyzwala segfault z powodu przepełnienia stosu, albo kompilatory optymalizujące go do iteracji, zapętlają się w nieskończoność:

48 bajtów, zero to prawda:

int f(int n,int i=2){return n%i?n-1:f(n/i,i+1);}

Wypróbuj online!

48 bajtów, zero to prawda (na podstawie przesłania Hagena von Eitzena 33 bajtów C (gcc) ):

int f(int n,int e=0){return n%++e?n-1:f(n/e,e);}

Wypróbuj online!

Deadcode
źródło
50 EDYCJA: 49 , bez rekurencji.
Grimmy
Powrót do rekurencji za 48 . I prawdopodobnie nie polubisz tego, ale 44 używając globalnego var.
Grimmy
3

Mathematica, 20 bajtów

!FreeQ[Range[#]!,#]&

inna wersja do testowania dużych liczb (patrz komentarze)

Range[10^3]!~MemberQ~#&

testy do 1000!

J42161217
źródło
2
Jak rozumiem pytanie, czy Mathematica jest w stanie przyjąć 1001! jako dane wejściowe, to nie spełnia specyfikacji.
Peter Taylor
2
Możesz nawet zapisać trzy bajty, czyniąc je poprawnymi dla wszystkich danych wejściowych. Po prostu zamień 10 ^ 3 na #; możesz zaoszczędzić kolejny bajt używając Range @ #
Julien Kluge
@Julien Klugethen szukając 1243234 zajmie wieczność ...
J42161217
1
Myślę, że możesz zapisać kolejny bajt, zastępując Range[#]go Range@#:)
numbermaniac
3
Wygląda na to, można zapisać kolejny bajt ze składnią Infix: !Range@#!~FreeQ~#&.
numbermaniac
3

Cubix , 24 bajty

U0O@1I1>-?1u>*w;W;@Orq)p

Wypróbuj online

Cubified

    U 0
    O @
1 I 1 > - ? 1 u
> * w ; W ; @ O
    r q
    ) p

Zaczynamy od pchnięcia 1, Input, 1na stos. Będą to odpowiednio nasz indeks, nasz cel i nasz akumulator.

Następnie zapętlamy. Przy każdej iteracji odejmujemy akumulator od wejścia. Jeśli wynik jest 0, skończymy, więc naciskać 1, Output i Wyjdź. Jeśli jest negatywny 0, Ozaszliśmy za daleko, więc wypychamy, wypowiadamy się i wychodzimy. W przeciwnym razie widzimy

;p)*rq;
;         Pop the difference off the stack.
 p)       Move the index to the top of the stack and increment it.
   *      Multiply the accumulator by the index to get the next factorial.
    rq;   Put the stack back in the right order.
Mnemoniczny
źródło
3

Neim , 8 bajtów

𝐈Γ𝐈𝐩₁𝔼)𝐠

Wyjaśnienie:

Example input: 6
𝐈         Inclusive range [1 .. input]
          [1, 2, 3, 4, 5, 6]
 Γ        For each...
  𝐈         Inclusive range [1 .. element]
            [[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6]]
   𝐩        Product
            [1, 2, 6, 24, 120, 720]
     𝔼      Check for equality with
    ₁       the first line of input
            [[0, 0, 1, 0, 0, 0]]
      )   End for each
       𝐠  Select largest element
          [1]

Spróbuj!

Neim , 3 bajty (niekonkurujące)

Niekonkurencyjne, ponieważ token zawiera i token czynnikowy zostały dodane po wykonaniu wyzwania.

𝐈𝐓𝕚

Wyjaśnienie:

Example input: 6
𝐈     Inclusive range [1 .. input]
      [[1, 2, 3, 4, 5, 6]
 𝐓    Factorial each
      [[1, 2, 6, 24, 120, 720]]
  𝕚   Check that the [cycled] input is in the list
      [1]

Spróbuj!

Okx
źródło
3

> <> , 24 22 bajtów

-2 bajty dzięki @Aaron

Próbuję nowego języka (ponieważ wygasła moja licencja Mathematica…)

01\{=n;
?!\$1+:@*:{:}(

Wypróbuj online lub na stronie placu zabaw dla ryb

Zakłada, że ​​numer wejściowy jest już na stosie , i zwraca 0 lub 1. Działa poprzez pomnożenie razem pierwszych n liczb, aż przestanie być mniejszy niż wejściowy, a następnie wypisanie 1, jeśli jest równy wejściowemu, i 0, jeśli nie t.

Nie drzewo
źródło
Możesz zmienić się v>\n<^w \\n/; patrz tutaj
Aaron
@Aaron, to wspaniale, dziękuję!
Nie ma drzewa
3

APL (Dyalog Unicode) , 5 6 7 bajtów

Zagrał w bajt, zmieniając ×/na !dzięki Erik the Outgolfer

⊢∊!∘⍳

Wypróbuj online!

Wyjaśnienie

                          Range of numbers from 1 to argument, 1 2 3 4 .. n
   !                       Factorial; 1! 2! 3! 4! .. n!
⊢∊                         Is the right argument a member of this list?
Kritixi Lithos
źródło
Łączna suma?
Leaky Nun
@LeakyNun Naprawiono
Kritixi Lithos
Jeden dodatkowy bajt w GNU APL 1.2 N∊×\⍳N←⎕Jak to się bierze za argument? nNigdzie nie widzę . Czy to jest coś specyficznego dla Dyalogu?
Arc676
2
@ Arc676 Moje rozwiązanie to pociąg, który nazywacie tak: (⊢∊(×/⍳)) right_argument jak widać w łączu TIO. I odnosi się do właściwego argumentu.
Kritixi Lithos
Uwagi: AGL zaoszczędzi ci bajt; ⊢∊×\ä⍳. „Prawidłowym” (ale dłuższym) rozwiązaniem byłoby 0=1|!⍣¯1; „Czy odwrotna silnia jest liczbą całkowitą?”
Adám
2

JavaScript (ES6), 71 bajtów

Pobiera to dane wejściowe jako argument funkcji i alertdane wyjściowe. Wyjścia 0dla falsey i 1dla truthy.

f=n=>n?n*f(n-1):1;g=(n,r=0,i=0)=>{while(i<=n){r=f(i)==n|r;i++}alert(r)}

Wyjaśnienie

Program składa się z dwóch funkcji foraz g. fjest rekurencyjną funkcją obliczeniową i gjest główną funkcją programu. g zakłada jeden argument n. Definiuje domyślny argument ro wartości 0 i kolejny domyślny argument o wartości 0. Następnie iteruje wszystkie liczby całkowite od 0 do n, i w każdej iteracji sprawdza, czy fzastosowana funkcja i(bieżący indeks) jest równa n, tj. Czy njest silnia i. Jeśli tak się dzieje, rwartość jest ustawiana na 1. Na końcu funkcji, rjestalert ed.

Test Snippet

( Uwaga: Wyjścia fragment wiadomości z wykorzystaniem console.log()jako nikt jak też wiele z tych brzydkie alert()s. )

f=n=>n?n*f(n-1):1;g=(n,r=0,i=0)=>{while(i<=n){r=f(i)==n|r;i++}console.log(r)}

g(1)
g(2)
g(3)
g(4)
g(5)
g(6)
g(7)
g(8)
g(24)
g(120)

Arjun
źródło
Eval może być krótszy niż przy użyciu bloku kodu.
Downgoat
@Downgoat Jak mam to zrobić? Przepraszam, jeśli to zbyt oczywiste! : P
Arjun
2

QBIC , 21 19 bajtów

[:|q=q*a~q=b|_x1}?0

Wyjaśnienie

[:|     Start a FOR loop from 1 to n
q=q*a   q starts as 1 and is multiplied by the FOR loop counter
        consecutively: q=1*1, *2, *3, *4 ... *n
~q=b|   If that product equals n
_x1     Then quit, printing a 1
}       Close the IF and the FOR
?0      If we're here, we didn't quit early and didn't find a factorial, print 0

Poprzednio

[:|q=q*a┘c=c+(q=b)}?c

Wyjaśnienie:

[:|         Start a FOR loop from 1 to n
q=q*a       q starts as 1 and is multiplied by the FOR loop counter
            consecutively: q=1*1, *2, *3, *4 ... *n
┘           Syntactic line break
c=c+        c starts out at 0 and then keeps track of 
    (q=b)       how often our running total == n
}           Closes the FOR-loop
?c          Print c, which is 0 fir non-factorials and -1 otherwise.
Steenbergh
źródło
2

Java 8, 59 bajtów

i->{for(int j=1,c=0;j<=i;j*=++c)if(j==i)return 1;return 0;}

Kod testowy

import java.util.function.IntFunction;
import java.util.stream.IntStream;

public class IsFactorial
{
    public static IntFunction<Integer> isFactorial = i->
    {
        for(int j=1,c=0;j<=i;j*=++c)
            if(j==i)return 1;return 0;
    };

    public static int[] truthyCases = {1,2,6,24,120};
    public static int[] falsyCases = {3,4,5,7,8};

    public static void main(String[] args)
    {
        System.out.println
        (
            IntStream.of(truthyCases)
                .allMatch(i->isFactorial.apply(i)==1)
            && IntStream.of(falsyCases)
                .allMatch(i->isFactorial.apply(i)==0)
        );
    }
}
Roman Gräf
źródło