Score Tarzan's Olympic Vine-Swinging Routine Olympic vine-swingers perform their routines in standard trees.  In particular, Standard Tree n has vertices for 0 up through n-1 and edges linking each nonzero vertex a to the vertex n % a below it.  So, for example, Standard Tree 5 looks like this:

3
|
2   4
 \ /
  1
  |
  0


because the remainder when 5 is divided by 3 is 2, the remainder when 5 is divided by 2 or by 4 is 1, and the remainder when 5 is divided by 1 is 0.

This year, Tarzan will be defending his gold with new routines, each of which begins at vertex n - 1, swings to vertex n - 2, continues to vertex n - 3, etc., until finally he dismounts to vertex 0.

The score for a routine is the sum of the scores for each swing (including the dismount), and the score for a swing is the distance within the tree between its start and end points.  Thus, Tarzan's routine on Standard Tree 5 has a score of 6:


a swing from 4 to 3 scores three points (down, up, up),
a swing from 3 to 2 scores one point (down),
a swing from 2 to 1 scores one point (down), and
a dismount from 1 to 0 scores one point (down).


Write a program or function that, given a positive integer n, computes the score of Tarzan's routine on Standard Tree n.  Sample inputs and outputs:

 1 -&gt;  0
 2 -&gt;  1
 3 -&gt;  2
 4 -&gt;  6
 5 -&gt;  6
 6 -&gt; 12
 7 -&gt; 12
 8 -&gt; 18
 9 -&gt; 22
10 -&gt; 32
11 -&gt; 24
12 -&gt; 34
13 -&gt; 34
14 -&gt; 36
15 -&gt; 44
16 -&gt; 58
17 -&gt; 50
18 -&gt; 64
19 -&gt; 60
20 -&gt; 66
21 -&gt; 78
22 -&gt; 88
23 -&gt; 68
24 -&gt; 82


Rules and code scoring are as usual for code-golf.
C, 98 97 bytes

F(i){int c[i],t=i-2,n=0,p;for(;++n&lt;i;)for(p=c[n]=n;p=i%p;c[p]=n)t+=c[p]&lt;n-1;return i&gt;2?t*2:i-1;}


This calculates the distance between each pair of points with the following formula:


Add the distance from the root to node A
Add the distance from the root to node B
Subtract 2* the length of the common root of A and B


This has the advantage that when applied to all pairs, it's the same as:


Add 2* the distance from the root to each node
Subtract 2* the length of the common root of each node pair
Subtract the distance from the root to the first node
Subtract the distance from the root to the last node


To make the logic simpler, we assume we're going from node 0 to node n-1, rather than n-1 to 0 as the question states. The distance from the root node to node 0 is obviously 0 (they're the same). And we can see that for (most) trees, the distance from the last node to the root is 2:

                    n+1 % n = 1  for all n &gt; 1
and:                  n % 1 = 0  for all n &gt;= 0
therefore:  n % (n % (n-1)) = 0  for all n &gt; 2


This means we have some special cases (n&lt;2) but we can account for those easily enough.

Breakdown:

F(i){                               // Types default to int
    int c[i],                       // Buffer for storing paths
        t=i-2,                      // Running total score
        n=0,                        // Loop index
        p;                          // Inner loop variable
    for(;++n&lt;i;)                    // Loop through all node pairs (n-1, n)
        for(p=c[n]=n;p=i%p;c[p]=n)  //  Recurse from current node (n) to root
            t+=c[p]&lt;n-1;            //   Increase total unless this is a common
                                    //   node with the previous path
    return i&gt;2?   :i-1;             // Account for special cases at 1 and 2
               t*2                  // For non-special cases, multiply total by 2
}


Thanks @feersum for 1 byte saved



Bonus: Trees!

I wrote a quick-and-dirty program to see what these trees look like. Here's some of the results:

6:

5 4  
| |  
1 2 3
 \|/ 
  0  




8:

  5      
  |      
7 3   6  
|  \ /   
1   2   4
'--\|/--'
    0    




13:

   08              
    |              
11 05   10 09 07   
 |   \ /    |  |   
02   03    04 06 12
 '-----\  /---'--' 
        01         
         |         
        00         




19:

   12                       
    |                       
   07   14                  
     \ /                    
     05    15 11            
       \  /    |            
17      04    08 16 13 10   
 |       '-\  /--'   |  |   
02          03      06 09 18
 '---------\ |/-----'--'--' 
            01              
             |              
            00              




49:

                         31                                                    
                          |                                                    
           30            18   36                                               
            |              \ /                                                 
           19   38 27      13    39 29    32                                   
             \ /    |        \  /    |     |                                   
   26        11    22 44      10    20 40 17   34                              
    |         '-\  /--'        '-\  /--'    \ /                                
47 23   46       05               09        15    45 43 41 37 33 25    35 28   
 |   \ /          '--------------\ |/-------'-----'   |  |  |  |  |     |  |   
02   03                           04                 06 08 12 16 24 48 14 21 42
 '----'--------------------------\ |/----------------'--'--'--'--'--'    \ |/  
                                  01                                      07   
                                   '-----------------\  /-----------------'    
                                                      00