13
\$\begingroup\$

This question already has an answer here:

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.
\$\endgroup\$

marked as duplicate by H.PWiz, caird coinheringaahing, Zgarb, Erik the Outgolfer code-golf Dec 8 '17 at 18:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Similar to Brain-Flak: () nilad is 2 instead of 1, (...) monad is next prime instead of push, concatenation is multiply instead of add. \$\endgroup\$ – user202729 Dec 8 '17 at 14:39
  • 1
    \$\begingroup\$ @user202729 you could probably get some irony points by writing a Brain-Flak answer—good luck though. \$\endgroup\$ – Stephen Leppik Dec 8 '17 at 16:01
  • \$\begingroup\$ Definitely worth considering. \$\endgroup\$ – user202729 Dec 8 '17 at 16:05
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – H.PWiz Dec 8 '17 at 17:10
  • \$\begingroup\$ Why didn't that come up in the sandbox? \$\endgroup\$ – Stephen Leppik Dec 8 '17 at 18:06
3
\$\begingroup\$

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: "[\"[\\\"\\\"]\"]"
\$\endgroup\$
  • \$\begingroup\$ The ternary if is unnecessary: since p1 is the empty list, the result is the empty string. Also, "()" can be if you switch to square brackets. \$\endgroup\$ – Zgarb Dec 8 '17 at 16:50
  • \$\begingroup\$ 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. \$\endgroup\$ – Zgarb Dec 8 '17 at 16:54
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Mr. Xcoder Dec 8 '17 at 15:57
  • \$\begingroup\$ @Mr.Xcoder "The output is a string". \$\endgroup\$ – user202729 Dec 9 '17 at 12:43
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

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

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