
#1
Feb1413, 02:05 PM

P: 4

Hi, I'm new here and, as will become obvious from my question, neither a phycisist nor a mathematician. This is not a homework question, so I post it in this forum and hope that's okay. (I've aready asked on stack exchange but as far as I can see the answers given to me there were describing a different sequence.)
I need to find a nonrecursive formula for determining the members of the sequence that starts as follows: [itex]a_1=0,\; a_2=\frac{1}{2},\; a_3=\frac{1}{4},\; a_4=\frac{3}{4},\; a_5=\frac{1}{8},\; a_6=\frac{3}{8},\; a_7=\frac{5}{8},\; a_8=\frac{7}{8},\; a_9=\frac{1}{16}, ...[/itex] Imagine a line that is subsequently divided into more finegrained segments by dividing all of the previous segments, going from left to right. (For the record, it's in fact a programming problem. I need to split up a large chunk of memory into seperate areas on the basis of a given number of tasks, and this number may change dynamically at runtime.) I cannot even find a proper recursive definition. So far I've only come up with this: If [itex]n1[/itex] is a power of two, then [itex]a_n=\frac{1}{2n2}[/itex]. But I simply can't figure out how to get the values inbetween like 3/4, 3/8, 5/8, 7/8, 3/16, ... and combine everything into one simple formula. It's driving me nuts. P.S.: In case this is really the wrong place to ask (it's not exactly about topnotch research in theoretical physics), I'd be happy for pointers to other places to ask these kind of questions. 



#2
Feb1413, 02:23 PM

P: 295

I personally cannot understand your question. The sequence given makes no sense to me at all. An illustration of what you are actually trying to do on the line might help.




#3
Feb1413, 04:06 PM

P: 688

Hello, 3ToedSloth,
you want a fraction a/p, with p=2^ceiling(ln(n) / ln(2)) and a=2np1. (The "^" represents exponentiation here.) How to translate that into a computer program without precision problems is another story. If the calculation of ln(n) / ln(2) gives you 3.00001, for example, when 3 was the theoretical result, you don't want the ceiling function moving 3.00001 to 4. "p" (the denominator) is meant to represent the smallest power of 2 that is larger or equal to "n". Rather than using floatingpoint logarithms, in a computer language that can handle bitwise operations you will be better served by the following algorithm: * count how many rightshifts it takes to make "n" become 0; call that count "c". * shift the number 1 by c1 positions to the left; call the result "p". * if p=n, then n was a power of 2 to begin with, and you want that value of "p". Otherwise, you want twice that value (leftshift "p" one more time). Here is a C++ example (port to your favorite flavor): given a value for "n",




#4
Feb1413, 04:22 PM

P: 4

Sequence resulting from evenly dividing a line
I've drawn an image an hope that makes it clearer. Blue numbers are input, green numbers are output. It's looks like a binary search tree.
http://postimage.org/image/byt1pn8s7/ Edit: The last line got messed up a bit. The distances should always be the same, of course. 



#5
Feb1413, 04:44 PM

P: 688

Python example, if C++ or bit manipulation are not your thing. (If Python isn't either, it is easier to read as pseudocode.)




#6
Feb1413, 05:10 PM

P: 688

Or, lastly, hack around the eventual precision problems.




#7
Feb1513, 12:06 PM

P: 4

Thanks a lot, Dodo!
I'm still interested in the actual formula for the sequence, but your great code examples have solved my practical programming problem. 


Register to reply 
Related Discussions  
90% done with this "evenly dstrbtd chrg on infinite line" problem. PLEASE help 10%  Introductory Physics Homework  10  
Determien the resulting function of the line with points (1,2) and (3,3) and....  Precalculus Mathematics Homework  5  
Next line in the sequence...  Linear & Abstract Algebra  5  
When does natural become man made? What's the dividing line?  General Discussion  18  
Field resulting from line charge  Introductory Physics Homework  1 