Mixing
Does this mathematical technique have a formal name? And why does it work?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
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?
sequences-and-series power-series problem-solving
asked Aug 17 at 12:15
ng.newbie
1998
 |Â
show 18 more comments
up vote
3
down vote
favorite
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?
sequences-and-series power-series problem-solving
asked Aug 17 at 12:15
ng.newbie
1998
5
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.
– Servaes
Aug 17 at 12:16
6
@ng.newbie No, I don't get it. Why would you use $10=1+2+colorred3colorblack+4$ instead of $10=2+8$
– Rushabh Mehta
Aug 17 at 12:24
5
This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary.
– lulu
Aug 17 at 12:27
5
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.
– Stella Biderman
Aug 17 at 12:29
6
Do we call this "binary"?
– Joshua
Aug 17 at 18:38
 |Â
show 18 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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?
sequences-and-series power-series problem-solving
asked Aug 17 at 12:15
ng.newbie
1998
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?
sequences-and-series power-series problem-solving
asked Aug 17 at 12:15
ng.newbie
1998
edited Aug 17 at 12:27
asked Aug 17 at 12:15
ng.newbie
1998
asked Aug 17 at 12:15
ng.newbie
1998
asked Aug 17 at 12:15
ng.newbie
1998
1998
5
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.
– Servaes
Aug 17 at 12:16
6
@ng.newbie No, I don't get it. Why would you use $10=1+2+colorred3colorblack+4$ instead of $10=2+8$
– Rushabh Mehta
Aug 17 at 12:24
5
This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary.
– lulu
Aug 17 at 12:27
5
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.
– Stella Biderman
Aug 17 at 12:29
6
Do we call this "binary"?
– Joshua
Aug 17 at 18:38
 |Â
show 18 more comments
5
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.
– Servaes
Aug 17 at 12:16
6
@ng.newbie No, I don't get it. Why would you use $10=1+2+colorred3colorblack+4$ instead of $10=2+8$
– Rushabh Mehta
Aug 17 at 12:24
5
This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary.
– lulu
Aug 17 at 12:27
5
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.
– Stella Biderman
Aug 17 at 12:29
6
Do we call this "binary"?
– Joshua
Aug 17 at 18:38
5
5
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.
– Servaes
Aug 17 at 12:16
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.
– Servaes
Aug 17 at 12:16
6
6
@ng.newbie No, I don't get it. Why would you use $10=1+2+colorred3colorblack+4$ instead of $10=2+8$
– Rushabh Mehta
Aug 17 at 12:24
@ng.newbie No, I don't get it. Why would you use $10=1+2+colorred3colorblack+4$ instead of $10=2+8$
– Rushabh Mehta
Aug 17 at 12:24
5
5
This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary.
– lulu
Aug 17 at 12:27
This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary.
– lulu
Aug 17 at 12:27
5
5
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.
– Stella Biderman
Aug 17 at 12:29
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.
– Stella Biderman
Aug 17 at 12:29
6
6
Do we call this "binary"?
– Joshua
Aug 17 at 18:38
Do we call this "binary"?
– Joshua
Aug 17 at 18:38
 |Â
show 18 more comments
5 Answers
5
active
oldest
votes
up vote
10
down vote
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.
answered Aug 17 at 12:37
lulu
36.2k14275
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:02
"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$.
– lulu
Aug 20 at 9:44
 |Â
show 3 more comments
up vote
6
down vote
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 + colorred489$$
$$1000 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + colorred489$$
is the same thing as saying $$1000 = (512-1)+colorred489$$
$$1000 = (2^9-1)+colorred489$$
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 + colorred298$$
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.
answered Aug 17 at 12:51
steven gregory
16.7k22155
1
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
add a comment |Â
up vote
4
down vote
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=xcdot x^2cdot x^4$$
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
add a comment |Â
up vote
2
down vote
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.
answered Aug 17 at 12:28
Servaes
1
1
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
@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.
– ng.newbie
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
add a comment |Â
up vote
0
down vote
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:
- 8 no it's too big
- 4, ok it fits, 7-4=3 left,
- 2, ok it fits 3-2=1 left
- 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.
answered Aug 17 at 20:44
mathreadler
13.8k71957
1
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.
– Arnaud Mortier
Aug 18 at 9:15
@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.
– mathreadler
Aug 18 at 14:06
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
10
down vote
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.
answered Aug 17 at 12:37
lulu
36.2k14275
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:02
"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$.
– lulu
Aug 20 at 9:44
 |Â
