Partition N where the count of parts and each part are a power of 2, and part size and count are restricted

Question

How do you take a number representing a list of items, and divide it into chunks, where the number of chunks is a power-of-two, AND where each chunk also has a power-of-two number of items (where size goes up to a max power of two, so 1, 2, 4, 8, 16, 32, 32 being the max)? Is this even possible?

So for example, 8 items could be divided into 1 bucket (power of two bucket) with 8 items (power of two items):

[8]

9 items could be:

[8, 1]

That works because both numbers are powers of two, and the size of the array is 2 (also a power of two).

Let's try 11:

[8, 2, 1]

Nope that doesn't work. Because the size of the array is 3 which is not a power of two, even though it adds to 11. How about this?

[4, 4, 2, 1]

That works! It's 4 elements which is a power of two.

[2, 2, 2, 1, 1, 1, 1, 1]

That also works, since there are 8 buckets (8 is a power of two), with 1 or 2 items each (each a power of two). But [4, 4, 2, 1] is better because it's shorter.

I guess an even better one (after getting comments) would be this, though I didn't see it the first time around:

[8, 1, 1, 1]

That one is short, and also starts with the largest number.

So following this pattern, here are some other numbers:

13:

[8, 1, 1, 1, 1, 1] // no, 6 not power of 2
[8, 2, 1, 1, 1] // no, 5 not power of 2
[8, 2, 2, 1] // yes, 4 is power of 2
[8, 4, 1] // no, 3 not power of 2

14:

[8, 2, 2, 2]

15:

[8, 4, 2, 1]

16:

[16]

18:

[16, 2]

200:

[32, 32, 32, 32, 32, 32, 4, 4]

When the size of the first layer of buckets in the bucket tree grows to longer than 32, then it nests. So take the number 1234 for example. This can be represented by 38 32's followed by 16 followed by 4.

[32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 16, 4]

But now the bucket size is 40 items long, which isn't a power of two AND it's greater than 32. So it should be nested! I can't quite visualize this in my head, so sorry if this isn't a perfect example, I think you can get the gist of what I mean though.

// the parent "x" is 2 in length
x = [a, b]
// child "a" is 32 in length
a = [32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32]
// child "b" is 8 in length
b = [32, 32, 32, 32, 32, 32, 16, 4]

