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

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.

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.

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.

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.

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

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.