Build an aesthetically pleasing divisor tree

Question

An aesthetically pleasing divisor tree is a tree of divisors of input n that, for any composite number m, has two children nodes that are the pair of divisors that are closest to the square root of m. The left node should be the smaller divisor of m and the right node should be the larger divisor of m. A prime number in the tree should have no children nodes. Your tree may be in the form of text art or an image. The rules for text art output are as follows.

Spacing rules

To space out the nodes on the tree, we have the following rules:

• The nodes at a given depth from the root should all be on the same line of text in the output.

  /  \    NOT    /  \  
 /    \         /    3
2      3       2

• For left nodes, the incoming branch should be on the upper right if the node is a single-digit number, else, just above the last digit. Example:

 /    AND    /
3          720

• For right nodes, the incoming branch should be on the upper left if the node is a single-digit number, else, just above the first digit. Example:

\    AND    \
 7          243

• For outgoing left branches, the branch should begin one space to the left of the number. Example:

  275
 /
11

• For outgoing right branches, the branch should begin one space to the right of the number. Example:

275
   \
   25

• Any two nodes on the same level of the tree should have a minimum of two spaces between them. At the same time, any two subtrees on the same level of the tree should have as few spaces between them as possible.

This tree doesn't work because the **subtrees** are too close.

        504           
       /   \          
      /     \         
     /       \        
    /         \       
   21   .     24     
  /  \  .    /  \    
 /    \ .   /    \   
3      7.  4      6  
        . / \    / \ 
        .2   2  2   3

While this tree does have enough space between its branches.

         504           
        /   \          
       /     \         
      /       \        
     /         \       
    /           \      
   21   ...     24     
  /  \  ...    /  \    
 /    \ ...   /    \   
3      7...  4      6  
        ... / \    / \ 
        ...2   2  2   3

• If any two subtrees are too close together on a tree, they can be separated by adding another row of branches /\ to the tree above the parents.

   441                              
  /   \    Last row is not filled in yet and we have already run out of space.
 21   21
/  \ /  \

Add another row of branches

     441                              
    /   \     Almost, but the 7 and the 3 are too close together.
   /     \    One more row should do it.
  21     21
 /  \   /  \
3    7 3    7

Add another row of branches

      441
     /   \      And we're done.
    /     \
   /       \
  21       21
 /  \     /  \
3    7   3    7

Examples

As a full example, the divisor tree of 24 will look like this:

     24
    /  \
   /    \
  4      6
 / \    / \
2   2  2   3

4 and 6 are the pair of divisors closest to the square root of 24. 4 is on the left, because it's smaller. On the next line, the number 2 to the left of 3, because it's smaller.

The divisor tree for 63 should look like:

  63        and NOT like this        63
 /  \                               /  \
7    9                             3   21
    / \                               /  \
   3   3                             7    3

In the incorrect tree, 3 and 21 are not the pair of divisors closest to the square root of 63, and 3 and 7 are not sorted properly. The branch placement on the 21 is correct, though.

For 42, you should have:

    42      and NOT        42
   /  \                   /  \
  6    7                 21   2
 / \                    /  \
2   3                  3    7

Let's have a look at 720. Note that we need five levels of branches from 720 so that the 24 and 30 subtrees are correctly spaced. Also, note that 24 and 30 have two levels of branches because 4 and 6 have children nodes that need correct spacing and the children nodes of 30 need to be on the same level as the children nodes of 24.

           720
          /   \
         /     \
        /       \
       /         \
      /           \ 
     24           30
    /  \         /  \
   /    \       /    \
  4      6     5      6
 / \    / \          / \
2   2  2   3        2   3

The challenge

• Your task is to build a correctly-spaced aesthetically pleasing divisor tree for input n, where n is a positive integer greater than 1.
• Your output may contain leading and trailing spaces and leading and trailing newlines, but must otherwise conform to the spacing rules given above.
• Your output is allowed to be: text art, an image (other formats to be added, if needed).
• For images, make sure your tree's nodes are well-spaced, and that nodes at the same height in the tree are at the same height in the image.
• This is code golf. Least number of bytes (or equivalent) wins.

Credit to Stewie Griffin for thinking of this idea, and many thanks to Peter Taylor, Martin Ender, Mego, and Eᴀsᴛᴇʀʟʏ Iʀᴋ for their help in rewriting the specification. As usual, any suggestions or corrections are much appreciated. Good luck and good golfing!

More test cases:

2

  4
 / \
