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 ² 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.

Ł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)

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 ¹ , 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 ⁴ ):

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 ² × 3 ² ):

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

APL (Dyalog) , 42 bajty

⎕CY'dfns'
{1≥⍵:1⋄1=≢∪r←3pco⍵:∇1+¯1pco⊃r⋄0}

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

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.

Pari / GP , 49 bajtów

f(n)=d=factor(n);n<2||(#d~<2&&f(primepi(d[1,1])))

Wypróbuj online!