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:

$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}, ...$

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 separate 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 $n-1$ is a power of two, then $a_n=\frac{1}{2n-2}$.

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",

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

#!/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.

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]

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.