В этой задаче мы узнали, как кодировать каждое положительное целое число, используя деревья факторов.

Вот как это работает:

• Пустая строка имеет значение 1.

• (S)где Sлюбое выражение со значением S вычисляет S- е простое число.

• ABгде Aи Bявляются arbirary выражения со значениями A и B соответственно , имеет значение A * B .

Например, если бы мы хотели представить 7, мы бы сделали

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

Оказывается, мы можем представить каждое целое число, используя этот метод. На самом деле некоторые цифры мы можем представить несколькими способами. Поскольку умножение коммутативно, 10 является одновременно

((()))()

а также

()((()))

В то же время некоторые числа могут быть представлены только одним способом. Взять 8 например. 8 можно представить только как

()()()

И поскольку все наши атомы одинаковы, мы не можем использовать коммутативность для их реорганизации.

Итак, теперь вопрос «Какие числа могут быть представлены только 1 способом?». Первое наблюдение - это то, что я только что начал делать там. Кажется, что совершенные силы обладают особыми свойствами. При дальнейшем исследовании мы можем найти 36, то есть 6 ² является идеальной степенью, но имеет несколько представлений.

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

И это имеет смысл, потому что 6 уже переставляется, поэтому любое число, которое мы делаем из 6, также должно быть переставляемым.

Итак, теперь у нас есть правило:

• Число имеет уникальное представление, если оно является совершенной степенью числа с уникальным представлением.

Это правило может помочь нам уменьшить определение того, является ли составное число уникальным, чтобы определить, является ли простое число уникальным. Теперь, когда у нас есть это правило, мы хотим выяснить, что делает простое число уникальным. Это на самом деле довольно самоочевидно. Если мы берем уникальное число и заключаем его в круглые скобки, результат должен быть уникальным, и, наоборот, если n имеет несколько представлений, n- е простое число должно иметь несколько представлений. Это дает второе правило:

• П е простое единственно тогда и только тогда , когда п является уникальным.

Оба эти правила являются рекурсивными, поэтому нам понадобится базовый вариант. Какой самый маленький уникальный номер? Можно было бы сказать 2, потому что его просто (), но 1, пустая строка, еще меньше и уникальна.

• 1 уникален.

С помощью этих трех правил мы можем определить, имеет ли число уникальное дерево факторов.

задача

Возможно, вы видели, что он идет, но ваша задача - взять положительное целое число и определить, является ли оно уникальным. Вы должны написать либо программу, либо функцию, которая выполняет эти вычисления. Вы должны вывести одно из двух возможных значений, то, что это за значения, решать вам, но каждый должен представлять «да», будучи выводимым, когда вход является уникальным, и один должен представлять «нет», выводимый в противном случае.

Ваши ответы должны быть оценены в байтах с меньшим количеством байтов, тем лучше.

Контрольные примеры

Вот первая пара уникальных номеров:

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

Предлагаемые тестовые случаи

5381 -> Unique

Кажется, что OEIS A214577 так или иначе связан, поэтому, если вам нужно больше тестов, попробуйте там, но я не знаю, что они одинаковые, так что используйте на свой страх и риск.

Шелуха , 11 10 байт

Сохранено один байт благодаря Zgarb!

Ωεo?oṗ←¬Ep

Возвращает 1для уникального, в 0противном случае

Попробуйте онлайн! Или вернув первые 50

Объяснение:

Ωε              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)

Желе , 10 байт

^{После много возни!}

ÆET0ṪḊ?µl¿

Монадическая ссылка, принимающая положительное целое число и возвращающая, 1если она уникальна или 0нет.

Попробуйте онлайн!

Как?

Æ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

Подождите, логарифм, что ?!

Давайте рассмотрим несколько примеров цикла.

Если n=31( 31 ¹ , одиннадцатое простое):

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

Если 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

Если 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 байта

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

Использование ⎕CY'dfns'с dfnses не очень выполнимо на tio.

Желе , 11 байт

ÆfẋE$ḢÆCµl¿

Попробуйте онлайн!

-2 благодаря очень гениальному трюку Джонатана Аллана .

Используя алгоритм Хаска Х.П.

Пари / ГП , 49 байт

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

Попробуйте онлайн!