question and answer thread.

I have an integer, could anyone tell me the number of operations I need to partition that number till it is a sum of all 1s
For example I have 5=4+1=2+2+1=2+1+1+1=1+1+1+1+1
I will get num(5)=4
:)
Thank you...

The way you're doing it seems to get just one new "+ 1" at each step. It means that you need N-1 steps.

num(N) = N - 1

I am sorry perhaps because my question mightnot be clear , you misundertood what I really want to ask...
When you partition the number, its parts must be a power of 2. Try again please...:)

Thanks...

I should point out at this stage that the question states 'any integer', and that can't be done, as negative integers can not be expressed as the sum of powers of positive numbers.

Also, I'm going to assume that when a number is initiately broken down, it is into the smallest number of powers of 2 possible, or else the answer is trivial (1 breakdown to turn everything into 1's).

For any power of two you break down, the total number of sub-breaks is equal to that number minus 1. Proof (sort of): 2 requires 1 break down, for each time you multiply this by two, you double the number of breakdowns and add 1, the initial breakdown. It looks kinda like a binary tree if you chart it.

For non-powers of two, the rules change a bit. You need the additional breakdown at the start which results in more than two powers of two created. The number of powers of two created is equal to the number of '1's in the binary representation of the number. Thus the total number of breakdowns is equal to the number of break downs for each power of 2, plus the initial break down. The number of additional breakdowns of all the powers created is equal to the sum of those powers (which is the original number) minus the number of powers created. Therefore:

num(N) = N + 1 - (number of '1's in binary representation of number)

so num(5) = 5 + 1 - 2 (there are two '1's in '101')

Unless there's a formula to determine the number of digits in a binary number based on it's decimal number other that just counting, that's pretty much it.

Sir, Could you tell me what made you think of using binary representation of that given number ? May I ask for that ? :)

Thank you....
Regards,

because of powers of 2 of course, forgive me for answering for him, but what else would someone do?

Yah, what Souldog said. Should I ask a question now?

Sure, go ahead.

Oh please not yet...:)
A.J.Gibson,
As what you have explained in your previous post, if my number is N there will be N' times that must be smaller than N to break down that N, is that right ?
Because what I have just been taught leads the result to something slightly different from that...Could you give me your answer ?...:)
Thanks...

P.S I am sorry just because I amnot really sure...

Quote:

---

Originally posted by hometown
As what you have explained in your previous post, if my number is N there will be N' times that must be smaller than N to break down that N, is that right ?
Because what I have just been taught leads the result to something slightly different from that...Could you give me your answer ?...:)
Thanks...

---

Are you saying my answer is wrong? If you looking for a solution that works with 0 or negative numbers, there isn't one, because you can't express a number less than 1 as the sum of positive numbers, and all powers of a positive number are positive.

Looking back at my answer, I see that I might not have been clear at one point: there are two formula's for the answer: num(N) = N-1 for powers of 2, and num(N) = N+1-(# of 1's in binary representation) for non-powers of 2. Is this what you meant? Or is one of my original assumptions wrong? I assumed the initial breakdown resulted in only powers of 2.

For example: say you're breaking down the number 23:
23
16+4+2+1 (this is the initial breakdown, the '+1')
8+8+4+2+1
8+4+4+4+2+1
4+4+4+4+4+2+1
4+4+4+4+2+2+2+1
4+4+4+2+2+2+2+2+1
4+4+2+2+2+2+2+2+2+1
4+2+2+2+2+2+2+2+2+2+1
2+2+2+2+2+2+2+2+2+2+2+1
2+2+2+2+2+2+2+2+2+2+1+1+1
2+2+2+2+2+2+2+2+2+1+1+1+1+1
2+2+2+2+2+2+2+2+1+1+1+1+1+1+1
2+2+2+2+2+2+2+1+1+1+1+1+1+1+1+1
2+2+2+2+2+2+1+1+1+1+1+1+1+1+1+1+1
2+2+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1
2+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

That's 20 breakdowns, which is 23 + 1 - 4, the 4 being the sum of how many powers of 2 that 23 is (at minimum), namely 16, 4, 2, and 1.

Does that help?

A.J.Gibson
Please donot get angry...I think it is not important for the answer to be correct or incorrect because there are always unexpected countless things in between, it was me who made such an unclear question. The main purpose I had when asking you again and again was nothing but just try to understand what you were really thinking when you gave me such an answer and more than that, I would like to find out why I couldnot get the answer that was the same as yours, which might partially upset you... Now I understood...Donot get angry at me hah ?:)
Your answer is absolutely correct...
What I have learnt,however, is different from the detailed result you offered and explained here...Because everytime I partition a number, I have only one choice, which means I am allowed to break only one number into its binary components at one time. Therefore, if I want to do that with another number that is next to the one I have just "devided", I will have to go back to its original position.
For example, in your case:
23
16 4 2 1
16 4 1 1 1
16 2 2 2 1
16 2 2 1 1 1
16 2 1 1 1 1 1
16 1 1 1 1 1 1 1
8 8 4 2 1 // Go back to the second position *
8 8 2 2 2 1
8 8 2 2 1 1 1
8 8 2 1 1 1 1 1
8 8 1 1 1 1 1 1 1
8 4 4 4 2 1// Go back to the postion *
.....
This is repeated until
2 2 2 2 2 2 2 2 2 2 2 1
2 2 2 2 2 2 2 2 2 2 1 1 1
2 2 2 2 2 2 2 2 2 1 1 1 1 1
......
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

So finally there are 74 steps to finish...
Finally, I have to say that I really like your explanation, it is natural in the way of reasoning, and... that really helps...

Thank you very much...:)

I'm not angry, hometown, I'm just confused. But now I've read your explanation, so I've moved on to bewildered :)

I'm going to ask a riddle now, because I think it's my turn. If it's not, ignore my riddle. My apologies if it's been done here already, I haven't read every single riddle here. Hope it's not to easy...I haven't been able to solve it, and I'll be kicking myself if it's something obvious.

Name a 10-digit number with 10 different digits such that taking any number of digits from the front of the number results in a number divisible by the number of digits. In other words, the first 2 digits form a 2 digit number divisible by 2. The first 7 digits form a 7 digit number divisible by 10. And so forth up to 10.

Quote:

---

Originally posted by A.J.Gibson
The first 7 digits form a 7 digit number divisible by 10.

---

shouldn't this be by 7?

1296547830 is a (the number) that does it

Quote:

---

Originally posted by Elrond
1296547830 is a (the number) that does it

---

why?