21
\$\begingroup\$

In this challenge we learned a way to encode every positive integer using factor trees.

Here is how it works:

  • The empty string has value of 1.

  • (S) where S is any expression with a value of S evaluates to the Sth prime.

  • AB where A and B are arbirary expressions with values of A and B respectively has value A*B.

For example if we wanted to represent 7 we would do

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

Turns out we can represent every whole number using this method. In fact some numbers we can represent in multiple ways. Because multiplication is commutative 10 is both

((()))()

and

()((()))

At the same time some numbers can only be represented in 1 way. Take 8 for example. 8 can only be represented as

()()()

And since all of our atoms are the same we can't use commutivity to reorganize them.


So now the question is "Which numbers can only be represented in 1 way?". The first observation is one I just started making back there. It seems that perfect powers have some special properties. Under further investigation we can find 36, which is 62 is a perfect power but has multiple representations.

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

And this makes sense because 6 is already rearrangable, so any number we make out of 6 must also be rearrangable.

So now we have a rule:

  • A number has a unique representation if it is a perfect power of a number with a unique representation.

That rule can help us reduce determining if a composite number is unique to determining if a prime number is unique. Now that we have that rule we want to figure out what makes a prime number unique. This is actually pretty self evident. If we take a unique number and wrap it in parentheses, the result must be unique, and, going the other way if n has multiple representations the nth prime must have multiple representations. This yields the second rule:

  • The nth prime is unique if and only if n is unique.

Both of these rules are recursive, so we are going to need a base case. What is the smallest unique number? One might be tempted to say 2 because its just (), but 1, the empty string, is even smaller and is unique.

  • 1 is unique.

With these three rules we can determine whether a number has a unique factor tree.

Task

You may have seen it coming, but your task is to take a positive integer, and determine if it is unique. You should write either a program or function that does this computation. You should output one of two possible values, what these values are is up to you but one should represent "yes", being output when the input is unique and one should represent "no" being output otherwise.

Your answers should be scored in bytes with less bytes being better.

Test cases

Here are the first couple unique numbers:

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

Suggested test cases

5381 -> Unique

It seems that OEIS A214577 is somehow related, so if you need more test cases try there, but I don't know they are the same so use at your own risk.

\$\endgroup\$
  • \$\begingroup\$ I believe that the prime factors had to be sorted but whatever. \$\endgroup\$ – Nissa Dec 23 '17 at 17:53
  • 1
    \$\begingroup\$ @JonathanAllan no, it's all here. \$\endgroup\$ – Nissa Dec 23 '17 at 17:55
  • \$\begingroup\$ Suggested test case: 5381 \$\endgroup\$ – Nissa Dec 23 '17 at 17:56
  • \$\begingroup\$ @StephenLeppik Test case added, thanks. \$\endgroup\$ – Sriotchilism O'Zaic Dec 23 '17 at 18:27
  • 1
    \$\begingroup\$ @H.PWiz I'm going to say that a full program can error as output because that is a form of output for a program, but a function must return a value. \$\endgroup\$ – Sriotchilism O'Zaic Dec 23 '17 at 20:48
9
\$\begingroup\$

Husk, 11 10 bytes

Saved one byte thanks to Zgarb!

Ωεo?oṗ←¬Ep

Returns 1 for unique, 0 otherwise

Try it online! Or returning the first 50

Explanation:

Ωε              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)
\$\endgroup\$
  • \$\begingroup\$ Oh, and your explanation says "ȯp←". \$\endgroup\$ – Erik the Outgolfer Dec 23 '17 at 18:31
  • \$\begingroup\$ @EriktheOutgolfer Good catch, fixed \$\endgroup\$ – H.PWiz Dec 23 '17 at 18:32
  • \$\begingroup\$ I think ṁ¬ can be just ¬ since the list must be non-empty in that branch. \$\endgroup\$ – Zgarb Dec 23 '17 at 20:19
  • \$\begingroup\$ @Zgarb Oh fancy, I think you gave me that tip before \$\endgroup\$ – H.PWiz Dec 23 '17 at 20:29
7
\$\begingroup\$

Jelly, 10 bytes

After a LOT of fiddling around!

ÆET0ṪḊ?µl¿

A monadic link taking a positive integer and returning 1 if it is unique or 0 if not.

Try it online!

How?

Æ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

Wait, logarithm, what?!

Lets run through some examples of the loop.

If n=31 (311, the eleventh prime):

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

If n=625 (54):

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

If n=225 (52×32):

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
\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog), 42 bytes

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

Using ⎕CY'dfns' with dfnses isn't very feasible on tio.

\$\endgroup\$
  • \$\begingroup\$ My answer came out quite similar to yours, although, I did write the first version around 4 hours ago \$\endgroup\$ – H.PWiz Dec 24 '17 at 0:22
  • \$\begingroup\$ @H.PWiz look man, I don't really care when people submit in the same language although I usually prefer to just comment when I find shorter solution, but this is almost the same. I don't mind you keeping it, but I find answers that look the same pretty useless. About timing - that's how it works. I dropped dozens of answers because someone else came first. I (and I believe the rest) am doing it for fun, not a real competition. \$\endgroup\$ – Uriel Dec 24 '17 at 0:40
  • \$\begingroup\$ Sorry for taking so long getting around to it, but I have deleted my answer. Looking back, a comment seems like it would have been more appropriate. I think, since I was new to APL at the time, such an answer required a fairly significant amount of effort, and I felt a comment would have made it feel like a waste \$\endgroup\$ – H.PWiz Feb 13 '18 at 2:53
2
\$\begingroup\$

Jelly, 11 bytes

ÆfẋE$ḢÆCµl¿

Try it online!

-2 thanks to a very genius trick by Jonathan Allan.

Using H.PWiz's Husk algorithm.

\$\endgroup\$
  • \$\begingroup\$ Since log to the base one and zero both yield None you can do ÆfẋE$ḢÆCµl¿for 11 :) \$\endgroup\$ – Jonathan Allan Dec 23 '17 at 20:45
  • \$\begingroup\$ @JonathanAllan Hey, that's a first! Nice. \$\endgroup\$ – Erik the Outgolfer Dec 23 '17 at 21:02
1
\$\begingroup\$

Pari/GP, 49 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.