Node n is preceded by n nodes of size at least 1. Half of those nodes, rounded down, have a size that is at least 1 greater (2 instead of 1). Half of those further nodes, rounded down, have a size that is at least 2 greater (4 instead of 2). Half of those have a size that is at least 4 greater.
We can denote rounding down using the floor operator, ⌊x⌋.
Therefore, the offset of node n from the beginning is n + ∑0<i<∞ ⌊n/2i⌋(2i−2i−1) = n + ∑0<i<∞ ⌊n/2i⌋2i−1.
This is integer sequence A006520 except it includes an initial 0.
The following C code demonstrates a calculation of it.
#include <stdio.h> static unsigned int f(unsigned int n) { unsigned int t = n; for (unsigned int p = 1; n /= 2; p *= 2) t += p*n; return t; } int main(void) { for (unsigned int n = 0; n < 20; ++n) printf("%u -> %u.\n", n, f(n)); }
Equivalently, the bits for the binary of n may be reinterpreted as bit i having position value 2i−1•(i+2), instead of the normal 2i. Thus, bit 0 has value 1, bit 1 has value 3, bit 2 has value 6, bit 3 has value 20, and so on. This code demonstrates that:
static unsigned int f(unsigned int n) { unsigned int t = 0; /* i is the bit index. d tracks the power, 2^(i-1). However, it would need to be 1/2 for the first iteration, so instead we make it double the power and divide by 2 when using it. */ for (unsigned int i = 0, d = 1; n; i += 1, d *= 2, n /= 2) t += (n&1) * (i+2)*d/2; return t; }
OP writes in a comment:
it is different, there is plenty of variations possible for this, depending of the size(s) of the nodes.
If the size of a node at level i is s(i), where i is 0 for a leaf and 1 more for each successive parent level, then a general formula is n•s(0) + ∑0<i<∞ ⌊n/2i⌋(s(i)−s(i−1)).
