3
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ How is $3$ a power of $2$? Or $489$? You could write $10=2+8$ and $1000=512+256+128+64+32+8$, these are the binary representations of the numbers. $\endgroup$ – Servaes Aug 17 '18 at 12:16
  • 6
    $\begingroup$ @ng.newbie No, I don't get it. Why would you use $10=1+2+\color{red}3\color{black}+4$ instead of $10=2+8$ $\endgroup$ – Don Thousand Aug 17 '18 at 12:24
  • 5
    $\begingroup$ This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary. $\endgroup$ – lulu Aug 17 '18 at 12:27
  • 5
    $\begingroup$ I think you guys are missing that it’s increasing powers of $2$. So you go $1+2+4+8+...$ until the next power of 2 is too large. $\endgroup$ – Stella Biderman Aug 17 '18 at 12:29
  • 6
    $\begingroup$ Do we call this "binary"? $\endgroup$ – Joshua Aug 17 '18 at 18:38
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You seem to have an off-by-one error. $1+2=4-1$ $\endgroup$ – Stella Biderman Aug 17 '18 at 12:41
  • $\begingroup$ @StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+\cdots +2^{k-1}=2^k-1$, not $2^k$. $\endgroup$ – lulu Aug 17 '18 at 12:57
  • $\begingroup$ @lulu No, I don't quite understand it yet. Why can't I form all numbers from an expansion of the powers of $3$ or $4$ or $5$ or any other number? The power of $1$ and $2$ are the only ones that have this property. That was my question. Is this the correct place or clarify it or should I post a different thread? $\endgroup$ – ng.newbie Aug 20 '18 at 8:01
  • $\begingroup$ @lulu When you say "so you can get every natural number $<2^k$ as a partial sum of those terms (using the binary expansion)" I dont understand what you mean by this. What exactly is binary expansion? $\endgroup$ – ng.newbie Aug 20 '18 at 8:02
  • $\begingroup$ "Binary Expansion", just refers to writing integers in base $2$. See, e.g., this for a standard write up. You only need the digits $0$ and $1$, so any integer can be written as a sum of distinct terms in $\{1,2,2^2,2^3,\cdots\}$. You can write every integer in base $3$ or $5$ but you need digits other than $0$ and $1$. That means you can't write every integer as a sum of distinct terms in $\{1,3,3^2,\cdots\}$. $\endgroup$ – lulu Aug 20 '18 at 9:44
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The last power of two in the last equality should be $1024$, not $2048$. $\endgroup$ – Adayah Aug 17 '18 at 14:58
4
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ But the issue is that his expansion is not exactly binary, e.g. $10=1+2+\color{red}3\color{black}+4$ $\endgroup$ – Don Thousand Aug 17 '18 at 12:25
  • $\begingroup$ -1 The comments make clear that this is not what the asker is after. $\endgroup$ – Servaes Aug 17 '18 at 12:25
  • $\begingroup$ @Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain. $\endgroup$ – Arnaud Mortier Aug 17 '18 at 12:31
  • $\begingroup$ @ArnaudMortier Wonder why this got a downvote $\endgroup$ – ng.newbie Aug 17 '18 at 12:33
  • $\begingroup$ @ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable. $\endgroup$ – Arnaud Mortier Aug 17 '18 at 12:39
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It really comes down to the flexibility of the remainder +1. $\endgroup$ – Don Thousand Aug 17 '18 at 12:30
  • $\begingroup$ @Servaes Got this method when I was reading about the bounded knapsack problem being turned into a 0/1 Knapsack problem. It was from this paper. $\endgroup$ – ng.newbie Aug 17 '18 at 12:33
  • $\begingroup$ Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required. $\endgroup$ – Stella Biderman Aug 17 '18 at 12:33
  • $\begingroup$ @StellaBiderman Yes I need more explanation. More than I want to know how I can combine it to make any number less than or equal to that number I am breaking. $\endgroup$ – ng.newbie Aug 17 '18 at 12:34
  • $\begingroup$ @StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment. $\endgroup$ – Servaes Aug 17 '18 at 12:34
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is essentially a copy of my answer. In fact, I don't think that you have read the other answers at all, because none of them assumes that the OP was talking about binary representation. $\endgroup$ – Arnaud Mortier Aug 18 '18 at 9:15
  • $\begingroup$ @ArnaudMortier it turns out you are right. I wrote answer early, but then lost internet connection for like 8 hours and then when I posted apparently several other answers had come in. $\endgroup$ – mathreadler Aug 18 '18 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.