Does this mathematical technique have a formal name? And why does it work?

Question

When I split a number in the powers of 2. I am able to make any combination of any number that is less than it by taking each number of the series only once.

For example:

$7=1+2+4$

I can construct any number less than or equal to seven using the $3$ numbers $1,2,4$.

Or take $10$ for instance:

$10 = 1 + 2 + 4 + 3$

I can construct any number that is less than or equal to $10$ using the 4 numbers.

How this decomposition is done is via breaking the number in powers of 2 until you can't break it anymore. More examples:

5 -> (1, 2, 2)
10 -> (1, 2, 4, 3)
15 -> (1, 2, 4, 8)
1000 -> (1, 2, 4, 8, 16, 32, 64, 128, 256, 489)

Does this method of decomposition have a name? And how does it allow us to make any number that is less than or equal to it?

Answer 1

There is a process of breaking a number into a sum of powers of $2$, called the binary expansion. To do this, you first see what is the largest power of $2$ that is smaller than your number. Then you take it out, and iterate.

This is different from your own process, because what you do is take powers of $2$ from the smallest ($1$) and keep going till the next larger doesn't fit. However, the usual binary expansion is quite useful, as shown for instance by the example below.

Using it to compute powers efficiently in time is called the fast exponentiation algorithm, or exponentiation by squaring. E.g. to compute $x^7$ all you need is $x$, squared into $x^2$ squared into $x^4$ and multiply all three $$x^7=x\cdot x^2\cdot x^4$$

Answer 2

As far as I know this method does not have a name. Perhaps if you could describe its purpose, or give some context, that would help to find a name.

And it is obvious from the definition that every number can be represented this way; given a number $n$, you keep subtracting higher powers of $2$ the remainder is less than the next power of $2$. The remainder is then the last number in the representation.

Answer 3

To see that you can write every natural number $≤n$ as a partial sum of the decomposition of $n$:

Let $2^k$ be the greatest power of $2$ not exceeding $n$. Then your decomposition is $$n=1+2+\cdots +2^{k-1}+ (n-2^k+1)$$

That is, the "remainder" is $r_n=n-2^k+1$.

We note that $1+2+\cdots +2^{k-1}=2^k-1$ so you can get every natural number $<2^k$ as a partial sum of those terms (using the binary expansion).

But then, adding $r_n$ you get can every natural number from $r_n$ to $r_n+2^k-1=n$ and we are done.

Answer 4

First of all, $1+2+4+\cdots2^n = 2^{n+1}-1$. So, for example

$$1000 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + \color{red}{489}$$ $$1000 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + \color{red}{489}$$
is the same thing as saying $$1000 = (512-1)+\color{red}{489}$$ $$1000 = (2^9-1)+\color{red}{489}$$

If you pick a number, say $2345$, you notice that $$2^{11}-1 = 2047 < 2345 < 2^{12}-1=4095$$

and

$$2345-2047 = 298$$

So

$$2345 = 1 + 2 + 4 + 8 + 16 + 32 + \cdots + 2048 + \color{red}{298}$$

I have never seen anything mathematical that referred to this pattern. So I don't know if it has a name or not, nor can I know if anyone else found it interesting.

Answer 5

Countrary to most of your feedback, this is not at all binary representation, because you split from the small end and not from the big end.

For binary representation to represent 7 you start with:

1. 8 no it's too big
2. 4, ok it fits, 7-4=3 left,
3. 2, ok it fits 3-2=1 left
4. 1, ok it fits 1-1=0 left, done!

What you are doing is splitting from the small end, so you will end up with a number $2^k-1 + b$, where $b$ is some remainder. I don't know if this has any name, but it sure is not a binary representation of the number.