show 3 more comments
up vote
10
down vote
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.
answered Aug 17 at 12:37
lulu
36.2k14275
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:02
"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$.
– lulu
Aug 20 at 9:44
 |Â
show 3 more comments
up vote
10
down vote
up vote
10
down vote
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.
answered Aug 17 at 12:37
lulu
36.2k14275
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.
answered Aug 17 at 12:37
lulu
36.2k14275
edited Aug 17 at 12:56
answered Aug 17 at 12:37
lulu
36.2k14275
answered Aug 17 at 12:37
lulu
36.2k14275
answered Aug 17 at 12:37
lulu
36.2k14275
36.2k14275
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:02
"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$.
– lulu
Aug 20 at 9:44
 |Â
show 3 more comments
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:02
"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$.
– lulu
Aug 20 at 9:44
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
You seem to have an off-by-one error. $1+2=4-1$
– Stella Biderman
Aug 17 at 12:41
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@StellaBiderman Yes, thanks. I specialize in those. Here the blunder was that $1+2+cdots +2^k-1=2^k-1$, not $2^k$.
– lulu
Aug 17 at 12:57
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:01
@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?
– ng.newbie
Aug 20 at 8:02
@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?
– ng.newbie
Aug 20 at 8:02
"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$.
– lulu
Aug 20 at 9:44
"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$.
– lulu
Aug 20 at 9:44
 |Â
