/sci/ - Science & Math

>>10526203
You can easily deduce that you actually need to see if you can describe 2018 as a sum of powers, but just give me a hot minute

>>10526203
probably an np hard problem but seems like you can zero in on it pretty quickly

(-2)^12 + (-2)^11 = 2048
so only need to find a way to get -29

>>10526249
ok, (-2)^12 + (-2)^11 + (-2)^5 + (-2)^2 + (-2)^1 + (-2)^0

it's the "subset-sum" problem, but iirc there's an efficient algorithm for this case where the magnitude of each successive number is superincreasing

>>10526203
also, i think the thrust of this exercise is not to provide a method (which seems extraordinarily complicated), but to prove that it can be done.
at first glance we have the fact you can get 1, 2, 3 and -1, -2, -3, and you can produce higher numbers by adding and subtracting smaller numbers. so there's probably some inductive proof you can present. seems very interesting but it's late, so...

>>10526203
it's called writing in binary you dumbfuck.

Every number can be written using powers of 2 at most once

>>10526319
Kill yourself, you retarded nigger

>>10526315
I managed to get an answer that I don't have on me right now, but it seemed like any method and any literature I looked up was overly complicated for what is a high school math education course

>>10526264
Ty, I'll have a look at the subset sum problem and see what I can pull from it. I know I don't have to write heaps on it but it sounds interesting


>>10526319
I feel like a retard, I remember a lecturer mentioning that now. That's a great lead on what to write about

>>10526319
>not reading the question

>>10526203
(-2)^[log_(-2) 2019]

>>10526203
Isn't this the negabinary representation or am i a turbo brainlet?

[eqn]\left(-2\right)^0+\left(-2\right)+\left(-2\right)^2+\left(-2\right)^5+\left(-2\right)^{11}+\left(-2\right)^{12}=2019[/eqn]

>>10526319
What part of -2 don't you understand?

It is not a simple matter of binary.

>>10526386
Every integer has a finite negabinary representation so he was right for the wrong reasons.

>>10526363
Effectively he's asking how to write any number in negabinary without having to guess.

The solution OP is looking for is a step by step guaranteed process to arrive at the answer

See https://en.wikipedia.org/wiki/Negative_base#Calculation for the easiest method. Works for any base

>>10526363
How did you guess that? Now generalize to any integer n. Is your solution tractable?

>>10526401
IS IT TELEKINETICS. MAYBE SO.

>>10526401
you moron
read >>10526396
it's literally just repeated >>10526406
division and listing remainders at each step from right to left

>>10526410
wow i really fucked up that formatting
meant to say at the end "if you can't understand it, it's basically just >>10526406"

I have a general solution for any N. A bit rough around the edges but it works.

2019 = 11111100011

You know the set of -2^x with even x will be positive, and the set of -2^x with odd x will be negative, so you need to setup a binary subtract, with that as the result. Top row (positive row) can only have 1s in the even indicies, bottom row only have 1s in the odd indicies

1000000000001
-100000100010
---------------------
11111100011

spacing is fucked up because of the font, but that should be clear enough. You can start by knowing that you need -2^12 on the top line because you need a positive number larger than 2019, and (-2)^11 is negative. You also know you need an odd number so you can set the 0 index to 1. From there you can just infer which bits need to be on or off if you work left to right doing a binary subtraction. The only tricky one is knowing to set (-2)^5 on, but you know you need 5 more 1s to the left of that position, so you can figure out you need (-2)^11 and (-2)^12 to make it work out.

Cool, I would never have thought about the idea of negative bases without this thread.

>>10526396
wtfff https://en.wikipedia.org/wiki/Quater-imaginary_base

>>10526432
>left to right
oops. I meant left to right

>>10526432
>left to right
sorry, meant right to left

>>10526203
Are you retarded?

(-2)^[log_(-2) 2019]

>>10526396
thanks for this anon