eklhad@ihnet.UUCP (K. A. Dahlke) (05/16/85)
<> 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
ttw@lanl.ARPA (05/20/85)
> <> > 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 The answer to your question 1 is "yes." The fractional parts of the multiples of an irrational number are dense. References are John H. Halton,"The distribution of the sequence {n 'XI'} (n=0,1,2,...)" ,Proc. Camb. Phil. Soc. 61,(1965),665-670. L. Kuipers and H. Niederreiter, "Uniform Distribution of Sequences," Wiley, New York, 1974. J. Schoiszengeier, "On the discrepancy of (n 'alpha')," Acta. Arith.,44, (1984),241-279. I think that the answer to 2, 3, and 4 can be obtained from the continued fraction structure of the irrational. As only rational operations are performed it would seem that two irrationals could not appear unless one had a linear rational relation to the other. Thus sqrt(2) and its relatives would not appear in the sequence generated by pi. For more information, see Cassels book on diophantine approximation (I forgot the title.)
djr@myriasb.UUCP (Don Reble) (05/22/85)
> Consider a ssequence of real numbers defined recursively: > A[i] = (A[i-1]+X) mod 1; A[0] = 0 > ... > Given irrational X, and the sequence A[] described above: Now THAT'S an interesting puzzle. > 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 ... First, let me note a few observations: 1) A[i] = frac(i*X) {frac means "mod 1", of course) since ((a mod 1) + b) mod 1 = (a + b) mod 1 2) If Y is an element of the A[] sequence, and Z = K*Y-N for some integer N and some positive integer K, then Z is an element iff 0 <= Z < 1 This follows from (1); if Y is an element, then Y=frac(i*X) for some i; if 0 <= K*Y-N < 1, then K*Y-N = frac(K*Y) = frac(K*frac(i*X)) = frac(K*i*X) which is A[K*i]. Now, on with the proof. Part a) For each non-zero A[i] in the sequence, there is a non-zero element A[j] which is < A[i]/2. Proof: Let m*A[i] be the largest multiple of A[i] which is less than one, that is, m*A[i] < 1 < (m+1)*A[i]. In other words, the A[i] size interver (m*A[i], (m+1)*A[i]) contains the number one. Therefore, one of the two numbers must be within A[i]/2 of one. Case a1) 1 < (m+1)*A[i] < 1+A[1]/2 0 < (m+1)*A[i]-1 < A[1]/2 From observation (2), we know that for some j, A[j] = (m+1)*A[i]-1 0 < A[j] < A[1]/2 Case a2) 1-A[i]/2 < m*A[i] < 1 A[i]/2 > 1-m*A[i] > 0 Let n*(1-m*A[i]) be the largest multiple of (1-m*A[i]) which is less than one, that is, n*(1-m*A[i]) < 1 < (n+1)*(1-m*A[i]) By similar reasoning, we know that 1-A[i]/2 < n*(1-m*A[i]) < 1 And therefore A[i]/2 > 1-n*(1-m*A[i]) > 0 A[i]/2 > (n-1)*m*A[i] + 1-n > 0 and for some j, A[j] = (n-1)*m*A[i] + 1-n < A[i]/2 In either case, we have j for which A[j] < A[i]/2 Part b) For any positive number p, there is an element A[k] < p. proof: Starting with A[1], apply theorem (a) repeatedly: A[j.1] < A[1]/2 < 1/2; A[j.2] < A[1]/4 < 1/4; A[j.3] < A[1]/8 < 1/8; ... A[j.k] < A[1]/2**k < 1/2**k; Obviously, we will find an element smaller than p after at most 1-log2(p) steps. Part c) For any interval Y-eps, Y+eps, where Y-eps>0 and Y+eps<1, there is an element A[l] such that Y-eps < A[l] < Y+eps Proof: let p = 2*eps and apply theorem (b); we have A[k] < 2*eps. There will therefore be a multiple of A[k] in the required interval, which by observation (2), will be a member of the sequence. > 2. ... design an algorithm for finding a specific A[i] satisfying > Y-epsilon < A[i] < Y+epsilon ... The previous proof is constructive, and the algorithm falls out quite nicely. Given X, Y, EPS: let I = 1, let AI = frac(X); { A[I] } while (Ai >= 2*EPS): let M = trunc(1/AI), { largest multiple < 1 } let MA = M*AI, let NMA = MA+AI; { next multiple } if (NMA < 1+AI/2): { case 1 } let I = (M+1)*I, let AI = NMA - 1; else { case 2 } let N = trunc(1/(1-MA)), let I = N*M*I, let AI = 1-N*(1-MA); endif end while { now, AI = A[I] < 2*EPS } K = round(Y/AI), { a multiple in the interval } AI = K*AI, I = K*I; print("A[",I,"] = ",AI," is in the required interval"); end. A sample run will illustrate some of the difficulties implementing this program. > Example: find an A[i] between 0.499999999 and 0.500000001 (X = pi). starting with i = 1, a[i] = .14159 26535 89793 23846 26433 83279 50288 41971 69399+ step 2: i = 784 a[i] = .00864 04143 97898 95471 24124 91130 26121 05808 09110 08296 36443 56560 36932 80625 28387 85492 43793 03068 21978 12980 04099 82641 33284 11321 57417 38876 56469 67268 17759 72729 19608 10227 36518 39+ step 3: i = 90944 a[i] = .00228 80701 56278 74663 98489 71110 30042 73738 56769 62378 27453 61002 84205 52532 92991 17122 79991 55913 49463 05684 75579 86394 60957 13302 60417 09681 50482 03108 60128 36586 74539 86374 36134+ step 4: i = 35 06085 82016 a[i] = .00009 94680 11948 39871 13100 25751 81767 58522 48381 97287 41732 10731 20126 86856 65194 57953 78658 87288 69241 50141 49603 08343 92641 85836 37480 72924 32991 23189 17889 33075 26262 470+ step 5: i = 73313 09596 01424 38400 a[i] = .00002 16388 46691 83352 87668 80383 12718 20666 44724 51637 95999 40165 21743 77830 48358 64791 01950 76841 25471 59637 94550 39549 24319 79504 38524 03057 67529 60619 94767 95456+ step 6: i = 85172 40351 19838 87151 53504 25600 a[i] = .00000 13081 12316 77183 98657 37066 99343 62659 89715 48839 83516 47546 01279 27698 55313 53772 11144 58743 75631 80742 18599 98759 19275 41631 18756 71628 72081 20177+ step 7: i = 142 06403 06454 36933 48871 45611 60087 68225 28000 a[i] = .00000 03674 48721 42478 04520 68315 39880 59894 34668 37810 14890 79134 29697 93905 70206 67897 77528 86067 79127 28792 18621 89200 00309 75637 90902 72716+ step 8: i = 6 13671 77321 50644 35772 89373 02579 76906 32154 11560 37591 04000 a[i] = .00000 00293 85592 08485 24503 45098 66912 87340 10334 07402 80472 84679 24711 79570 54347 18835 01388 06181 01803 86403 88769 24634 7201+ step 9: i = 14 28854 21479 11278 09077 11739 11103 72445 06630 59524 25775 38075 51386 78620 16000 a[i] = .00000 00080 83802 89448 30096 30129 99910 62354 28489 35147 84705 26599 45222 46334 82190 67513 30794 52616 37805 684+ step 10: i = 963 12392 38730 82454 46128 28357 36790 66952 43773 75157 07591 55791 60521 29106 89444 52463 54554 88000 a[i] = .00000 00002 14434 11475 76218 88680 40779 38670 96325 86073 43672 98953 76730 18257 57909 00661+ step 11: i = 449 14678 10556 71461 71744 15710 39095 32068 26891 38950 11822 72673 12361 00484 55696 77645 82955 88370 95956 48000 a[i] = .00000 00000 47762 09547 32489 77317 14345 31468 44631 74567 11379 50441 88541 55328+ final step: k = 470 19166 19958 97251 10643 74467 84015 69497 87060 15493 32198 71544 85989 46239 40276 15581 55902 20488 29502 56325 34855 68000 a[k] = .49999 99999 59703 24486 29112 94658 98317 24377 75888 73256 76878 34371+ pi*k = 1477 15067 11054 85983 24557 28475 61701 37159 05857 12001 91066 69825 04728 12167 43848 18163 02834 91683 96594 42032 28586 56352 .49999 99999 59703 24486 29112 94658 98317 24377 75888 73256 76878 34371+ We finally got there, but the numbers are ridiculous. One should be able to discover a better algorithm using continued fractions. > 3. Design an algorithm to determine whether a given value (y) is in > the sequence A[i]. This one is tough. Being able to generate digits of (y) is clearly inadequate; for example, after generating the first millon digits, we have a (small) interval which contains y; but problem (1) shows that there are members of A[] is this interval, as well as non-members. Indeed, there are an infinitude of both! We cannot discover which set (y) belongs to this way. We can generate ALL digits, though, if there is some simple pattern in them. If the pattern repeats, (y) is rational, and therefore is not in the set. If the pattern does not repeat, well, good hunting. However, given some exact representaion of (y), one is frequently able to prove membership or non-membership. > Example: is sqrt(2)-1 in A[] (X = pi)? No. If sqrt(2)-1 were in the sequence, there would be some integers K,N such that K*pi-N = sqrt(2)-1, or pi=(sqrt(2)-1+N)/K, which would make pi algebraic. It is not. Other examples: is frac(pi/2) in the sequence? No. If K*pi-N = Pi/2-1, then (K-1/2)*pi = N-1, and pi is rational. is frac(sqrt(pi)) in the sequence? No. If K*pi-N = sqrt(Pi)-1, then K*pi-sqrt(pi)+1-N = 0, and pi is algebraic. is e (2.71828+) in the sequence? I strongly suspect not. There would have to be some strange relation between pi and e for this to come out. (Even stranger than exp(pi*sqrt(-1)) = -1) ). > 4. Find an algorithm implementing the inverse function. Given a Y > in A[i], find the index. This problem is closely related to #3. We might well ask how we know Y is in A[]. If some deity thunders, "It's in there, find it!", we are probably out of luck. On the other hand, if we can prove Y is in A[], then no doubt the proof will tell us where. I hope I've helped answer your questions. Don Reble Myrias Research Corp. ...ihnp4!alberta!myrias!djr