# Encode Factor Trees [duplicate]

I once saw on the xkcd fora a format for expressing numbers in an odd way. In this "factor tree" format:

• The empty string is 1.
• Concatenation represents multiplication.
• A number n enclosed in parentheses (or any paired characters) represents the nth prime number, with 2 being the first prime number.
• Note that this is done recursively: the nth prime is the factor tree for n in parentheses.
• The factors of a number should be ordered from smallest to largest.

For example, here are the factor trees for 2 through 10:

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


Your task is to take in a positive integer, and output the factor tree for it.

# Test Cases

In addition to the 9 above…

100 => ()()((()))((()))
101 => (()(()(())))
1001 => (()())(((())))(()(()))
5381 => (((((((())))))))
32767 => (()())((((()))))(()()(())(()))
32768 => ()()()()()()()()()()()()()()()


# Rules

• Characters other than ()[]{}<> are allowed in the output, but ignored.
• You should be able to handle any input from 2 to 215 inclusive.
• The winner is the shortest answer in bytes.
• Similar to Brain-Flak: () nilad is 2 instead of 1, (...) monad is next prime instead of push, concatenation is multiply instead of add. Commented Dec 8, 2017 at 14:39
• @user202729 you could probably get some irony points by writing a Brain-Flak answer—good luck though. Commented Dec 8, 2017 at 16:01
• Definitely worth considering. Commented Dec 8, 2017 at 16:05
• I would argue that this is a duplicate of Encode an integer. Here is my solution to that, with the front part removed and [1,0] replaced by "()". Also the Jelly solution there is remarkably similar to the one here Commented Dec 8, 2017 at 17:10
• Why didn't that come up in the sandbox? Commented Dec 8, 2017 at 18:06

## Wolfram Language (Mathematica), 848180 64 bytes

Byte count assumes Windows ANSI encoding.

Thanks to Misha Lavrov for saving 16 bytes.

±1=""
±x_:=Table[{"(",±PrimePi@#,")"},#2]&@@@FactorInteger@x<>""


Try it online!

### Explanation

Quite a literal implementation of the spec. We're defining a unary operator ± via two separate definitions.

±1=""


This is just the base case, the empty string for 1.

±x_:=Table[±#,#2]&@@@FactorInteger@x<>""


For all other x, we factor the integer (this gives a list of prime-exponent pairs, {p, k}), generate a table of k copies of the representation of p. For each p, we figure out the prime's index via PrimePi (i.e. the number of primes less than or equal to it), recursively pass it to ± and wrap the result in parentheses. Then flatten and join the result into a single string.

ÆfÆC$ÐLŒṘ€  Try it online! -7 bytes thanks to user202729 # Explanation ÆfÆC$ÐLŒṘ€  Main Link
ÐL     While the results have not yet repeated
ÆfÆC$Prime factorize the number (vectorizes) and turn each prime to its prime index ŒṘ€ Since none of the lists actually contain anything, turn it to a Python string or else it won't print. Call on each because otherwise there will be an extra set of brackets around the output.  • Since this is the way Jelly outputs, you can say your submission is a monadic link (like a function in other languages), and make it 7 bytes. Commented Dec 8, 2017 at 15:57 • @Mr.Xcoder "The output is a string". Commented Dec 9, 2017 at 12:43 # Husk, 15 7 bytes ṁös;₁ṗp  Try it online! -8 bytes thanks to @Zgarb! ### Explanation Note that the header f€"[]"₁ just filters out all [ & ] characters, it's just so that the output is more readable, if you want to see the original output, here you go. ṁ(s;₁ṗ)p -- define function ₁; example input: 6 p -- prime factorization: [2,3] ṁ( ) -- map and flatten the following (example with 3): "[""]["[\"\"]"]" ṗ -- get prime index: 2 ₁ -- recurse: "[\"\"]" ; -- create singleton: ["[\"\"]"] s -- show: "[\"[\\\"\\\"]\"]"  • The ternary if is unnecessary: since p1 is the empty list, the result is the empty string. Also, "()" can be sø if you switch to square brackets. Commented Dec 8, 2017 at 16:50 • Hmm, actually since characters other than ()[]{}<> are ignored in the output by the rules, J"()" could be s; instead. It produces a ton of quotes and backspaces but the rules explicitly allow it. Commented Dec 8, 2017 at 16:54 # Python 2, 113 110 bytes f=lambda n,d=2,p=1:n>2and(n%d and f(n,d+1,p+all(-~d%i for i in range(2,d)))or'(%s)'%f(p)+f(n/d,d,p))or'()'*~-n  Try it online! ungolfed def f(num, div=2, prime=1): if num > 2: if num % div: # if div does not divide num # try next divisor, add 1 to prime if the next divisor is prime return f(num, div + 1, prime + all((div + 1) % i for i in range(2, div))) else: # if div divides num add div as a factor, continue with num / div return '(%s)' % f(prime) + f(num / div, div, prime) else: # if num <= 1: return '' # if num == 2: return '()' return '()' * (num - 1)  Try it online! # JavaScript (ES6), 93 bytes Uses the same approach as ovs' Python answer. f=(n,d=2,k=1)=>n>2?n%d?f(n,++d,k+(P=n=>n%--d?P(n):d<2)(d)):(${f(k)})+f(n/d,d,k):n-2?'':'()'


f=(n,d=2,k=1)=>n>2?n%d?f(n,++d,k+(P=n=>n%--d?P(n):d<2)(d)):(${f(k)})+f(n/d,d,k):n-2?'':'()' ;[2,3,4,5,6,7,8,9,10,100,101,1001,5381,32767,32768].forEach( n => console.log(n, '->', f(n)) ) # R + numbers, 113 bytes f=function(n)"if"(n<2,"",paste0("(",sapply(match(primeFactors(n),Primes(n)),f),")",collapse="")) library(numbers)  Try it online! Recursive function. Returns a string. function(n) if(n < 2) # 1 is empty string "" # else # paste0("(", # wrap in parens sapply( # for each match(primeFactors(n),Primes(n))), # prime index of factors of n f), # apply f ")", # collapse="") # collapse into a single string # Swift, 155 bytes func f(_ n:Int)->String{var d=0;return n<2 ?"":(d=(2...n).first{n%$0<1}!,n==d).1 ?"(\(f((2...n).filter{m in(2...m).first{m%$0<1}==m}.count)))":f(d)+f(n/d)}  ## Explanation (Ungolfed) func f(_ n:Int) -> String { // Declare recursive function f(n) var d = 0; // Temporary variable d return n < 2 ? // If n < 2: "" // Return empty string : (d = (2...n).first{n %$0 < 1}!, n == d).1 ? // If the lowest number divisible by n
// is equal to n (n is prime):
"(\(f((2...n).filter{m in (2...m).first{   //    Return prime index of n (length of
m % \$0 < 1} == m}.count)))"                //    list of all primes ≤ n)
:                                              // Else:
f(d) + f(n / d)                            //    Return f(d) + f(n / d) where d is
}                                                  //    the smallest number divisible by n
`