2   2

    20
   /  \
  4    5
 / \
2   2

  323
 /   \
17   19

                        362880
                       /      \
                      /        \
                     /          \
                    /            \
                   /              \
                  /                \
                 /                  \
                /                    \
               /                      \
              /                        \
            576                        630
           /   \                      /   \
          /     \                    /     \
         /       \                  /       \
        /         \                /         \
       /           \              /           \
      /             \            /             \
     24             24          21             30
    /  \           /  \        /  \           /  \
   /    \         /    \      /    \         /    \
  4      6       4      6    3      7       5      6
 / \    / \     / \    / \                        / \
2   2  2   3   2   2  2   3                      2   3

              1286250
             /       \
            /         \
           /           \
          /             \
         /               \
      1050               1225
     /    \             /    \
    /      \           /      \
   /        \         /        \
  30        35       35        35
 /  \      /  \     /  \      /  \
5    6    5    7   5    7    5    7
    / \
   2   3

Answer 1

Python 2, 711 651 575 559 554 547 539 540 530 522 bytes

After four months of trying to write this answer, running into a wall, leaving it for a weeks, rinse, repeat, I have finally finished a proper ASCII art answer for this challenge. All that's left is the golfing, and so, golfing suggestions are very welcome. Try it online!

Golfs: -60 bytes from renaming some often used functions and changing how the result is returned. -73 bytes from changing how the subtrees' heights are checked, how the spacing variables are calculated, and how the result is returned. -3 bytes from FlipTack's isdigit() replacement. -16 bytes golfing that isdigit() replacement even further and replacing " " with E. -5 bytes from minor improvements and changing from Python 3 to Python 2. -7 bytes from modifying how the result is returned. -8 bytes from a small change to how A is defined, changing how T is defined, and adding W, using the hypothesis that any subtree with at least one longer branch than its counterpart, is necessarily longer overall than its counterpart, removing Q altogether, and editing how the result is returned. -10 bytes from using A<10 instead of L(S(A))<2 for A and B. -8 bytes from changing the default H to [0] since the code avoids the problem of mutable default arguments by never mutating H, changing how q is defined by using (B>9) instead of 1-(B<10), removing p altogether, and creating F as a replacement for p+q-M.

Bug fixes: Hypothesis was wrong, counterexample in 11**9 = 2357947691. +1 byte

G=range;L=len;E=" "
def t(n,H=[0]):
 A=max(z*(n%z<1)for z in G(1,int(n**.5)+1));B=n/A;Z=str(n);M=L(Z)
 if A<2:return[Z]
 T=max([i for i in G(L(w))if"/"not in w[i]]for w in(t(A),t(B)));V=H[1:]or[T[k+1]-T[k]-1for k in G(L(T)-1)];x=t(A,V);y=t(B,V);P=x[0].rindex(str(A)[-1])+(A<10);q=y[0].index(str(B)[0])+(B>9);F=L(x[0])-P+q-M;h=H[0]or(F+M%2+2)/2or 1;return[E*(P+J)+(J<h and"/"+E*(2*h+M-2*J-2)+"\\"or Z)+E*(L(y[0])-q+J)for J in G(h,-1,-1)]+[(E*(2*h-F)).join(I<L(w)and w[I]or E*L(w[0])for w in(x,y))for I in G(max(L(x),L(y)))]

Explanation

The whole function can be boiled down to about four steps:

1. Determine the largest divisor pair of n, A and B.
2. Make the subtrees of A and B, redrawing as needed.
3. Determine the number of spaces that should go between the subtrees.
4. Draw and return the new divisor tree.

I will go through each step in order.

Step 1. This is the easiest step, quite frankly. Check every number z between 1 and the square root for divisibility into n and grab the largest z and n//z that matches. Return just str(n) if n is prime (either A==1 or B==n)

Step 2. Draw the subtrees of A and B and get the number of /\ branches between nodes in the subtrees. To do this, we get the indices of every step that has digits in them, get the first differences of the indices, and subtract 1 again. Once we have the heights, we compare them to get the largest, and redraw the subtrees with the new heights.

I have a sneaking suspicion that the subtree that is taller overall always has branches as long as or equal to the branches on the shorter subtree, and I can use that to golf the code, but I have no proof of this yet. Counterexample in 11**9 = 2357947691.

Step 3. This step is what took months to write. Step 2 took a few days to write and debug, but finding the right formulas for the spacing took ages. I'll see if I can condense what I figured out into a few paragraphs. Note that some of the code in this explanation has since been golfed out of the real code.

