January 2003 - mathfun@mailman.xmission.com

[math-fun] 1.24 Trillion digits of pi
by Richard Schroeppel 09 Jan '03

09 Jan '03

http://www.guardian.co.uk/worldlatest/story/0,1280,-2223732,00.html Pi Value Calculation Earns Record Friday December 6, 2002 7:20 AM 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. Professor Yasumasa Kanada and nine other researchers at the Information Technology Center at Tokyo University calculated the value for pi with a Hitachi supercomputer over 400 hours in September, project team member Makoto Kudo said. The new calculation is more than six times the number of places in the record currently recognized by Guinness World Records - 206.158 billion places - which Kanada also helped calculate in 1999. Kanada's team spent five years designing the program used in the September experiment, Kudo said. The Hitachi supercomputer is capable of 2 trillion calculations per second, or twice as fast as the one used for the current Guinness record calculation.

3 2

[math-fun] (no subject)
by Helger Lipmaa 09 Jan '03

09 Jan '03

Simon Plouffe was wondering that some people are calculating pi by using imperfect algorithms. Here is an example of some people doing factoring by using imperfect algorithms. Helger ----------------------------------------------------- Date: Tue, 7 Jan 2003 13:00:30 +0200 (EET) From: Markku-Juhani O. Saarinen <mjos(a)tcs.hut.fi> To: Phil Carmody <fatphil(a)asdf.org> Cc: Helger Lipmaa <helger(a)tcs.hut.fi>, Johan Wallen <johan(a)tcs.hut.fi> Subject: 2000+ complete idiots doing factoring Hi, This is from "The Neo Project", http://www.theneoproject.com, which recently got to the news: http://news.com.com/2100-1040-979301.html They've got a lot of people working on this: LIVE RSA-576 Project Statistics Live: Tuesday January 07, 2003 05:39:28 EST (GMT -5) Total Users: 2,069 Total Nodes: 6,457 Total Teams: 1648 Total Packets Complete: 36,878,155 Total Keys Checked: .14633251904E+15 Total CPU Years: 160.3000 Now.. the good bit. Check out their method (from the FAQ's [sic]): How are we going to crack the RSA 576 challenge? [..] You can basically get a bunch of computers together and start sieving, but that could take months, years, decades, even centuries. So we decided to take the random approach. We do this by to generating a random number less than or equal to the square root of the challenge number and add 1 digit until its a possible prime number, as per Miller's Primality Test (while keeping the number the same length as the square root of the challenge) and see if the challenge number is evenly divisible by the "altered" randomly generated number. If it is... it is figured out. We are looking in to incorporating a few known methods, but keeping it a little random! Cheers, - mjos Markku-Juhani O. Saarinen <mjos(a)tcs.hut.fi> Helsinki University of Technology

1 0

Re: [math-fun] Fibonacci power triangle
by Richard Schroeppel 08 Jan '03

08 Jan '03

