How Often Does the Inner Line Run?

A profiler reports how many times the marked line runs, for three loop shapes:

"square"                      "triangle"                  "halving"
for i in range(n):            for i in range(n):          k = n
    for j in range(n):            for j in range(i):      while k >= 1:
        mark()                        mark()                  mark()
                                                              k //= 2

Write inner_runs(n, shape) returning that count for the given shape.

Examples

Input:  n = 4, shape = "triangle"
Output: 6
Explanation: i = 0 marks nothing, then 1, 2 and 3 marks.

Input:  n = 8, shape = "halving"
Output: 4
Explanation: k takes the values 8, 4, 2, 1.

Constraints

• 0 <= n <= 10**15, so the loops themselves are far too slow to run.
• shape is one of "square", "triangle", "halving".

Goals

• Replace a loop nest by the closed form that counts its steps
• Recognise the square, triangular and halving shapes
• Answer for sizes far too large to simulate