Encode Factor Trees

Question

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 2¹⁵ inclusive.
• The winner is the shortest answer in bytes.

Answer 1

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: "[\"[\\\"\\\"]\"]"

Answer 2

Wolfram Language (Mathematica), 84 81 80 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.

Answer 3

Jelly, 10 bytes

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

Answer 4

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!

Answer 5

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?'':'()'

Test cases

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

Answer 6

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

Answer 7

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