Encode Factor Trees

Wolfram Language (Mathematica), 84 81 80 64 bytes

Byte count assumes Windows ANSI encoding.

Thanks to Misha Lavrov for saving 16 bytes.


Try it online!


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


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


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.

Jelly, 10 bytes


Try it online!

-7 bytes thanks to user202729


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

Husk, 15 7 bytes


Try it online!

-8 bytes thanks to @Zgarb!


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