Date: Tue, 7 Jan 2003 17:12:06 -0800 (PST) From: "R. William Gosper" <rwg(a)spnet.com> Rich said >This can probably be connected with q-binomial coefficients. Bingo. But to make matters worse, there are q-Fibonacci numbers. >Some other curiosities: >(-1 2 2 -1) also works for F*F' It works for Fib(n+a)*Fib(n+b), a, b arbitrary integers. >(-1 -3 6 3 -1) works for F*F'*F'' Likewise. If I load("c:\\rwg\\climax\\share\\differ6.mac") Warning - you are redefining the MACSYMA function DIFFERENCEQ (which is why it doesn't load automatically) (c17) makerecurrence(f(n),fib(n-12)*fib(n-9)*fib(n+5)) (d17) f(n) - 3 f(n - 1) - 6 f(n - 2) + 3 f(n - 3) + f(n - 4) However, trying to recover fib(n)^3 by imposing initial conditions, (c18) differenceq(%,f(n),f(0)=0,f(1)=1,f(2)=1,f(3)=8) we get instead the alternative form fib(3 n) + 3 fib(- n) (d18) f(n) = --------------------- 5 Without the initial conditions, (c19) differenceq(d17,f(n)) (d19) f(n) = %r15 fib(3 n + 1) + %r16 fib(3 n) + %r14 fib(- n) + %r13 fib(1 - n) I.e., for any integers a,b,c, there are constant values of %r13,...,%r16 to make f(n) = fib(n+a)*fib(n+b)*fib(n+c). Similarly for fib(n)^2: (c21) makerecurrence(g(k),fib(k)^2) (d21) g(k) - 2 g(k - 1) - 2 g(k - 2) + g(k - 3) (c22) differenceq(%,g(k),g(0)=0,g(1)=1,g(2)=1) k 2 fib(2 k + 1) - fib(2 k) - 2 (- 1) (d22) g(k) = ------------------------------------ 5 a peculiar expression for fib(k)^2. To those of you running my Macsyma enhancements, I apologize upon discovering that the MAKERECURRENCE in \rwg\climax\share\differ6.mac returns recurrences of needlessly high order, which I just corrected in differ6 by exhaustively trying all "factors" of the difference operator, in spite of a so-far successful conjecture as to which factor to try. Also, since the even power annihilators contain the difference operator as a factor, there is a lower order operator that renders fib(k)^(2*n) a non-zero constant. --rwg

1 0

Re: [math-fun] Re: Krantz review of Wolfram Book
by asimovd＠aol.com 08 Jan '03

08 Jan '03

I strongly urge anyone who feels the Bulletin carried an ill-considered review to write to the Editor about it (Donald Saari, bams(a)ams.org) (I was very disappointed in some of the "survey" articles in the Jan. Bulletin, due to their utter inaccessibility -- at least to this mathematician. I think several were given a pass because of the fame of their authors and because they are just replicas of talks given at the L.A. Millennial meeting in 2000. But I don't think any of this is a justification for printing impenetrable survey articles.) --Dan

1 0

[math-fun] Chern Shing-shen & Krantz review
by Thane Plambeck 08 Jan '03

08 Jan '03

The Krantz review is valuable because it is an approachable document that can be read and enjoyed by a nonmathematical reader. It's actually quite amusing I think, and not just because it has some cheap shots in it (although I agree, it does). I forwarded it to a classical scholar of Greek, an English professor, and a venture capitalist and they all thanked me for sending it. Two of them asked me if I "agreed with it" and I said I had only flipped through the book, so really had no idea. I suggested they take a look at it themselves. Generally speaking there is a tremendous shortage of popularly-approachable reviews and accounts of the mathematical literature, and there is a public out there that will read and enjoy it if it is done well. There are plenty of sterile technical analyses, addressed only to the specialist, of ANKOS available already. It's good that the Bulletin published the Krantz review in my opinion. * * * * At the ICM 2002-Opening Ceremony in Beijing, SS Chern contributed this introduction (in part) It is my great pleasure to welcome you to this gathering....In 2000, we had a mathematics year, an effort to attract more people to math. We now have a vast field and a large number of professional mathematicians whose major work is mathematics. Mathematics used to be individual work. But now we have a public. In such a situation a prime duty seems to be to make our progress available to the people. There is clearly considerable room for popular expositions. I also wonder if it is possible for research articles to be produced by a historical and popular introduction. The net phenomenon could be described as a globalization. It is more than geographical. In recent studies different fields were not only found to have contacts, but were merging. We might even foresee a unification of mathematics, including both pure and applied, and even the possibility of the emergence of a new Gauss. Chern's Whole text at http://www.mathunion.org/ICM/opening_speech.html Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

[math-fun] Re: Krantz review of Wolfram Book
by mcintosh＠servidor.unam.mx 07 Jan '03

07 Jan '03

Rich: I finally got around to reading ... By some stroke of coincidence, my copy of Bulletin of AMS was sitting in the morning mail, just after Rich's message arrived. So, nothing to do but take a look. Well, it is slightly different than the advance copy which many of us have already read, and the differences aren't good. Somehow, when I read that copy I dismissed it, failing to take adequate notice that it was destined for the AMS Bulletin, which is a serious publication of a major scientific society. How they managed to publish such a revier is a cause for wonderment. To start with, they don't accept reviews from the public, which are automat- ically rejected (see the statement of policy in the Bulletin). Rather they commision them. Well and good, but from whom? You would think that there are numerous candidates, who are knowledgeable in cosmology, dynamical systems, automata, the history of science, whatever ... . So, who is Steven G. Krantz? Well, he is a member of their editorial board, specializing in complex analysis who has reviewed some books and written some editorials. Perhaps he is not familiar with the areas represented by the contents of ANKOS. Still, you would think it possible to read a book and form some coherent view of its content. But wait! He starts right off by failing to capture the essence of Rule 30 (which was the subject of some commentary here last fall. Apparently word didn;t get back to him.} Indeed, to say ``Vestigial forms of cellular automata were around in the 1950's --- ...'' Doesn't this man even have the slightest idea of where cellular automata came from? I really don't want to turn this into a flame. But a couple of tidbits might merit mention. I footnote 2 (not in the draft) he asserts that Addison-Wesley was contacted about publishing the book, but ``One sticking point in that relationship was that he demanded that any reviewer sign a nondisclosure agreement and promise not to study math nor physics for the ensuing ten years.'' Some of the other reviewers have mentioned the nondisclosure agreement as well as the expensive meal to which they were invited; such agreements seem to be rather standard oven if the meal is not. Well, prepublication publicity is one thing, even Science and Nature have come under discussion for practicint it against journalists. Getting good reviews at the time of publication is undoubtedly seen as a sales technique, and so on... . But do you really think that Wolfram brought that promise into the bargain? I don't know Wolfram close at hand, and maybe he said something like that as a joke. I doubt it, and I wonder how the (other) editors at the Bulletin allowed that footnote to get into the review? If true, it ought to have some substantiation. Footnote 3 tries to set mathematicians and physicists apart in their thinking, and we all know that they represent two different styles of thought. But are they really orthogonal? In one of his Notices editorials, our reviewer takes on she chemists. I suspect that he is as fond of his wit as Wolfram is of his intellect, and both can get to be a little overwhelming. I wonder if Freeman Dyson actually said what he is cited for in footnote 6, and if so, whether he acquiesced in having been quoted as having said it. On to footnote 7 and the Heisenberg principle, which was stated differently and more jargonly in the preprint. We discussed that here a couple of weeks ago. We had a whole course on this, under the guise of ``quantum computing'' in our last summer school; one should be aware that to mention the principle is but to call attention to the tip of an iceberg. Well, to cut this short, I agree with Richard, and feel quite bemused to realize that I had not comprehended what had happened untill he mentioned it. If the review had appeared in a lesser journal, one might not worry so much, but >that society< and >that journal< deserve a review of much higher quality. ---- Here is a chance to comment on an earlier comment. At first sight, it appears that there is an error in the ANKOS treatment of Rule 110, because the text and the drawings do not entirely correspond to each other. Separate correspon- dence and careful analysis reveal that the dozen pages or do of description is far too inadequate to constitute a comprehensible description of the Turing Machine emulation; several dozen would be more appropriate. One hopes that they will eventually be forthcoming. - hvm ------------------------------------------------- Obtén tu correo en www.correo.unam.mx UNAMonos Comunicándonos

1 0

[math-fun] Re: Fibonomial triangle
by N. J. A. Sloane 06 Jan '03

06 Jan '03

Rich, that triangle is in the OEIS, of course - see A010048 and A055870 NJAS

1 0

[math-fun] simultaneous approximation
by Richard Schroeppel 06 Jan '03

06 Jan '03

On Dec 8, 2002, Gene Salamin asked 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? Dan Asimov suggested some possible definitions of "best" based on projective plane ideas. Mike Stay suggested 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) David Bailey remarked This is just the integer relation problem for n = 3. The integer relation problem for n = 2 is solvable by the standard Euclidean algorithm. For n = 3 one can use PSLQ, or suitably modified application of LLL. Gene continued with If irrational x is approximated by rational p/r, and irrational y is approximated by rational q/r, then a hand-waving argument using information conservation shows that there should be lots of approximations good to order r^(-3/2). If we did not require the same r in both denominators, then it is known from continued fraction theory that we could do better, namely r^(-2). Suppose x and y are given with n bits each, for a total of 2n bits. Then integers p, q, r will have (2/3)n bits each. If the fractions are to be good to n bits, then the error is of order r^(-3/2). Is this conjecture known to be true (or false)? which seems to be the last message in the discussion. I have a couple of comments. I don't understand DHB's remarks about the Integer Relation Problem. I've always taken the IRP to be looking for linear combinations of several given numbers (such as pi, e, and gamma) with integer coefficients, that are close to 0, or close to 0 (mod 1). Gene's problem is different, since he's essentially asking for only one number, a "common denominator" to use for two approximations. I don't know of an LLL version that solves this problem, but I'm no expert on LLL. It's certainly a latticey kind of problem. Gene's order r^(-3/2) conjecture is Theorem 200 of Hardy & Wright, An Introduction to the Theory of Numbers. For dimension N, assuming at least one of Xi is irrational, there are infinitely many solutions where R*(X1,X2,...,Xn) (mod 1) is within 1/R^(1/N) of (0,0,...,0) in each coordinate. Setting N=2 and dividing by R gives R^(-3/2). The proof idea is to divide the unit cube into subcubes of side 1/[R^(1/N)]; some subcube must contain two multiples of the X vector. There's a fine point here worth mentioning: We can find Rs such that the distance-of-multiple-to-integer is bounded by 1/R^(1/N), and distance of Xi to numerator/R is bounded by 1/R^(1+1/N). But if we choose a denominator limit Rmax, there's no guarantee of a denominator R<=Rmax that is within 1/Rmax^(1+1/N). The best we can get is 1/(R*Rmax^(1/N)). A 1-dimensional example: Suppose X is irrational with decimal expansion 1/10 + 1/10^10 + ...; one of Liouville's numbers would serve. Let Rmax=10^6. Look at abs(X-P/R) with R<=Rmax. Can we make it < Rmax^-2 = 10^-12? No! Unless R is a multiple of 10, |RX-P|>.1-.0001; if 10|R, then P/R reduces to 1/10, and abs(X-1/10)>10^-10. --- The following algorithm gives a reasonable method for finding good denominators, but it has some pitfalls I'll sketch at the end. It's a 2-dimensional generalization of one of my pre-LLL relation- finding methods. X,Y are irrational. We want multiples N(X,Y) (mod 1) close to 0,0. Our starting square is (-1/3,1/3)^2 with area 4/9. Find, by trial, four multipliers N++, N+-, N-+, and N-- such that N++ * (X,Y) mod 1 lies in the subsquare (0,1/3)x(0,1/3), N+- * (X,Y) mod 1 lies in the subsquare (0,1/3)x(-1/3,0), N+- * (X,Y) mod 1 lies in the subsquare (-1/3,0)x(0,1/3), and N-- * (X,Y) mod 1 lies in the subsquare (-1/3,0)x(-1/3,0). We want a multiple in each quadrant, not too far from either axis. Let Nmax = max(N++,N+-,N-+,N--). (The multipliers Nxx are all >0.) List all multiples of (X,Y) (mod 1) up to Nmax*(X,Y) that fall in the four subsquares. Each subsquare has at least one multiple. Within each subsquare, select the multiple Mi that's "best". Probably we'll use the metric of max(abs(MX(mod 1)), abs(MY(mod 1))), choosing the point whose distance to the further axis is minimal. Other reasonable definitions of "best" are also possible. We've started with 1/3 as the worst error of our approximations, and we can shrink it down a little. We're assuming X and Y are irrational, so no multiple actually has a coordinate that's +-1/3 (mod 1). Reduce the size of the square accordingly to accommodate the actual best multiples. (All 4 subsquares must be the same size.) Discard any multiples that fall outside the reduced square; at least one multiple must still remain in each quadrant. As a side effect, we can produce a sequence of increasingly good approximations, for all multiples <=Nmax. Now I sketch an iterative step, which is repeated indefinitely, to increase Nmax while reducing the size of the square containing the good approximations. At each stage, the square contains all the good multipliers <=Nmax. We select the largest multiplier within each quadrant, and use the four corresponding multiples as base points. Let Nmin = minimum of the four multipliers. For each base point, try adding each good multiple (in all quadrants) to the base point. Keep any new multiple that's within the square. (There might be a lot, or maybe nothing new.) We now have a (probably larger) list of multiples that lie within the square, and is complete up to Nmax+Nmin. This becomes the new Nmax. We discard multiples larger than this limit; we'll refind them later. Now we try to shrink the square: within each quadrant, choose the best point; choose the worst of these four points; if this point is new, we can shrink the square to just include it. This will probably discard some multiples that fall outside the reduced square. This concludes the iterative step. The stopping rule is when some multiple is close enough to 0,0. Each step of the iteration is guaranteed to increase Nmax, but the increment could be tiny. There's no guarantee that an individual step will shrink the square, but the size must ultimately approach 0 since multiples of (X,Y) are dense[*] in the unit square. The practical problems of the algorithm are similar to using a subtraction algorithm to compute GCDs: You can get "nearly stuck", developing a lot of multiples that fit in the square but leave one quadrant making no progress. Perhaps there's a way to improve the method that's similar to using division for GCDs. The startup step can also be a problem. It's easy in the typical case. Some bad cases: if one of X,Y is small, say X=.0001..., then there are a lot of multiples of X to record before reaching .6666. [*] Also, the density argument fails when there's an integer relation between X and Y, when multiples of (X,Y) fall on a rational-slope line. So if X=pi-3 and Y=2X, no multiples of (X,Y) fall in the 2nd and 4th quadrants (mod 1, residues normalized to lie in (-.5,.5)). Rich rcs(a)cs.arizona.edu

1 0

Re: [math-fun] Fibonacci power triangle
by Dan Hoey 06 Jan '03

06 Jan '03

Richard Schroeppel <rcs(a)cs.arizona.edu> wrote: > The next diagonals turn out to be products of three adjacent > Fibs divided by 2: 260 = 5*8*13/2. > The right way to look at this seems to be 5*8*13/(1*1*2), a > kind of binomial coefficent with the regular integers replaced > by Fibonacci numbers. The next diagonals will be products of > four adjacent Fibs divided by 1*1*2*3, and so on. Neat! Would you like to call them Fibonomial coefficients, or is that too cute? I wonder if there's an analogue of the role of binomial coefficients in the expansion of (a+b)^n? Dan

1 0

[math-fun] Krantz review of Wolfram's book
by Richard Schroeppel 05 Jan '03

05 Jan '03

Salamin> The January 2003 issue of the Bulletin of the AMS has a review by Steven Krantz of "A new kind of science". I finally got around to reading Krantz's review of Wolfram's book. I found the review disappointing and uninformative. He makes a number of cheap-shot comments, and remarks that he's unprepared to talk about the meat of the book. Rich

1 0