First, p, q, h, P, Q, s and M.p is the number of characters from the end of the left branch / to the right end of the left subtree. q is the number of characters from the left end of the right subtree to the end of the right branch /. h is the number of branches between the root and the subtrees. P and Q are just the inverses of p and q and are useful for placing the spaces around /\ branches up to the root n. s is the number of spaces that add between the two subtrees. M is simplest; it's the length of n. Put graphically:

            M
           ---
           720           
 |        /   \          
 |       /     \         
h|      /       \        
 |     /         \       
 |    /           \      
   P    p    s   q   Q   
------______---____------
     24           30     
    /  \         /  \    
   /    \       /    \   
  4      6     5      6  
 / \    / \          / \ 
2   2  2   3        2   3

The formula for determining p is this: p = len(x[0]) - x[0].rindex(str(A)[-1]) - (A<10), the length, minus the zero-index of the last character in A, minus a correction for single-digit As.

The formula for determining q is this: q = y[0].index(str(B)[0]) + (B>9), the index of the first character in B, plus a correction for zero-indexing, minus a correction for single-digit Bs (combined into one correction for multiple-digit Bs).

The formula for determining h is this: h = H[0] or (p+q+M%2+2-M)//2 or 1. Either we grab from a predefined H which means we're redrawing the tree, we use (from_the_left + from_the_right + parity_space + 2 - len(root)) // 2), or we use the minimum number of branch levels, 1.

The formula for determining s is this: s = 2*h+M-p-q. We subtract p and q from the number of spaces between the root's branches at their widest 2*h + M.

Step 4. And finally we put it all together. First we make the root, [" "*(P+h)+Z+" "*(Q+h)], then we put in the branches down to the subtrees, [" "*(P+J)+"/"+" "*(2*h+M-2*J-2)+"\\"+" "*(Q+J)for J in G(h)][::-1], and finally we put in our properly spaced subtrees, [(" "*(2*h+M-p-q)).join([(I<L(w)and w[I]or" "*L(w[0]))for w in(x,y)])for I in G(max(L(x),L(y)))].

Et voilà! We have ourselves an aesthetically pleasing divisor tree!

Ungolfing:

def tree(n, H=[0]):
    A = max(z for z in range(1, int(n**.5)+1) if n%z<1)
    B = n/A
    Z = str(n)
    M = len(Z)
    if A < 2:
        return [Z]

    # redraw the tree so that all of the numbers are on the same rows
    x = tree(A)
    y = tree(B)
    for W in [x, y]:
        T = [i for i in range(len(W)) if "/" not in W[i]]
    V = H[1:] or [T[k+1]-T[k]-1 for k in range(len(T)-1)]
    x = tree(A, V)
    y = tree(B, V)

    # get the height of the root from the two trees
    P = x[0].rindex(str(A)[-1]) + (A < 10)
    p = len(x[0]) - P
    q = y[0].index(str(B)[0]) + (B > 9)
    Q = len(y[0]) - q
    h = hs[0] or (p+q+M%2+2-M)/2 or 1

    # and now to put the root down
    R = []
    s = 2*h+M-p-q
    for I in range(max(len(x),len(y))):
        c = I<len(x) and x[I] or " "*len(x[0])
        d = I<len(y) and y[I] or " "*len(y[0])
        R += c + " "*s + d,
    for J in range(h, -1, -1):
        if J<h:
            C = "/" + " "*(2*h+M-2*J-2) + "\\"
        else:
            C = Z
        R += [" "*(P+J) + C + " "*(Q+J)]
    return R

Answer 2

Mathematica, 96 86 81 79 78 bytes

Thanks @MartinEnder for 2 bytes.

