Sequence resulting from evenly dividing a line

3ToedSloth

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 non-recursive 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 fine-grained 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]n-1[/itex] is a power of two, then [itex]a_n=\frac{1}{2n-2}[/itex].

But I simply can't figure out how to get the values in-between 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 top-notch research in theoretical physics), I'd be happy for pointers to other places to ask these kind of questions.

Millennial

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.

dodo

Hello, 3ToedSloth,
you want a fraction a/p, with p=2^ceiling(ln(n) / ln(2)) and a=2n-p-1. (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 floating-point logarithms, in a computer language that can handle bitwise operations you will be better served by the following algorithm:

* count how many right-shifts it takes to make "n" become 0; call that count "c".
* shift the number 1 by c-1 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 (left-shift "p" one more time).

Here is a C++ example (port to your favorite flavor): given a value for "n",

Code:

int c = 0;
for (int b = n; b > 0; b >>= 1)
        c++;
int p = 1 << (c-1);
if (p != n)
        p <<= 1;
int a = 2*n - p - 1;
cout << a << "/" << p << endl;

3ToedSloth

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.

dodo

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

Code:

#!/usr/bin/python

class Fraction:
	def __init__(self, n):
		c = 0
		b = n
		while b > 0:
			b /= 2
			c += 1
		c -= 1
		p = 1
		while c > 0:
			p *= 2
			c -= 1
		if p != n:
			p *= 2

		self._p = p
		self._a = 2*n - p - 1

	def __str__(self):
		return '{0}/{1}'.format(self._a, self._p)

for n in range(1, 18):
	print n, Fraction(n)

dodo

Or, lastly, hack around the eventual precision problems.

Code:

from math import *
for n in range(1,18):
    p = int(pow(2, ceil(log(n)/log(2) - 0.001)) + 0.5)
    a = 2*n - p - 1
    print n, a, '/', p

3ToedSloth

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.

micromass

Quote by 3ToedSloth

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.

He gave the actual formula in the beginning of post 3.

you want a fraction a/p, with p=2^ceiling(ln(n) / ln(2)) and a=2n-p-1. (The "^" represents exponentiation here.)

It's far from pretty. But I don't think you'll get it any nicer.

Similar Threads for: Sequence resulting from evenly dividing a line
Thread	Forum	Replies
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

Millennial	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.

3ToedSloth	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.

dodo	Or, lastly, hack around the eventual precision problems. Code: from math import * for n in range(1,18): p = int(pow(2, ceil(log(n)/log(2) - 0.001)) + 0.5) a = 2*n - p - 1 print n, a, '/', p