Question

\[331 = x_0 + 2x_1 + 4x_2 + \color{red}{8x_3}+16x_4 + 32x_5 + 64x_6 + 128x_7 + 256x_8\]

where \(x_i = 0 ~or~1\)
Find a solution if it exists

\(\color{Red}{EDIT} : \text{updated the missing term, thanks to Unkle} :)\)

Answer 1

oh gee

Answer 2

seems you know how to solve this problem :)

Answer 3

wait cant you just add these like terms first

Answer 4

the solve backwards

Answer 5

then*

Answer 6

this looks like 2 solutions because..

Answer 7

wait am i solving this or are you putting this out there and you already know the answer.

Answer 8

What like terms are there?

Answer 9

the x

Answer 10

I think those are different variables

Answer 11

add each variable(like terms) and then divide by non like terms

Answer 12

i think its two solutions

Answer 13

yes let me update the question :)

Answer 14

ok

Answer 15

Why write x_1 and x_2 and so on? I was thinking each subscript denoted a different variable

Answer 16

yes each subscript denotes a different variable

Answer 17

in this case am i using 0 or 1? does it matter.

Answer 18

The answer lies within your heart.

Answer 19

haha i think i need to give an example to make the problem more clear :

Example : \(5 = x_1 + 2x_2 + 4x_3\)
the solution is \(x_1 = 1,~x_2 = 0,~x_3 = 1\) because \(1 + 2(0) + 4(1) = 5\)

Answer 20

Ohhh I get it now

Answer 21

oh i was just reading this .. http://arxiv-web3.library.cornell.edu/pdf/1110.6620v3.pdf

Answer 22

its something similar

Answer 23

except more broad

Answer 24

did you miss 8 ?

Answer 25

The LHS is odd, so we must have \(x_1 = 1\).
The remaining number is \(330\), and we have to check if we can express it in terms of the sum of powers of two.
And there must be a 256 - otherwise our sum wouldn't be able to reach 330.

The remaining sum is 74. It has come down to expressing 74 as a sum of powers of two. And we can certainly achieve that! \(74 = 64 + 8 + 2\).

Therefore, \(331 = 1 + 2 + 8 + 64 + 256\). The other terms are zero.

Answer 26

**assuming that there is an 8 in the sum, that is.

Answer 27

If there is not an 8 in the sum, then we can claim that it is in fact impossible to find a solution, because I can't see any other way to express 74 as the sum of powers of two.

Answer 28

Sorry yes I did miss the 8 :/
PK looks good :)

Answer 29

So it is a unique solution, yes?

Answer 30

\[\sum_{i=0}^82^ix_i=\begin{bmatrix}2^0&2^1&2^2&2^3&2^4&2^5&2^6&2^7&2^8\end{bmatrix}\begin{bmatrix}x_0\\x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x^7\\x_8\end{bmatrix}\]

Answer 31

that looks more like "binary number system" now XD

Answer 32

indeed

Answer 33

so the answer to PK's question should be
yes there is an one-to-one mapping because each decimal number has an unique binary representation and each binary number has an unique decimal representation

Answer 34

Ohhhh, I didn't think of it that way. Yeah.

Answer 35

Actually it can be shown easily that every super increasing series has an unique solution :

\[N = a_0x_0 + a_1x_1 + a_2x_2 + \cdots + a_{n-1}x_{n-1}+a_nx_n \]

if exists, there exists an unique solution provided \(a_i \gt a_0+a_1+\cdots + a_{i-1}\)

Answer 36

A simle example of superincreasing sequence is \(\{1,~2, ~4, ~8,~\ldots~, 2^n\}\) where \(2^i \gt 2^{i}-1 = 1+2+4+\cdots + 2^{i-1}\)

Answer 37

That's cool. What does \(\{ x_n \}\) signify? Ones and zeroes?

Answer 38

yes missed that detail :
\(x_i = 0/1\)

Answer 39

there are pretty interesting problems based on this unique solution criterion
http://en.wikipedia.org/wiki/Superincreasing_sequence

Answer 40

That is an interesting fact. I haven't studied number theory or whatever field this is, so I'm wondering how we can even prove this.

Answer 41

Can we separate the "power" terms from the general term so as to prove it for general super-sequences?