show 3 more comments
up vote
6
down vote
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 + colorred489$$
$$1000 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + colorred489$$
is the same thing as saying $$1000 = (512-1)+colorred489$$
$$1000 = (2^9-1)+colorred489$$
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 + colorred298$$
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.
answered Aug 17 at 12:51
steven gregory
16.7k22155
1
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
add a comment |Â
up vote
6
down vote
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 + colorred489$$
$$1000 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + colorred489$$
is the same thing as saying $$1000 = (512-1)+colorred489$$
$$1000 = (2^9-1)+colorred489$$
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 + colorred298$$
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.
answered Aug 17 at 12:51
steven gregory
16.7k22155
1
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
add a comment |Â
up vote
6
down vote
up vote
6
down vote
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 + colorred489$$
$$1000 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + colorred489$$
is the same thing as saying $$1000 = (512-1)+colorred489$$
$$1000 = (2^9-1)+colorred489$$
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 + colorred298$$
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.
answered Aug 17 at 12:51
steven gregory
16.7k22155
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 + colorred489$$
$$1000 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + colorred489$$
is the same thing as saying $$1000 = (512-1)+colorred489$$
$$1000 = (2^9-1)+colorred489$$
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 + colorred298$$
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.
answered Aug 17 at 12:51
steven gregory
16.7k22155
answered Aug 17 at 12:51
steven gregory
16.7k22155
answered Aug 17 at 12:51
steven gregory
16.7k22155
answered Aug 17 at 12:51
steven gregory
16.7k22155
16.7k22155
1
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
add a comment |Â
1
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
1
1
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
The last power of two in the last equality should be $1024$, not $2048$.
– Adayah
Aug 17 at 14:58
add a comment |Â
up vote
4
down vote
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=xcdot x^2cdot x^4$$
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
add a comment |Â
up vote
4
down vote
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=xcdot x^2cdot x^4$$
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
add a comment |Â
up vote
4
down vote
up vote
4
down vote
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=xcdot x^2cdot x^4$$
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
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=xcdot x^2cdot x^4$$
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
edited Aug 17 at 12:34
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
answered Aug 17 at 12:22
Arnaud Mortier
19.6k22159
19.6k22159
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
add a comment |Â
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
But the issue is that his expansion is not exactly binary, e.g. $10=1+2+colorred3colorblack+4$
– Rushabh Mehta
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
-1 The comments make clear that this is not what the asker is after.
– Servaes
Aug 17 at 12:25
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@Servaes Possibly. I edited to explain the difference between the OP and this answer, because it is quite straightforward to explain.
– Arnaud Mortier
Aug 17 at 12:31
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ArnaudMortier Wonder why this got a downvote
– ng.newbie
Aug 17 at 12:33
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
@ng.newbie Thanks. Servaes explained that I was not really answering the question. I guess it's debatable.
– Arnaud Mortier
Aug 17 at 12:39
add a comment |Â
up vote
2
down vote
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.
answered Aug 17 at 12:28
Servaes
1
1
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
@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.
– ng.newbie
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
add a comment |Â
up vote
2
down vote
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.
answered Aug 17 at 12:28
Servaes
1
1
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
@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.
– ng.newbie
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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.
answered Aug 17 at 12:28
Servaes
1
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.
answered Aug 17 at 12:28
Servaes
1
answered Aug 17 at 12:28
Servaes
1
answered Aug 17 at 12:28
Servaes
1
answered Aug 17 at 12:28
Servaes
1
1
1
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
@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.
– ng.newbie
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
add a comment |Â
1
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
@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.
– ng.newbie
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
1
1
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
It really comes down to the flexibility of the remainder +1.
– Rushabh Mehta
Aug 17 at 12:30
@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.
– ng.newbie
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
Since it is clearly not obvious to the OP why this occurs, I think more of an explanation is required.
– Stella Biderman
Aug 17 at 12:33
@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.
– ng.newbie
Aug 17 at 12:34
@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.
– ng.newbie
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
@StellaBiderman Feel free to give one; I can't be bothered to explain why division with remainder is well-defined at the moment.
– Servaes
Aug 17 at 12:34
add a comment |Â
up vote
0
down vote
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:
- 8 no it's too big
- 4, ok it fits, 7-4=3 left,
- 2, ok it fits 3-2=1 left
- 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.
answered Aug 17 at 20:44
mathreadler
13.8k71957
1
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.
– Arnaud Mortier
Aug 18 at 9:15
@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.
– mathreadler
Aug 18 at 14:06
add a comment |Â
up vote
0
down vote
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:
- 8 no it's too big
- 4, ok it fits, 7-4=3 left,
- 2, ok it fits 3-2=1 left
- 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.
answered Aug 17 at 20:44
mathreadler
13.8k71957
1
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.
– Arnaud Mortier
Aug 18 at 9:15
@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.
– mathreadler
Aug 18 at 14:06
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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:
- 8 no it's too big
- 4, ok it fits, 7-4=3 left,
- 2, ok it fits 3-2=1 left
- 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.
answered Aug 17 at 20:44
mathreadler
13.8k71957
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:
- 8 no it's too big
- 4, ok it fits, 7-4=3 left,
- 2, ok it fits 3-2=1 left
- 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.
answered Aug 17 at 20:44
mathreadler
13.8k71957
answered Aug 17 at 20:44
mathreadler
13.8k71957
answered Aug 17 at 20:44
mathreadler
13.8k71957
answered Aug 17 at 20:44
mathreadler
13.8k71957
13.8k71957
1
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.
– Arnaud Mortier
Aug 18 at 9:15
@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.
– mathreadler
Aug 18 at 14:06
add a comment |Â
1
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.
– Arnaud Mortier
Aug 18 at 9:15
@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.
– mathreadler
Aug 18 at 14:06
1
1
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.
– Arnaud Mortier
Aug 18 at 9:15
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.
– Arnaud Mortier
Aug 18 at 9:15
@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.
– mathreadler
Aug 18 at 14:06
@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.
– mathreadler
Aug 18 at 14:06
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2885700%2fdoes-this-mathematical-technique-have-a-formal-name-and-why-does-it-work%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
5
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.
– Servaes
Aug 17 at 12:16
6
@ng.newbie No, I don't get it. Why would you use $10=1+2+colorred3colorblack+4$ instead of $10=2+8$
– Rushabh Mehta
Aug 17 at 12:24
5
This is hard to follow. Why is $5=(1,2,2)$ instead of $(1,4)$? The rules seem arbitrary.
– lulu
Aug 17 at 12:27
5
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.
– Stella Biderman
Aug 17 at 12:29
6
Do we call this "binary"?
– Joshua
Aug 17 at 18:38