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)
gdzieS
dowolne wyrażenie o wartości S jest oceniane na S pierwszą liczbę pierwszą.AB
gdzieA
iB
są 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.
Odpowiedzi:
Łuska ,
1110 bajtówOszczędność jednego bajtu dzięki Zgarb!
Zwraca
1
za wyjątkowe,0
inaczejWypróbuj online! Lub zwracając pierwsze 50
Wyjaśnienie:
źródło
ȯp←
”.ṁ¬
może tak być,¬
ponieważ lista musi być niepusta w tej gałęzi.Galaretka , 10 bajtów
Po wielu zabawach!
Łącze monadyczne przyjmujące dodatnią liczbę całkowitą i zwracające,
1
jeśli jest unikalne lub0
jeśli nie.Wypróbuj online!
W jaki sposób?
Czekaj, logarytmie, co ?!
Przejdźmy przez kilka przykładów pętli.
Jeśli
n=31
( 31 1 , jedenasta liczba pierwsza):Jeżeli
n=625
( 5 4 ):Jeżeli
n=225
( 5 2 × 3 2 ):źródło
APL (Dyalog) , 42 bajty
Korzystanie
⎕CY'dfns'
zdfns
es nie jest bardzo wykonalne na TiO.źródło
Galaretka , 11 bajtów
Wypróbuj online!
-2 dzięki bardzo genialnej sztuczce Jonathana Allana .
Korzystanie z algorytmu Husk H.PWiz.
źródło
None
, możesz zrobićÆfẋE$ḢÆCµl¿
za 11 :)Pari / GP , 49 bajtów
Wypróbuj online!
źródło