Taken another layer up, say we have a very large number (I don't know what the minimum large number is) that requires another layer of nesting. What we can say about this layer is that, x will be 32 in length, but we will also have a y that is at least 1.

_x_ = [a, b, c, d, e, f, g, h,
       i, j, k, l, m, n, o, p,
       q, r, s, t, u, v, w, x,
       y, z, a2, b2, c2, d2, e2, f2]
_y_ = [a3]
a   = [32, 32, 32, ..., ?]
...
f2   = [32, ..., ?]

Then once we have _x_, _y_, _z_, ... 32 total of these, we build another layer on top.

What is an algorithm/equation that will take a number and divide it into this tree of buckets / item sizes that are all powers of two, up to a max (in this case, 32)?

A subgoal is to minimize the number of levels. There isn't a specific limit, but I am imagining no more than 1 million or very max 1 billion nodes in the entire runtime, so it seems like you'll only have 3 or 4 levels probably, I don't know exactly how to calculate it.

This is going to be used for array lookup. Essentially I am breaking apart a single, large, arbitrarily sized "contiguous" array into small contiguous chunks with size power-of-2 up to 32 in length. This balances lookup performance (i.e. fits within cpu cache), with memory fragmentation.

Update:

I think trying to incorporate this somehow to build up that nested tree I'm trying to describe will help. The last thing now missing is getting the nested arrays to be properly sized to power-of-two values...

The best I have been able to do so far is this:

console.log(spread(74))
console.log(spread(85))
console.log(spread(87))
console.log(spread(127))
console.log(spread(1279))
console.log(spread(12790))
console.log(spread(127901))

function spread(n) {
  if (n == 0) {
    return [0, 0, 0, 0, 0, 0]
  }
  let array = []
  let r = split(n)
  while (r[0] > 31) {
    array.push([32, 0, 0, 0, 0, 0])
    r[0] -= 32
  }
  array.push(r)
  let s = sum(r)
  if (!isPowerOf2(s)) {
    let x = pow2ceil(s)
    let i = 1
    while (i < 5) {
      if (r[i] > 1) {
        i++
        break
      }
      i++
    }
    if (i == 5) {
      i = 0
    }
    main:
    while (true) {
      while (r[i]) {
        r[i + 1] += 2
        r[i]--
        s += 1
        if (s == x) {
          break main
        }
      }
      i++
    }
  }

  if (array.length == 1) {
    return array[0]
  } else if (array.length < 33) {
    return array
  } else {
    return divide(array, 32)
  }
}

function sum(arr) {
  let i = 0
  arr.forEach(x => {
    i += x
  })
  return i
}

function split(n) {
  const r = [0, 0, 0, 0, 0, 0]
  let u = 32
  let i = 0
  while (u > 0) {
    while (n >= u) {
      r[i]++
      n -= u
    }
    i += 1
    u >>= 1
  }
  return r
}

function isPowerOf2(v) {
  return v && !(v & (v - 1))
}

function pow2floor(v) {
  var p = 1;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function pow2ceil(v) {
  var p = 2
  while (v >>= 1) {
    p <<= 1
  }
  return p
}

function divide(data, size) {
  const result = []
  const upSize = data.length / size;

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

Answer 1

It's always possible.

Start with the normal binary representation.

You get a number of summands that are all powers of 2.

So the problem is the number of summands is most of the times not a power of two.

You can always get an extra summand by splitting a power of 2 in 2 summand (also powers of 2). Only exception is 1.

So the question is there a case where not enough summand > 1 exists?

Answer: No

Worst case is we have n summand where n is a (power of 2)-1. E.g. 3, 7,15, ... Is we have 3 summand the smallest possible case is 1+2+4. We need 4 summand, so we must create 1 extra summand by splitting one of the summands >1 into two. e.g 1+1+1+4.

For bigger values the highest summand is always >= ceeling(value/2) and has at most ceeling(sqrt(value))+1 summands in binary representation.

ceeling(value/2) grows much faster than sqrt(value).

So we have with increasing values always plenty of summands to split to reach the power of 2 summands goal.

---

Example: value= 63
Binary representation: 32+16+8+4+2+1 (6 summands)
Highest summand is 32 (at least value/2) (which can be split in any number of summands (all powers of 2) up to 32 summands.

We need at most ceeling(sqrt(63))+1 = 8 summands to reach a power of 2 summands.

So we need 2 extra summands for our 32+16+8+4+2+1

Take any summand >1 and split it in two summands (powers of 2) e.g 32 = 16+16
=> 16+16+16+8+4+2+1 (7 summands)
do it again (because we needed 2 extra summands). Take any summand >1 e.g. 4 and split ist 2+2=4
=> 16+16+16+8+2+2+2+1 (8 summands)

Answer 2

Here is a possible algorithm:

Check the lowest 5 bits of the input number n and generate the corresponding powers of 2 in an array. So for instance for n = 13 we get [1, 4, 8]

Divide n by 32 ignoring the above-mentioned bits (floor).

Add to the above array as many values of 32 as n modulo 32. So for example for input = 77 we get [1, 4, 8, 32, 32]

Most of the times this array will have a length that does not exceed 32, but it could go up to 36: [1, 2, 4, 8, 16, 32, ..., 32]. If that happens, extract 16 values from the end of the array and store them in a "carry": this carry will be processed later. So not considering this potential carry, we ensure we end up with an array that is not longer than 32.

Then perform a split in halves of the greatest value in the array (thereby growing the array with one unit) until the array's length is a power of 2. For instance, for the case of 77 we'll have a few of such iterations in order to get [1, 4, 8, 8, 8, 16, 16, 16]

Divide n again by 32 ignoring the remainder (floor).

Consider again n modulo 32. If this is non-zero we have found summands of 32*32, so we create a new array [32, ..., 32] for each of those, and combine that with the previously established array into a new tree. So for instance for 1037, we could get

[
  [1,4,4,4],
  [32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32]
]

If there is room to add a potential carry (i.e. the top level array does not have a length of 32), then do so.

If the length of the array is not yet a power of 2, apply a similar algorithm as previously mentioned, although now a split in half concerns arrays instead of primitive values.

Repeat this division by 32 to identify even higher nested summands, so these are complete 32*32*32 trees, then in the next iteration, these are complete 32⁴ trees, etc, until all of n is accounted for.

At the end, check if the carry is still there and could not yet be added somewhere: if this is the case add an extra level to the tree (at the top) to combine the achieved result with this carry, so they are siblings in an array of 2.

Implementation

Here is an interactive snippet: type a number and the resulting tree will be displayed in real time. Note that the nested tree is really created in this implementation and will consume quite some memory, so to keep the response times acceptable in JavaScript, I have limited the allowed input to numbers with 7 digits, but in theory the only limit is memory and floating point precision (which in this script is guaranteed up to 2⁵³).

// Utility functions
const sum = arr => arr.reduce((a, b) => a+b, 0);
const powersOf2andZero = [0,1,2,4,8,16,32];
const clone = tree => JSON.parse(JSON.stringify(tree));

function createTree(n) {
    let tree = [];
    let carry = null;
    // Isolate 5 least significant bits
    for (let pow of [1, 2, 4, 8, 16]) if (n & pow) tree.push(pow);
    n = Math.floor(n / 32);
    for (let i = n % 32; i > 0; i--) tree.push(32);
    // This array could have more than 32 values, up to 36.
    //   If that happens: remove 16 occurrences of 32, and consider this as carry-over for later treatment.
    if (tree.length > 32) carry = tree.splice(-16); // pop off 16 x 32s.
    // Make the array length a power of 2 by splitting the greatest value (repeatedly)
    let j = tree.length;
    while (!powersOf2andZero.includes(tree.length)) {
        if (j >= tree.length) j = tree.indexOf(tree[tree.length - 1]); // first occurrence of greatest
        // Split greatest value into 2; keep list sorted
        tree.splice(j, 1, tree[j] / 2, tree[j] / 2); // delete, and insert twice the half at same spot
        j += 2;
    }
    // Isolate and count factors of 32, 32², 32³, ...etc. 
    //   Add a superiour level in the tree for each power of 32 that is found:
    n = Math.floor(n / 32);
    let template = 32;
    while (n) {
        if (tree.length > 1) tree = [tree]; // nest
        if (n % 32 < 31 && carry !== null) { // we have room to dump the carry here
            tree.push(carry);
            carry = null;
        }
        template = Array(32).fill(template); // nest the template tree, "multiplying" by 32.
        for (let i = n % 32; i > 0; i--) tree.push(clone(template));
        if (tree.length === 1 && typeof tree[0] !== "number") tree = tree[0]; // Eliminate useless array wrapper
        // Turn this top level into a length that is a power of 2 by splitting the longest array (repeatedly)
        let j = tree.length;
        while (!powersOf2andZero.includes(tree.length)) {
            if (j >= tree.length) j = tree.findIndex(elem => elem.length === tree[tree.length - 1].length);
            // Split longest array into 2; keep list sorted
            let size = tree[j].length / 2;
            tree.splice(j, 1, tree[j].slice(0, size), tree[j].slice(size)); // delete, and insert twice the half
            j += 2;
        }
        n = Math.floor(n / 32);
    }
    // Is the carry still there? Then we cannot avoid adding a level for it
    if (carry) return [tree, carry];
    return tree;
}

// I/O handling
let input = document.querySelector("input");
let output = document.querySelector("pre");

(input.oninput = function () {
    let n = +input.value;
    if (isNaN(n) || n % 1 !== 0 || n < 1 || n > 9999999) {
        output.textContent = "Please enter an integer between 1 and 9999999";
    } else {
        let tree = createTree(n);
        output.textContent = pretty(tree);
    }
})();

function pretty(tree) {
    return JSON.stringify(tree, null, 2)
           .replace(/\[\s*\d+\s*(,\s*\d+\s*)*\]/g, m => m.replace(/\s+/g, ""))
           .replace(/\b\d\b/g, " $&");
}

pre { font-size: 8px }

n: <input type="number" value="927">
<pre></pre>