img.latex_eq { padding: 0; margin: 0; border: 0; }

Friday, 5 October 2007

A Sequence

Start with the number 1.

To get the next number in the sequence:
(1) Go to the nearest integer strictly greater than the number you're on.
(2) Subtract the fractional part of your original number. The fractional part is the part that would be a fraction if you wrote the number in the standard 'composite' fashion (rather than an 'improper fraction'). For example, the fractional part of three and a half is a half; the fractional part of one and seven eighths is seven eighths.
(3)Take the reciprocal. (The easiest way to do that, as anyone with any mathematical fluency will tell you, is to write it as an improper fraction and then 'flip' the fraction -- put the bottom number on the top and the top number on the bottom. For example, three and a half is equivalent to 7/2; the reciprocal is 2/7. If you don't know why three and a half is 7/2 then, um, I'll be happy to explain in the comments...)

There are several ways of writing this as a mathematical formula. If x is the current number, then one way of writing the next number is

1/[_x_ + 1 - frac(x)]

where frac(x) is the fractional part of x, and I'm using the underscore for a floor function, which takes the nearest integer less than or equal to the number (floor function plus one gives the nearest integer strictly greater than the number, as required by the description above). If you're trying to follow without much mathematical experience, I'll give you for free that one over a number is always the reciprocal.

That's not necessarily the neatest formula; tidy it as desired, if you like that sort of thing.

Now go play.

No, seriously. If you're an experienced mathsy type, try to prove that the sequence contains every possible positive fraction exactly once (yes, people, sequences like that are possible). I did it in four hours -- working with a friend who was obsessed with Fibonacci numbers :-). Another friend of mine got it by himself in three, but our proof was nicer. And the Fibonacci numbers may or may not be a clue.

If you need a reason to go play, look at the sequence:

1

1/2

2

1/3

3/2

2/3

3

1/4

4/3

3/5

5/2

2/5

5/3

3/4

4

...

It's just kinda cool. Any and all patterns may or may not be useful for proving you've got every fraction in there....

3 comments:

Brent Yorgey said...

Have you seen this paper? Because if you haven't, you should. =)

And also maybe this one, although if you don't know any Haskell that one might be hard to follow, I'm not sure.

Lynet said...

Ah! I hadn't. And yes, that paper basically gives exactly our method of proof. Very nice. Thank you.

I don't know any Haskell, but the other paper is still interesting on a skim...

L.L. Barkat said...

I've been missing your voice on Seedlings (though I'm sure it hasn't been that long, but the blogworld makes time seem compressed and sometimes decompressed!). Anyway, I see you've been playing with numbers, so you have a great excuse. Somebody's got to do this, and it generally isn't me. (Even so, I must say I'm enjoying teaching math to my home-educated daughters. But. Well. It's third and fifth-grade math!)