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

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)

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^{4} 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^{53}).

```
// 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>
```