Register to reply

Sequence resulting from evenly dividing a line

by 3ToedSloth
Tags: sequences and series
Share this thread:
3ToedSloth
#1
Feb14-13, 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 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.
Phys.Org News Partner Mathematics news on Phys.org
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
Millennial
#2
Feb14-13, 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.
dodo
#3
Feb14-13, 04:06 PM
P: 688
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
#4
Feb14-13, 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.
dodo
#5
Feb14-13, 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 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
#6
Feb14-13, 05:10 PM
P: 688
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
#7
Feb15-13, 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.
micromass
#8
Feb15-13, 12:15 PM
Mentor
micromass's Avatar
P: 18,229
Quote Quote by 3ToedSloth View Post
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.


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