Czy mój numer jest unikalny

21

W tym wyzwaniu nauczyliśmy się kodować każdą dodatnią liczbę całkowitą za pomocą drzew czynników.

Oto jak to działa:

  • Pusty ciąg ma wartość 1.

  • (S)gdzie Sdowolne wyrażenie o wartości S jest oceniane na S pierwszą liczbę pierwszą.

  • ABgdzie Ai Bsą arbirary wyrażenia o wartości A i B ma odpowiednio wartość A * B .

Na przykład, jeśli chcielibyśmy reprezentować 7, zrobilibyśmy to

  7 -> (4) -> (2*2) -> ((1)(1)) -> (()())

Okazuje się, że możemy reprezentować każdą liczbę całkowitą za pomocą tej metody. W rzeczywistości niektóre liczby możemy reprezentować na wiele sposobów. Ponieważ mnożenie jest przemienne, 10 to jedno i drugie

((()))()

i

()((()))

Jednocześnie niektóre liczby mogą być reprezentowane tylko w jeden sposób. Weźmy na przykład 8. 8 można przedstawić wyłącznie jako

()()()

A ponieważ wszystkie nasze atomy są takie same, nie możemy używać przemienności do ich reorganizacji.


Więc teraz pytanie brzmi: „Które liczby można przedstawić tylko w jeden sposób?”. Pierwsze spostrzeżenie, które właśnie zacząłem tam robić. Wydaje się, że doskonałe moce mają pewne specjalne właściwości. W ramach dalszych badań możemy znaleźć 36, co oznacza, że ​​6 2 to doskonała moc, ale ma wiele reprezentacji.

(())()(())()
(())()()(())
()(())()(())
()(())(())()
()()(())(())

Ma to sens, ponieważ 6 można już przestawiać, więc każda liczba z 6 musi być również przestawialna.

Więc teraz mamy zasadę:

  • Liczba ma unikalną reprezentację, jeśli jest idealną potęgą liczby z unikalną reprezentacją.

Ta reguła może nam pomóc w ograniczeniu określania, czy liczba złożona jest unikalna, w określaniu, czy liczba pierwsza jest unikalna. Teraz, kiedy mamy tę zasadę, chcemy dowiedzieć się, co czyni liczbę pierwszą wyjątkową. To jest rzeczywiście dość oczywiste. Jeśli weźmiemy unikalny numer i zawińmy go w nawiasach, wynik musi być unikalny, a odwrotnie, jeśli n ma wiele reprezentacji, n- ta liczba pierwsza musi mieć wiele reprezentacji. To daje drugą zasadę:

  • N th Prime jest wyjątkowa tylko wtedy, gdy n jest wyjątkowy.

Obie zasady są rekurencyjne, więc będziemy potrzebować podstawowego przypadku. Jaki jest najmniejszy unikalny numer? Można pokusić się o stwierdzenie 2, ponieważ jest to sprawiedliwy (), ale 1, pusty ciąg znaków, jest jeszcze mniejszy i wyjątkowy.

  • 1 jest wyjątkowy.

Dzięki tym trzem regułom możemy ustalić, czy liczba ma unikalne drzewo czynników.

Zadanie

Być może zauważyłeś, że nadchodzi, ale Twoim zadaniem jest przyjęcie dodatniej liczby całkowitej i ustalenie, czy jest ona unikalna. Powinieneś napisać program lub funkcję wykonującą to obliczenie. Powinieneś wypisać jedną z dwóch możliwych wartości, to, jakie są te wartości, zależy od ciebie, ale należy reprezentować „tak”, wyprowadzając, gdy dane wejściowe są unikalne, a w przeciwnym razie należy reprezentować „nie”.

Twoje odpowiedzi powinny być oceniane w bajtach, przy czym im mniej bajtów, tym lepiej.

Przypadki testowe

Oto kilka pierwszych unikalnych numerów:

1
2
3
4
5
7
8
9
11
16
17
19
23
25
27
31

Sugerowane przypadki testowe

5381 -> Unique

Wygląda na to, że OEIS A214577 jest w jakiś sposób spokrewniony, więc jeśli potrzebujesz więcej przypadków testowych, wypróbuj je, ale nie wiem, czy są one takie same, więc używaj na własne ryzyko.

Kreator pszenicy
źródło
Uważam, że główne czynniki musiały być uporządkowane, ale cokolwiek.
Nissa
1
@JonathanAllan nie, wszystko tu jest.
Nissa,
Sugerowany przypadek testowy: 5381
Nissa,
@StephenLeppik Dodano przypadek testowy, dzięki.
Wheat Wizard
1
@ H.PWiz Powiem, że pełny program może generować błąd jako wynik, ponieważ jest to forma wyniku dla programu, ale funkcja musi zwrócić wartość.
Kreator pszenicy

Odpowiedzi:

9

Łuska , 11 10 bajtów

Oszczędność jednego bajtu dzięki Zgarb!

Ωεo?oṗ←¬Ep

Zwraca 1za wyjątkowe, 0inaczej

