southard@unc.UUCP (Scott Southard) (09/23/85)
Expires: References: Sender: Keywords: I have come across a problem that I would love to learn the solution to... if anyone can help me I would appreciate it. Is the set of numbers of the form 2^m * 3^n (that's 2 to the m power times 3 to the n power) where m and n are integers, dense in the positive rational numbers? The set of rationals is dense in the real numbers, for example, since between every two distinct real numbers a rational number may be found. The question is, can a number of the form 2^m * 3^n be found between every two positive rational numbers? Scott Southard <southard@unc>
eklhad@ihnet.UUCP (K. A. Dahlke) (09/27/85)
> ... The question > is, can a number of the form 2^m * 3^n be found between every two positive > rational numbers? > Scott Southard This is an interesting problem, let me attempt a proof. Restated: for each pair of positive reals R < S, there exists integers M and N, such that R < 2^M * 3^N < S. R and S need not be rational. Since log base 3 is a continuous, monotonic, cheerful function, we can take logs across the board, transforming the inequality: log3(R) < log3(2)*M + N < log3(S). In other words, it is sufficient to prove that numbers of the form log3(2)*M + N are dense in the reals. Next, we can shift the interval (log3(R), log3(S)) by an integer offset, so that 0 <= log3(R) < 1. The naked integer "N" in "log3(2)*M + N" takes up the slack. Thus, it is sufficient to prove that numbers of the form log3(2)*M + N are dense in the interval (0, 1). This problem was discussed here a few months ago (don't know if you are a regular subscriber). For any irrational X (e.g. log3(2)), the set of values K*X mod 1 is dense in (0, 1). Several people offered clever proofs, though the exact details elude me. Let me try to recreate the reasoning. Take a circle 1 unit in circumference, and take quantized steps around it, each step of length X. Is there a section of the circle you never land in (say (R, S))? No. The first time you step over 0 (where you started), you will land within X/2 of 0. In the case of log3(2) (approximately 0.630929), it only takes 2 steps, and you are at 0.261859. Now group your steps together, traveling 0.261859 each time, and adding 2 to M instead of 1. After 3 more steps (now only 0.261859 in length), you will again cross 0, landing at 0.047438, and you can again modify your step size. After another 20 such steps, you are at 0.996198. Each iteration divides your step size in half (at least). When it is finally less than S-R, you will surely land in the (R, S) interval on your next trip around. We must also show that log3(2) is irrational, but that is easy. Assume log3(2) = P/Q (rational), and consider log3(2^Q) = (P/Q)*Q = P. Thus 3^P = 2^Q, contradicting the fundamental theorem of arithmetic. After all this, you have probably lost sight of the original problem. The bottom line is, the values 2^M * 3^N are dense in the positive reals. Hope this helps. -- This .signature file intentionally left blank. Karl Dahlke ihnp4!ihnet!eklhad
ian@sdcsma.UUCP (Ian Ferris) (09/27/85)
In article <58@unc.unc.UUCP> southard@unc.UUCP (Scott Southard) writes: > >Is the set of numbers of the form 2^m * 3^n (that's 2 to the m power times >3 to the n power) where m and n are integers, dense in the positive >rational numbers? > If I'm not mistaken, if p and q are relatively prime integers, then the set S of numbers of the form p^m * q^n is dense in the positive reals. I suspect, since school has just started in most places, that this is a homework problem in either a junior level analysis course or an honors freshman calculus course. (If my suspicion is unfounded, I apologize). Since I think it's a bad idea to do other people's homework, I will only remark that one possible proof of this fact (the only one that I came up with) can be gotten by considering the logarithms of the numbers in S and proving that they are dense in the reals. This approach also requires you to know the following theorem: if r is any irrational number and e is any positive real number, then there exist integers m and n such that 0 < abs( m + n * r ) < e. However, thanks for the problem! I had a very pleasant noontime walk yesterday while working on it.
janw@inmet.UUCP (09/30/85)
[ Written 12:17 am Sep 23, 1985 by southard@unc in inmet:net.math] > Is the set of numbers of the form 2^m * 3^n (that's 2 to the m power times > 3 to the n power) where m and n are integers, dense in the positive > rational numbers? Your problem was the last thing I read before the hurricane hit. So it gave me something to think about during the blackout. The answer to the problem is *yes*, proof follows: Denote the set of numbers of the form 2^m * 3^n with Z. (1) Obviously, multiplying or dividing two elements of Z produces an element of Z. In particular, 1/x, where x is a number of our type, also belongs to it. (2) Lemma : 1 is a condensation point of Z. In other words, there is a sequence of elements of Z, all different from 1, tending to 1. This lemma is proved below, in (4); for now assume it proved. Then it follows, as a corollary, that there exists a sequence of elements of Z, all *less than 1*, tending to 1. To prove the corollary, take any sequence of the kind whose existence is established by Lemma, and replace each member z of it that is >1 , with 1/z. (3) Using this corollary, we can prove the main proposition. Namely, that for every alpha & beta such that 0 < alpha < beta, there exists a z belonging to Z such that alpha < z < beta. By Lemma and its corollary in (2), there exists an A such that alpha/beta < A < 1 and A belongs to Z. Obviously, there exists an element B of Z such that beta < B. Now consider the sequence b[i] = B * A^i (i = 0, 1, ...). Each member of this sequence belongs to Z. For sufficiently large i, b[i] < beta (since A < 1). Consider the *last* element b[t] such that b[t] >= beta. Then, since A > alpha / beta, alpha < b[t+1] < beta, Q. E. D. (4) Now we have to prove the Lemma stated in (2). Consider two sequences a[i], b[i] (i = 0, 1, ...) defined as follows: a[0] = 2/3 ; b[0] = 4/3 ; for every i, a[i+1] = a[i] * b[i] iff a[i] * b[i] < 1; else a[i+1] = a[i]; similarly, for every i, b[i+1] = a[i] * b[i] iff a[i] * b[i] > 1; else b[i+1] = b[i]; Note : The case a[i] * b[i] = 1 will never arise since all the numerators in a[i], b[i] are powers of 2, while all the denominators are powers of 3. For the same reason no a[i] or b[i] equals 1. Intervals ( a[i] , b[i] ) form a sequence of shrinking intervals straddling 1 : a[i] < 1 < b[i] for all i. a[i] monotonically increase, while b[i] monotonically decrease. It follows that there are limits A <= 1 and B >= 1, to which a[i] and b[i], respectively, tend. Let us prove that at least one of these limits equals 1 (actually, both do). Since all the numbers a[i], b[i] belong to Z, this will prove the lemma. Assume the contrary : A<1<B. A*B cannot equal 1, because then, a[i] * b[i] would tend to 1, and therefore (by the way the sequence is constructed) either a[i] or b[i] would tend to 1. Thus, either A * B > 1, or A * B < 1. Assume the former: A*B > 1. But then, for sufficiently large i, say, for i >= t >0, a[i] * b[i] > 1. Therefore, for all i >=t, b[i+1] = a[i] * b[i] < A * b[i]. Thus, for i > t, b[i] < b[t] * A^(i-t), and, since, by hypothesis, A < 1, b[i] tends to 0, which is absurd. For the case A*B < 1, the proof is symmetrical to this: Assume A*B < 1. But then, for sufficiently large i, say, for i >= t >0, a[i] * b[i] < 1. Therefore, for all i >=t, a[i+1] = a[i] * b[i] > a[i] * B. Thus, for i > t, a[i] > a[t] * B^(i-t), and, since, by hypothesis, B > 1, a[i] tends to infinity, which is absurd. The Lemma is proved. Jan Wasilewsky, at Intermetrics, Inc. 733 Concord Ave, Cambridge, MA
franka@mmintl.UUCP (Frank Adams) (10/01/85)
In article <58@unc.unc.UUCP> southard@unc.UUCP (Scott Southard) writes: >Is the set of numbers of the form 2^m * 3^n (that's 2 to the m power times >3 to the n power) where m and n are integers, dense in the positive >rational numbers? Yes. Here is an outline of a proof. Take the logarithm of the numbers, getting m*log(2) + n*log(3). It is fairly easy to show that the numbers of the form m*x + n*y, where y/x is not a rational number, are dense in the reals. Since the logarithm is order preserving, 2^m * 3^n must be dense in the positive reals (equivalent to dense in the positive rationals). If log(3)/log(2) were rational, there would be numbers n and m such that 2^m = 3^n, which violates unique factorization. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108