Является ли мой номер уникальным

21

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

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

  • Пустая строка имеет значение 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 2 является идеальной степенью, но имеет несколько представлений.

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

И это имеет смысл, потому что 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 так или иначе связан, поэтому, если вам нужно больше тестов, попробуйте там, но я не знаю, что они одинаковые, так что используйте на свой страх и риск.

Мастер пшеницы
источник
Я считаю, что главные факторы должны были быть отсортированы, но что угодно.
Nissa
1
@JonathanAllan нет, все здесь.
Nissa
Предлагаемый тестовый пример: 5381
Nissa
@StephenLeppik Тестовый набор добавлен, спасибо.
Пшеничный волшебник
1
@ H.PWiz Я собираюсь сказать, что полная программа может выдавать ошибку как вывод, потому что это форма вывода для программы, но функция должна возвращать значение.
Пшеничный волшебник

Ответы:

9

Шелуха , 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)
H.PWiz
источник
Ох, и ваше объяснение говорит " ȯp←".
Эрик Outgolfer
@EriktheOutgolfer Хороший улов, исправлено
H.PWiz
Я думаю, что ṁ¬может быть только ¬потому, что список должен быть не пустым в этой ветви.
Згарб
@ Zgarb Ой, кажется, ты уже дал мне этот совет
H.PWiz
7

Желе , 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 1 , одиннадцатое простое):

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

Если 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
Джонатан Аллан
источник
4

APL (Dyalog) , 42 байта

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

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

Уриэль
источник
Мой ответ получился очень похожим на ваш, хотя я и написал первую версию около 4 часов назад
H.PWiz
@ H.PWis look man, мне все равно, когда люди подают сообщения на одном языке, хотя я обычно предпочитаю просто комментировать, когда нахожу более короткое решение, но это почти то же самое. Я не возражаю против того, чтобы вы его сохранили, но я нахожу ответы, которые выглядят одинаково, бесполезно. Насчет сроков - вот как это работает. Я отбросил десятки ответов, потому что кто-то другой пришел первым. Я (и я верю остальным) делаю это для удовольствия, а не для реальной конкуренции.
Уриэль
Извините, что так долго добрался до него, но я удалил свой ответ. Оглядываясь назад, комментарии кажутся более подходящими. Я думаю, так как я был новичком в APL в то время, такой ответ потребовал довольно значительных усилий, и я чувствовал, что комментарий заставил бы его чувствовать себя как пустая трата времени
H.PWiz
2

Желе , 11 байт

ÆfẋE$ḢÆCµl¿

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

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

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

Эрик Outgolfer
источник
Поскольку вход в базу один и ноль оба дают, Noneвы можете сделать ÆfẋE$ḢÆCµl¿для 11 :)
Джонатан Аллан
@JonathanAllan Эй, это первое! Ницца.
Эрик Outgolfer