Two Plus Two Newer Archives  

Go Back   Two Plus Two Newer Archives > Other Topics > Science, Math, and Philosophy

Reply
 
Thread Tools Display Modes
  #1  
Old 08-05-2007, 04:26 AM
pzhon pzhon is offline
Senior Member
 
Join Date: Mar 2004
Posts: 4,515
Default 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
Reply With Quote
  #2  
Old 08-05-2007, 11:01 AM
gumpzilla gumpzilla is offline
Senior Member
 
Join Date: Feb 2005
Posts: 7,911
Default 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.
Reply With Quote
  #3  
Old 08-05-2007, 02:25 PM
bigpooch bigpooch is offline
Senior Member
 
Join Date: Sep 2003
Location: Hong Kong
Posts: 1,330
Default 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.
Reply With Quote
  #4  
Old 08-05-2007, 02:55 PM
gumpzilla gumpzilla is offline
Senior Member
 
Join Date: Feb 2005
Posts: 7,911
Default 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.
Reply With Quote
  #5  
Old 08-05-2007, 03:42 PM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default 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.
Reply With Quote
  #6  
Old 08-05-2007, 03:43 PM
blah_blah blah_blah is offline
Senior Member
 
Join Date: Feb 2007
Posts: 378
Default 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
Reply With Quote
  #7  
Old 08-05-2007, 05:40 PM
pzhon pzhon is offline
Senior Member
 
Join Date: Mar 2004
Posts: 4,515
Default 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.
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 07:36 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.