Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
#1 2015-06-21 03:20:28
- phanthanhtom
- Member
- Registered: 2012-06-22
- Posts: 290
Write a positive integer as the sum of powers of 2
Original wording of question:
>Let f(n) be the number of ways to write n as a sum of powers of 2, where we keep track of the order of summation. For example, f(4) = 6 because 4 can be written as 4, 2+2, 2+1+1, 1+2+1, 1+1+2, and 1+1+1+1. Find the smallest n greater than 2013 for which f(n) is odd.
My conjecture is that f(n) is odd if and only if n = 2^k - 1 for some nonnegative integer k, but I haven't been able to prove it
I've found few similar problems on the Internet. The closest one is at http://mathlesstraveled.com/2008/04/18/challenge-12-sums-of-powers-of-two/ (problem 3). The only difference is that my problem does distiguish 2+1+1 and 1+2+1 for example.
P/S: My older post a year ago about 64 pawns have not been answered yet. Can you please solve that also?
Thanks a lot!
Offline
#2 2015-06-21 04:56:25
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
Let f(n) be the number of ways to write n as a sum of powers of 2, where we keep track of the order of summation. For example, f(4) = 6 because 4 can be written as 4, 2+2, 2+1+1, 1+2+1, 1+1+2, and 1+1+1+1. Find the smallest n greater than 2013 for which f(n) is odd.
This is a computational problem and thusly can be solved by EM. The proof to your conjecture may or may not be possible.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#3 2015-06-21 05:06:54
- phanthanhtom
- Member
- Registered: 2012-06-22
- Posts: 290
Re: Write a positive integer as the sum of powers of 2
By EM? What does that mean? (I haven't been following English math forums for a while)
Is it possible to solve it solely with arithmetic and algebra, and without the use of computers? (so you can't just calculate f(n) for every number and then look at it)
Offline
#4 2015-06-21 05:11:03
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
That is the point...Solve what? The computational question or the proof?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#5 2015-06-21 11:42:54
- phanthanhtom
- Member
- Registered: 2012-06-22
- Posts: 290
Re: Write a positive integer as the sum of powers of 2
Find the proof. We aren't allow to compute all the values, as we are not allowed to have computers.
Offline
#6 2015-06-21 15:16:26
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
Why do you think the conjecture is true?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#7 2015-06-21 21:21:26
- phanthanhtom
- Member
- Registered: 2012-06-22
- Posts: 290
Re: Write a positive integer as the sum of powers of 2
Because I computed the values of f(n) for n = 1 to 10: only 1, 3 and 7 had f(n) odd. Also, I had this same f(n) a month ago, when I saw a problem about calculating f(15) - I think it was odd.
Offline
#8 2015-06-21 21:47:53
- phanthanhtom
- Member
- Registered: 2012-06-22
- Posts: 290
Re: Write a positive integer as the sum of powers of 2
For reference, the first 8 values of f(n) I calculated by hand are: 1, 2, 3, 6, 10, 18, 31, 56...
I looked it up on OEIS. The sequence is available on OEIS as "Number of compositions (ordered partitions) of n into powers of 2" - exactly what I need. (They start with 0) A023359
They do have f(15) = 2983 and f(31) = 26805983, furthering my conjecture.
I don't quite grasp the formula section though. Can you please elaborate?
Offline
#9 2015-06-22 02:00:56
Re: Write a positive integer as the sum of powers of 2
The answer is 2047 (verified by computation)
Those formulae are gf's. It can help you prove your conjecture, though.
Can you give me the permission to post this problem on a different forum?
Last edited by Agnishom (2015-06-22 02:26:15)
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#10 2015-06-22 03:13:36
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
Hi Agnishom;
That is correct.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#11 2015-06-22 03:17:36
Re: Write a positive integer as the sum of powers of 2
The conjecture should be correct too.
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#12 2015-06-22 03:22:25
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
I do not agree. It may be and maybe not.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#13 2015-06-22 03:23:28
Re: Write a positive integer as the sum of powers of 2
Did you try proving/disproving it?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#14 2015-06-22 03:25:24
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
Of course not!
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#15 2015-06-22 04:41:48
Re: Write a positive integer as the sum of powers of 2
You should have.
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#16 2015-06-22 04:45:57
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
I never try to prove anything that does not have millions of examples. The computational question was more interesting,
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#17 2015-06-22 04:49:39
Re: Write a positive integer as the sum of powers of 2
Who said proving something cannot be a computational job?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#18 2015-06-22 04:51:35
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
Do you see any closed form over there? What does that tell you?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#19 2015-06-22 04:56:00
Re: Write a positive integer as the sum of powers of 2
Not every function has a closed form. Why'd you always expect one?
The reason is simple: There are an uncountably infinite number of functions but only a countably infinite number of strings that you can create with your language.
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#20 2015-06-22 05:15:32
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
That is not what I meant.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#21 2015-06-22 05:29:28
Re: Write a positive integer as the sum of powers of 2
I know but I am willing to say that the conjecture is true and the proof is not that hard.
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#22 2015-06-22 05:29:58
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
Then how come no one over there has it?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#23 2015-06-22 06:28:15
Re: Write a positive integer as the sum of powers of 2
Over OEIS? Why should they care if some values are even?
Calvin gave me a proof
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#24 2015-06-22 06:29:42
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Write a positive integer as the sum of powers of 2
That is very good! When will you post the computational problem, I need more points...
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#25 2015-06-22 07:06:01
Re: Write a positive integer as the sum of powers of 2
What kind of points?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline