December 2002 - mathfun@mailman.xmission.com

Re: [math-fun] Simultaneous rational approximation of two irrationals
by Mike Stay 08 Dec '02

08 Dec '02

>Gene asks: > ><< >If x is irrational, and I wish to best approximate the ratio x:1 by integers >a:b, then I would use continued fractions. Suppose x and y are irrational, >and I wish to best approximate the ratio x:y:1 by integers a:b:c. Is it >known how to do this? >>> Depends what you mean by 'best'. For two irrationals, you might want to look into cubic continued fractions. Here are two papers on bifurcating continued fractions that give good approximations; the determinant of three consecutive approximations is 1 (whereas normal CF's give +/-1), so in that sense they're optimal. (arxiv.org/pdf/math.GM/0002227 and /0008060) -- Mike Stay staym(a)clear.net.nz -- Mike Stay staym(a)clear.net.nz

1 0

Re: [math-fun] Simultaneous rational approximation of two irrationals
by asimovd＠aol.com 08 Dec '02

08 Dec '02

Gene asks: << If x is irrational, and I wish to best approximate the ratio x:1 by integers a:b, then I would use continued fractions. Suppose x and y are irrational, and I wish to best approximate the ratio x:y:1 by integers a:b:c. Is it known how to do this? >> This is a very interesting question, and I don't have much useful to contribute, except that 1) The family of ratios x:y:1 is perhaps best naturally encoded as the projective space P^2 = R^3 - {0} / (x,y,z) ~ (ax,ay,az) where a runs over all nonzero reals, aka the set of lines through the origin in R^3. 2) The answer probably depends on how the goodness of is measured; the most natural way seems to me to be the smallness of the angle between two lines, or equivalently the nearness of cos(angle) to 1. 3) The points in question will then be of the form +-(K,L,1)/sqrt(K^2+L^2+1) for integers K,L. The asymmetry of this expression suggests the last refuge of the scoundrel -- changing the question slightly. Perhaps we should allow the approximation to be via (K,L,M) for any integers K,L,M, leading to all points of the form +-(K,L,M) / ||(K,L,M)||, with sign(s) chosen so that a dot product is always positive. 4) An even more radical change-of-problem, but perhaps equally interesting, might be to look at the (dense set of) rational points +-(p,q,r) on P^2 (which especially John Conway discussed vis-a-vis spheres a few months ago) as possible approximators of an arbitrary ratio (x:y:1). Clearing denominators shows this is a subset of the points +-(K,L,M) / ||(K,L,M)|| of 3). --Dan

1 0

Re: [math-fun] Why 1.24 trillion digits of pi.
by asimovd＠aol.com 07 Dec '02

07 Dec '02

Simon Plouffe writes: << What could anyone do to test a big super computer like [Hitachi's] ? It would be perhaps interesting to see if we could use the so called Earth Simulator (35 teraflop/s) to compute pi once. >> This makes a lot of sense -- to use digits of pi to test supercomputers. (Though it seems clear this is only one of about aleph_1 different tests that would all serve equally well.) (Note: My remark about pi's digits possibly containing a message from another planet was a reference to part of the plot of Carl Sagan's sci-fi novel "Contact" -- which was a fun book, despite this nonsense.) Then, am I right that it has no particular mathematical value? (My feeling is that there *must* be some kind of pattern in the digits of any basic constant C, since two straighforward algorithms (computation of C and computation of its, say, decimal digits) would seem to necessarily have some kind of relationship. I confess that finding such a relationship, though perhaps not surprising to me, would be interesting, especially if the base of the number system were less random than 10 -- I'd prefer 2. So the issue of understanding {3^n} expressed in binary seems in fact a very interesting question. N.B. My favorite base of all, which like continued fractions has infinitely many distinct "digits", is factorial base (which I think many math-funners have seen). That is, for an positive integer n write n = a_k * k! + a_(k-1) * (k-1)! + ... + a_1 * 1! for integers 0 <= a_k <= k. And for a fractional part x, i.e., 0 <= x < 1, write it as x = n_1 / 2! + n_2 / 3! + ... + n_k / k! + ... where 0 <= n_k <= k for all k. (This works for x = 1, but in that case why bother?) I'd think the best chance of finding a pattern for pi would be in its continued fraction, or in factorial base. (Maybe for the cleanest representation, one should represent 1/pi, instead of pi, in factorial base.) --Dan

1 0

[math-fun] Why 1.24 trillion digits of pi.
by Simon Plouffe 07 Dec '02

07 Dec '02

hello, I think that there are 2 main reasons. The university of Tokyo big computers are from Hitachi and this computation is a visibility selling point for them. To hold that record is a matter of pride too. The second reason is to test the machine. They used(?) arctan formulas which is not the fastest but with it they used a lot of disk I/O and cpu. This is a very good stress test for the machine. I don't know yet if they used a Gauss-Salamin formula and/or one of Borwein's quartic formulas, the first being the fastest known. In any case , to do it 2 times with 2 different formulas and arriving at the same result is the test. What anyone could do to test a big super computer like that ? It would be perhaps interesting to see if we could use the so called Earth Simulator (35 teraflop/s) to compute pi once. Simon Plouffe

1 0

Re: [math-fun] 1.24 Trillion digits of pi
by asimovd＠aol.com 07 Dec '02

07 Dec '02

<< TOKYO (AP) - A team of researchers at a leading national university have set a world record by calculating the value of pi to 1.24 trillion places, one of the researchers said Friday. >> I am very, very fond of pi, but I don't think I've ever been particularly excited about the calculation of huge numbers of its digits. Suppose someone finally found some kind of pattern in the digits -- would that be so very surprising? (OK, I admit that if the pattern were a message from another inhabited planet, *that* would be something to write home about!) But I suspect I'm missing something. Can someone try to explain to me what's the big deal about more and more digits of pi, other than getting into Guinness? Thanks, Dan

3 2

Re: [math-fun] Re: Number of ones in the binary expansion of 3^n
by asimovd＠aol.com 06 Dec '02

06 Dec '02

MIke Reid writes: << when we work modulo 2^n (n > 2), this means that (Z / 2^n Z)^* is isomorphic to a product of two cyclic groups, C_2 x C_(2^n-2) with generators -1 and 5 >> By coincidence, just today I was reviewing the proof that for an odd prime, (Z/p^nZ)* is cyclic, and it's amazing how many websites "prove" it without noting the exceptions for p = 2, n > 2. --Dan --Dan

1 0

Re: [math-fun] Re: Number of ones in the binary expansion of 3^n
by reid＠hedgehog.math.arizona.edu 06 Dec '02

06 Dec '02

> > More likely, a(n)/n should tend to log_2(3)/2 = 0.79248+, > > since a bit is equally likely to be 0 or 1. (Well, the > > first and last bits are ones; I meant the other bits.) > > The fours bit is always zero. Other bits (at least up to the 2^29s > position) are exactly balanced. to know the structure of the multiplicative group modulo 2^n , it is useful to consider the unit group in the ring of 2-adic integers. it is well-known that this group is generated by -1 and 5 . moreover, it is a direct product, with -1 having order 2 , and 5 having infinite order. when we work modulo 2^n (n > 2), this means that (Z / 2^n Z)^* is isomorphic to a product of two cyclic groups, C_2 x C_(2^n-2) with generators -1 and 5 . we're interested in the subgroup generated by 3 , so we express it as a product of our generators; we get 3 = -1 * 5^t mod 2^n , where t is an odd integer. (to see that t is odd, consider the congruence modulo 8 .) thus we see that 3 has order 2^n-2 , which means that it generates a subgroup of index 2 inside the multiplicative group (Z / 2^n Z)^* . dan hoey's observation that 3^t is never congruent to 5 or 7 mod 8 identifies which subgroup it is. therefore all bit patterns subject to this condition occur. mike

1 0

[math-fun] Maximum orbit of an n-bit register with monotonic update rule
by Allan C. Wechsler 06 Dec '02

06 Dec '02

Ooh, that subject line is so deliciously jargony. You are probably wondering what the hell I mean. Suppose you have an automaton consisting of an n-bit register, where each bit's next state is a boolean function of the states of all the other bits. We wish to find a rule (that is, an update function for each bit) and an initial state that maximizes the number of states that the automaton traverses before it repeats a state. The obvious maximum of a 2^n-state trajectory is easily achieved by creating a binary counter. Each bit will be on next time in two cases: if it is now on and some bit to its right is off; or if it is now off and all the bits to its right are on. (This is just the standard carry rule, "flattened" to a boolean function of the present bit values.) But note that this logic is required to take explicit notice that certain bits are off. Suppose we restrict the logic, and permit only monotonic boolean functions? We now expect that the 2^n maximum cannot be achieved, in general. We can still implement an n-bit counter with monotonic update rules, but it takes 2n actual bits. So a lower bound of the maximum achievable orbit of such an automaton is 2^[n/2]. Can anyone tighten these lower and upper bounds of 2^[n/2] and 2^n? -A

7 11

Re: [math-fun] Re: Number of ones in the binary expansion of 3^n
by Dan Hoey 06 Dec '02

06 Dec '02

Don Reble wrote: > More likely, a(n)/n should tend to log_2(3)/2 = 0.79248+, > since a bit is equally likely to be 0 or 1. (Well, the > first and last bits are ones; I meant the other bits.) The fours bit is always zero. Other bits (at least up to the 2^29s position) are exactly balanced. Dan

2 1

[math-fun] Re: Number of ones in the binary expansion of 3^n (fwd)
by Helger Lipmaa 06 Dec '02

06 Dec '02

Math-fun, I forwarded Allan's email to Philippe Dumas. H. ---------- Forwarded message ---------- Date: Fri, 6 Dec 2002 12:52:44 +0100 From: Philippe Dumas <Philippe.Dumas(a)inria.fr> To: Helger Lipmaa <helger(a)tcs.hut.fi> Subject: [math-fun] Re: Number of ones in the binary expansion of 3^n (fwd) Helger Lipmaa writes: do you know an answer to this problem? H. I know only this is a very difficult one. Cobham's theorem says that a 3-rational sequence cannot be a 2-rational sequence, unless it is rational in the classical sense. (This is folklore, and there is a proof only for automatic sequences, that is rational sequences which take only a finite number of values). Here the sequence is evidently 3-rational and certainly not rational in the classical sense. For more, ask Jean-Paul Allouche (http://www.lri.fr/~allouche/, allouche(a)lri.fr) Give him my name. Best regards, Philippe

1 0