TreeForm[If[PrimeQ@#,#,#0/@(#2[#,#2/#]&[Max@Nearest[Divisors@#,#^.5],#])]&@#]&

The output looks like this:

Explanation

Max@Nearest[Divisors@#,#^.5]

Generate the list of divisors of the input. Find the element nearest to the square root of the input. (Max is for flattening the output)

#2[#,#2/#]&

Find the other divisor by dividing the input by the divisor found above, apply the input as the head of the result.

#0/@

Repeat the process.

If[PrimeQ@#,#, ... ]

If the input is prime, don't do anything.

TreeForm

Format the output.

Edit: A more aesthetically pleasing version (258 bytes)

TreeForm[#/.{a_,_,_}:>a,VertexRenderingFunction->(#2~Text~#&),VertexCoordinateRules->Cases[#,{_,_},Infinity,Heads->True]]&@(If[PrimeQ@#,{##},{##}@@#0@@@({{#,#3-#4{1,√3}/2,#4/2},{#2/#,#3-#4{-1,√3}/2,#4/2}}&[Max@Nearest[Divisors@#,√#],##])]&[#,{0,0},1])&

The output looks like this:

Answer 3

Charcoal, 302 bytes

≔⟦⟦Ｎ⁰θ⁰¦⁰⟧⟧θＦθ«≔§ι⁰ζ≔⌈Ｅ…·²Ｘζ·⁵∧¬﹪ζκκη¿η«Ｆ⟦η÷ζη⟧«≔⟦κ⊕§ι¹Ｉκ⁰¦⁰⟧κ⊞ικ⊞θκ»⊞υι»»≔…⁰⌈Ｅθ§ι¹ηＦ⮌竧≔ηι⊕⌈⟦⁰⌈Ｅυ∧⁼§κ¹ι÷Σ⟦¹§§κ⁵¦⁴‹⁹§§κ⁵¦⁰§§κ⁶¦³‹⁹§§κ⁶¦⁰±Ｌ§κ²⟧²⟧ＦυＦ²§≔κ⁺³λ⁺⁺§ηι∨⊖Ｌ§§κ⁺⁵벦¹§§κ⁺⁵λ⁺³λ»Ｆυ«§≔§ι⁵¦³⁻⁻§ι³§η§ι¹∨⊖Ｌ§§ι⁵¦²¦¹§≔§ι⁶¦³⁻⁺⁺§ι³Ｌ§ι²§η§ι¹‹⁹§§ι⁶¦⁰»Ｆ⊕Ｌη«Ｆθ«Ｆ⁼§κ¹ι«←⸿Ｍ§κ³→Ｆ‹⁵Ｌκ«↙Ｐ↙§ηι↗»§κ²↓Ｆ‹⁵ＬκＰ↘§ηι»»Ｍ⊕§ηι↓

Try it online! Link is to verbose version of code. As the verbose version is very verbose, he's a JavaScript transliteration of the main algorithm:

u = []; // predefined variable, used as list of branches
q = [[+s, 0, s, 0, 0]]; // list of nodes starts with the root.
for (i of q) { // iterate nodes, includes new nodes
    z = i[0]; // get node value
    h = Math.max(...[...Array(Math.floor(z ** 0.5) + 1).keys()].slice(2).filter(
        k => z % k < 1)); // find largest factor not above square root
    if (h) {
        for (k of [h, z / h]) {
            k = [k, i[1] + 1, `${k}`, 0, 0]; // create child node
            i.push(k); // add each child to parent (indices 5 and 6)
            q.push(k); // and to master nodelist
        }
        u.push(i);
    }
}
h = new Array(Math.max(...q.map(i => i[1]))); // list of branch heights
for (i = h.length; i --> 0; ) {
    // find branch height needed to space immediate children apart at this depth
    h[i] = 1 + Math.max(...u.map(k => k[1] == j && // filter on depth
        1 + k[5][3] + (k[5][0] > 9) + k[6][2] + (k[6][0] > 9) - k[2].length
        >> 1)); // current overlap, halved, rounded up
    // calculate the new margins on all the nodes
    for (k of u) {
        k[3] = h[i] + (k[5][2].length - 1 || 1) + k[5][3]; // left
        k[4] = h[i] + (k[6][2].length - 1 || 1) + k[6][4]; // right
    }
}
// calculate the absolute left margin of all the nodes under the root
for (i of u) {
    i[5][3] = i[3] - h[i[1]] - (i[5][2].length - 1 || 1);
    i[6][3] = i[3] + i[2].length + h[i[1]] - (i[6][0] > 9);
}
// print the nodes (sorry, no transliteration available)

Answer 4

C (GCC) + Graphviz, 213 bytes

g(n,c,x,k,l){printf("a%d[label=\"%d\"]",k=c,n);for(x=(int)sqrt(n);x>1;x-=1)n%x||(printf("a%d->a%d a%d->a%d ",k,l,k,c=g(x,l=c+1)+1),c=g(n/x,c),x=0);return c;}main(n){scanf("%d",&n);puts("digraph{");g(n);puts("}");}

Assuming the compiled executable is a.out, run with ./a.out | dot -Tpng.

Takes the input n from stdin and outpus a PNG image to stdout.