Wypróbuj online! Lub zwracając pierwsze 50

Wyjaśnienie:

Ωε              Until the result is small (either 1 or 0), we repeat the following
         p     Get the prime factors
  o?           If ...
        E      they are all equal:
    ȯṗ←           Get the index of the first one into the primes
               Else:
       ¬          Not the list (since non-empty lists are truthy, this returns 0)
H.PWiz
źródło
Aha, a twoje wyjaśnienie mówi „ ȯp←”.
Erik the Outgolfer,
@EriktheOutgolfer Dobry połów, naprawiono
H.PWiz
Myślę, że ṁ¬może tak być, ¬ponieważ lista musi być niepusta w tej gałęzi.
Zgarb
@Zgarb Och, fantazyjne, myślę, że wcześniej dałeś mi tę wskazówkę
H.PWiz
7

Galaretka , 10 bajtów

Po wielu zabawach!

ÆET0ṪḊ?µl¿

Łącze monadyczne przyjmujące dodatnią liczbę całkowitą i zwracające, 1jeśli jest unikalne lub 0jeśli nie.

Wypróbuj online!

W jaki sposób?

ÆET0ṪḊ?µl¿ - Link: number, n     e.g. 11          or 13            or 20
         ¿ - while:
        l  - ...condition: (left) logarithm with base (right)
           -               note: x log 0 and x log 1 both yield None, which is falsey
       µ   - ...do the monadic chain: (first pass shown)
ÆE         -   prime exponent array   [0,0,0,0,1]    [0,0,0,0,0,1]    [2,0,1]
  T        -   truthy indexes         [5]            [6]              [1,3]
      ?    -   if:
     Ḋ     -   ...condition: dequeue (i.e. if length > 1)
   0       -   ...then: literal zero   -              -               0
    Ṫ      -   ...else: tail           5              6               -
           - end result                1              0               0

Czekaj, logarytmie, co ?!

Przejdźmy przez kilka przykładów pętli.

Jeśli n=31( 31 1 , jedenasta liczba pierwsza):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |       31 |        31 |    1.000 -> continue
         2 |       11 |        31 |    0.698 -> continue
         3 |        5 |        11 |    0.671 -> continue
         4 |        3 |         5 |    0.683 -> continue
         5 |        2 |         3 |    0.631 -> continue
         6 |        1 |         2 |    0.000 -> stop, yielding left = 1

Jeżeli n=625( 5 4 ):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |      625 |       625 |    1.000 -> continue
         2 |        3 |       625 |    0.171 -> continue
         3 |        2 |         3 |    0.631 -> continue
         4 |        1 |         2 |    0.000 -> stop, yielding left = 1

Jeżeli n=225( 5 2 × 3 2 ):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |      225 |       225 |    1.000 -> continue
         2 |     *  0 |       225 |-inf+nanj -> continue
         3 |     ** 0 |         0 |     None -> stop, yielding left = 0

*The dequeued list was not empty
**Tailing an empty list in Jelly yields 0
Jonathan Allan
źródło
4

APL (Dyalog) , 42 bajty

CY'dfns'
{1≥⍵:11=≢∪r3pco⍵:∇11pcor0}

Korzystanie ⎕CY'dfns'z dfnses nie jest bardzo wykonalne na TiO.

Uriel
źródło
Moja odpowiedź wyszła dość podobna do twojej, chociaż pierwszą wersję napisałem około 4 godzin temu
H.PWiz
@ H.PWiz wyglądam na człowieka, nie obchodzi mnie to, kiedy ludzie przesyłają w tym samym języku, chociaż zwykle wolę po prostu komentować, gdy znajduję krótsze rozwiązanie, ale to prawie tak samo. Nie mam nic przeciwko temu, że go trzymasz, ale znajduję odpowiedzi, które wyglądają tak samo całkiem bezużytecznie. O czasie - tak to działa. Upuściłem dziesiątki odpowiedzi, ponieważ ktoś inny był pierwszy. Ja (i wierzę reszcie) robię to dla zabawy, a nie prawdziwej konkurencji.
Uriel
Przepraszam, że tak długo się do tego zabieram, ale usunąłem swoją odpowiedź. Patrząc wstecz, wydaje się, że komentarz byłby bardziej odpowiedni. Myślę, że skoro w tym czasie byłem nowy w APL, taka odpowiedź wymagała dość znacznego wysiłku i czułem, że komentarz sprawi, że poczujesz się jak strata
H.PWiz
2

Galaretka , 11 bajtów

ÆfẋE$ḢÆCµl¿

Wypróbuj online!

-2 dzięki bardzo genialnej sztuczce Jonathana Allana .

Korzystanie z algorytmu Husk H.PWiz.

Erik the Outgolfer
źródło
Ponieważ zalogowanie do bazy jeden i zero oba dają zysk None, możesz zrobić ÆfẋE$ḢÆCµl¿za 11 :)
Jonathan Allan
@JonathanAllan Hej, to pierwszy! Miły.
Erik the Outgolfer,