Answer 42

Proving is a bit theoretic.. so its not so interesting ;) but there is an amaging application of this property : it allows two people to communicate securely in a not so safe medium.

For example, using that property a bunch of people can communicate by writing letters to each other through postal service without worrying about compromising the security

Answer 43

this is like asking find the binary of 331

Answer 44

Yes exactly !

Answer 45

I was talking about below encryption algorithm
http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem

but its really easy, idk why wiki is trying hard to make it complicated

Answer 46

you could prove the general case for \(n\) with induction,

Answer 47

Induction works pretty neatly. The textbook i am refering to has this proof/general solution which can be a bit enlightnenign :
\[N = a_0x_0 + a_1x_1 + a_2x_2 + \cdots + a_{n-1}x_{n-1}+a_nx_n\]
Assuming there exists a solution to above, the solution is given by
\[x_i = \left\{\begin{array}{}1& \text{if }N-(a_{i+1}x_{i-1}+\cdots+a_nx_n)\ge
a_i\\
0& \text{if }N-(a_{i+1}x_{i-1}+\cdots+a_nx_n)\lt
a_i\\

\end{array}\right.\]

Answer 48

So just a question, doesn't this whole thing just depend on if x_0=1?

Answer 49

I think so... \(x_0 = 0/1\) depending on \(N\) being even or odd... it was stated by PK earlier..

Answer 50

whats a good way to see the highest power of 2 that can go into your number

Answer 51

whats the function for log?

Answer 52

is there a better way can to floor log function

Answer 53

than * to

Answer 54

But it has to equal 1

Answer 55

Oh right we need to work the highest power that goes into N as the solution is wokring from right hand side

Answer 56

It's also a prime factorization

Answer 57

yeah

Answer 58

question is, does 330 have a prime factorization that only contains twos?

Answer 59

because 256 < 330 < 512, we pick \(x_8 = 1\) and \(x_9=0\)

Answer 60

I feel you are overcomplicating it

Answer 61

yeah that how u wud go about generating binary numbers fast

Answer 62

there might be a more efficient way

Answer 63

I am just working the step given in proof above

Answer 64

decimal to binary conversion ?

Answer 65

yaa

Answer 66

oh, For this particular problem I would just do a prime factorization on 330, realize it's not all twos then disprove possibility of a solution

Answer 67

it's like a 4-5 step disprove

Answer 68

all numbers below 512 are possible though

Answer 69

oh, I'm thinking of straight multiplication, not the addition

Answer 70

dang

Answer 71

its just the decimal way of writing out binary numbers so, everything below the next highest power of 2 is possible

Answer 72

using 9 bits we can represent number between 0 and 2^9-1

Answer 73

2 = (10)_2
2^2 = (100)_2
2^3 = (1000)_2
...

like this ? this is efficient for computer to work..
but still it wont tell us 2^n = what in decimal form right ?

Answer 74

yea yea I see where I misinterpreted

Answer 75

you can type up an algorithm

Answer 76

yee lets goo

Answer 77

basically convert the base to binary and left shift to increase the exponent

Answer 78

yea

Answer 79

or google haha
101001011

Answer 80

wolfram is also cool
http://www.wolframalpha.com/input/?i=331+to+binary

Answer 81

So your problem has no solution. The solution requires an x_9

Answer 82

hey is there a way to do log base 2 stuff with only lns

Answer 83

uhm, you would have to do a conversion. So convert all log base twos into ln.

Answer 84

you're trying to work below efficiently ?
\[2^? = N\]

Answer 85

ya i wanna do
floor(log_2_(N))
but matlab only allows Ln

Answer 86

we can use change of base as fib said right ?

log_2 (N) = ln(N)/ln(2)

Answer 87

you remember how in calc to do other logs we used the change of base formula?

Answer 88

That would be how I'd approach it at least

Answer 89

why does that give u change of base again

Answer 90

@Jhannybean hii

Answer 91

haha I never proved it. But it does

Answer 92

hahaha

Answer 93

i remember doing it on here a while ago

Answer 94

@ganeshie8 heyyyyy . Heading off OS for a while again. See you guys soon :)

Answer 95

Hey Jhanny!!!! Nice to see ya again, have fun!