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.
Sis any expression with a value of S evaluates to the Sth prime.
Bare 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
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.
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.
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.