#1
|
|||
|
|||
IBM Ponder This August 2007
I thought this month's IBM Ponder This challenge was interesting.
<ul type="square"> Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice. For example, f(10)=5 since there are five different ways to express 10: 1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8. Describe, in a single sentence, the sequence {f(n)/f(n-1)} for positive integer n. Show your proof to this sentence.[/list] I believe in this problem, {n} means floor(n), the greatest integer less than or equal to n. Here are the first few values of f(n), obtained by multiplying a(x)a(x^2)a(x^4)... where a(x) = (1+x+x^2): 0: 1 1: 1 2: 2 3: 1 4: 3 5: 2 6: 3 7: 1 8: 4 9: 3 10: 5 11: 2 12: 5 13: 3 14: 4 15: 1 16: 5 17: 4 18: 7 19: 3 20: 8 21: 5 22: 7 23: 2 24: 7 25: 5 |
#2
|
|||
|
|||
Re: IBM Ponder This August 2007
Well, it looks to me like the sentence that describes that sequence is (in white for those who don't want to be spoiled): <font color="white"> {f(1) / f(0)} = 1, and for all other n, {f(n) / f(n-1)} is equal to the greatest power of 2 that divides f(n).</font>
Having looked at the first 20 or so values I'm pretty confident that's right, but I haven't an idea about the proof yet. I'll think about that for a while. |
#3
|
|||
|
|||
Re: IBM Ponder This August 2007
No, I don't think {f(n)/f(n-1)} as stated in the question
is the floor, for then the result isn't as interesting! Hint: <font color="white"> Look at the sequence of fractions j/k starting with f(1)/f(0), f(2)/f(1), etc. </font> I haven't yet found an "elegant" proof. |
#4
|
|||
|
|||
Re: IBM Ponder This August 2007
Whoa, that's pretty crazy. Just a guess here, but is the property of the sequence that you're observing (in white) <font color="white">that all rational numbers appear exactly once in lowest terms? </font>
Wow, not even sure how I'd start to prove that. With the floor I at least had some ideas going. |
#5
|
|||
|
|||
Re: IBM Ponder This August 2007
[ QUOTE ]
Whoa, that's pretty crazy. Just a guess here, but is the property of the sequence that you're observing (in white) <font color="white">that all rational numbers appear exactly once in lowest terms? </font> Wow, not even sure how I'd start to prove that. With the floor I at least had some ideas going. [/ QUOTE ] nice observation. this is the content of a talk I attended given by Herb Wilf a couple of months ago. it should be well documented in the mathematical literature. |
#6
|
|||
|
|||
Re: IBM Ponder This August 2007
for more information look at section 3 of the following article
http://www.math.upenn.edu/%7Ewilf/we...talScience.pdf |
#7
|
|||
|
|||
Re: IBM Ponder This August 2007
[ QUOTE ]
No, I don't think {f(n)/f(n-1)} as stated in the question is the floor, for then the result isn't as interesting! [/ QUOTE ] My mistake, then. I thought the pattern of floor(f(n)/f(n-1)) was interesting enough for one of these challenges, and there is a simple proof of that pattern, but determining the actual sequence is definitely better. |
|
|