[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1697.0. "Crux Mathematicorum Problem 1785" by RUSURE::EDP (Always mount a scratch monkey.) Mon Nov 30 1992 18:15

    Proposed by David Doster, Choate Rosemary Hall, Wallingford,
    Connecticut:
    
    (a) Show that the set of numbers of the form 2^r/5^n, where r is a
    nonnegative rational number and n is a nonnegative integer, is dense in
    the set of nonnegative real numbers [that is, any nonnegative real
    number can be approximately arbitrarily closely by numbers of the form
    2^r/5^n].
    
    (b)* What if r and n must both be nonnegative integers?
    
    The asterisk indicates the problem was submitted without a solution.
T.RTitleUserPersonal
Name
DateLines
1697.195% there.CADSYS::COOPERTopher CooperTue Dec 01 1992 14:0673
Problem a)

    Follows from the solution to problem b.

Problem b)

    We are trying to approximate a value X to within an error of eps1,
    i.e.,

	X ~eps1= 2^r / 5^n	r, n non-negative integers

    We can "take the log of both sides", that is, we can find a value
    eps2 such that:

	log(X) ~eps2= log(2^r / 5^n)

    will guarantee that the previous condition will also be met.  In
    particular I will let the log be to the base 2 (lg), so

	lg(X) ~eps2= r - n*lg5

    CASE 1: X = 1; lg(X)=0

	r=n=0

    CASE 2: X > 1; lg(X)>0

	The following procedure will find the necessary values:

	Let X' be 1 - decimal_part(X).

	We want to find an "n" such that

	    X' ~eps2= decimal_part(n*lg5)

	Note that lg5 is irrational (easily proven) and that this implies (I
	have not yet proven this, but I am quite confident about it, and I
	think that I have seen such a proof) that such an n can always be
	found.

	Now choose r = floor(X) + floor(n*lg5) + 1, and we are done.

    CASE 3: X < 1; lg(X)<0

	Let:

	    n1 = ceiling(|X|/lg5)	(note: n1>0)

	and let

	    Y = lg(X) + n1*lg5

	Note that Y is non-negative and the logrithm of some positive
	value.  We may thus use the previous two cases to find an r and
	an n2 such that,

	    Y ~eps2= r - n2*lg5

	But since

	    lg(X) = Y - n1*lg5

	we get that:

	    lg(X) ~eps2= r - n2*lg5 - n1*lg5 = r - (n1+n2)*lg5

	Since r, n1 and n2 are all non-negative integers and thus n = n1+n2
	is also, we have solved this case as well.  QED

    I'll see if I can come up with a proof or a pointer to a proof for the
    unproven lemma this lunch hour.  Contributions on this welcome.

				    Topher
1697.2Got it.CADSYS::COOPERTopher CooperTue Dec 01 1992 16:1534
    To finish up, we need (to outline) a proof for the following lemma:

	Let p be an irrational number.  Then we can find a positive integer
	N such that decimal-part(N*p) will be less than eps (0<eps<1) of
	any arbitrary value t (0<t<1).

    Lets first examine the behavior of a rational value a/b (assumed
    reduced, i.e., a r.p. b) under successive multiplication by the integers
    1 through b.  The decimal parts of the results will form the set:

	{1/b, 2/b, 3/b, ... , (b-1)/b, 1}

    So any t (0<t<1) may be approximated within eps = 1/b by the decimal
    part of some multiple of a/b between 1 and b.

    So we need only find a rational approximation to p (our irrational),
    a/b, such that:

	1) a/b is in fully reduced form,
	2) 1/b < eps/2
	3) b*p ~eps/4= a   (= (a/b)*b)
	4) a/b > p

    This means that each of the multiples of p between 1*p and b*p will be
    within eps/4 of one of the multiples of a/b between 1*a/b and b*a/b.
    (Condition 4, will make each irrational multiple slightly smaller than
    its corresponding rational multiple).  This in turn means that the
    decimal part of each multiple of p will be within eps/4 of each of
    the decimal part of the corresponding multiple of a/b.  (Condition 4
    avoids "wrap around" for the value near 1).  One of those decimal
    parts of a multiple of p will therefore be within eps/4 of a value
    within eps/2 of t, which means that it is within eps of t.  QED.

					Topher