Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 exptools; site ihnet.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!ihnet!eklhad
From: eklhad@ihnet.UUCP (K. A. Dahlke)
Newsgroups: net.math
Subject: Sequence of Irrational Numbers
Message-ID: <229@ihnet.UUCP>
Date: Thu, 16-May-85 13:12:48 EDT
Article-I.D.: ihnet.229
Posted: Thu May 16 13:12:48 1985
Date-Received: Fri, 17-May-85 01:30:09 EDT
Distribution: net
Organization: AT&T Bell Laboratories
Lines: 44

<>
	Consider a sequence of real numbers between 0 and 1,
defined recursively:  A[i] = A[i-1]+X mod 1;  A[0] = 0.
In other words, each term is the fractional part of the sum
of the previous term and a constant (X).
For example, when X = pi, the sequence begins:
0.0, 0.14159, 0.28318, 0.42477, 0.56637, 0.70796,
0.84955, 0.99114, 0.13274, 0.27433 ...
When X is rational (P/Q), the sequence is periodic, cycling every Q terms.
The sequence is more interesting when X is irrational (as above).
Each value occurs only once.  To show this, assume A[i] and A[i+k] are equal.
This implies k*X = l (k and l integers).  Since k is not 0,
X must be l/k (rational), contradicting the assumption.
Does every real [0-1) appear in the sequence?
Clearly not.  You cannot map a countable set onto a continuum of values.
Note that A[] contains no rationals, except A[0] = 0.

	Now for your homework assignment.
Given irrational X, and the sequence A[] described above.
1.  Prove, for every Y between 0 and 1, and for every epsilon > 0,
there exists A[i], such that Y-epsilon < A[i] < Y+epsilon.
In other words, arbitrarily small intervals always contain values from this 
sequence.
2.  If your proof is not constructive, design an algorithm for finding
a specific A[i] satisfying Y-epsilon < A[i] < Y+epsilon.
Example: find an A[i] between 0.499999999 and 0.500000001 (X = pi).
I want a time-bounded algorithm; stepping through the sequence
looking for a value that lies within the interval doesn't count.
3.  Design an algorithm to determine whether a given value (y)
is in the sequence A[i].
Example: is sqrt(2)-1 in A[] (X = pi).
4.  Find an algorithm implementing the inverse function.
Given a Y in A[i], find the index.
Example: what is the inverse of 10*pi-31 (X = pi).
Again, time-bounded, not waltzing through A[]
looking for Y.

	I don't know the answers to any of these questions.
I feel part 1 is true, and provable, and I will work on it.
I am rather pessimistic about 2, 3, and 4.
Any thoughts?
-- 

Karl Dahlke    ihnp4!ihnet!eklhad