July 2003 - mathfun@mailman.xmission.com

RE: [math-fun] Prime Testing technology
by Schroeppel, Richard 15 Jul '03

15 Jul '03

There is a small prize offered for a number that is a pseudoprime base 2 and also a Lucas PSP. Probably the first examples will have many prime factors. The Carmichael numbers will usually be PSP base 2 and 3. There are an infinite number of them. I don't know the situation if we strengthen the requirement to MR-PSP. Richard Pinch has produced a list of PSP2s < 10^16; this would be a good starting point for trying out tests. We can decide if a number has >1 prime factor (i.e., it's composite). But we have no good way to show >2 prime factors. We can do it for some numbers by finding a factor F and showing either F or N/F is composite. Rich -----Original Message----- From: Michael Kleber [mailto:kleber@brandeis.edu] Sent: Tuesday, July 15, 2003 8:31 AM To: math-fun Subject: Re: [math-fun] Prime Testing technology Following up my previous mail, > Timing[PrimeQ[(32*10^6959 - 23)/99]] > {198.245 Second, True} > > The above is from a Mathematica run.[...] From the Mathematica implementation details at http://documents.wolfram.com/v5/TheMathematicaBook/MathematicaReferenceGuide / SomeNotesOnInternalImplementation/A.9.4.html --------- * PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test. * As of 1997, this procedure is known to be correct only for n < 10^16, and it is conceivable that for larger n it could claim a composite number to be prime. * The package NumberTheory`PrimeQ` contains a much slower algorithm which has been proved correct for all . It can return an explicit certificate of primality. --------- I had been under the mistaken impression that Mma's Miller- Rabin at least used (pseudo)random bases for PrimeQ. Since the algorithm is deterministic, there is (almost certainly, ie unless there's a big theorem about prime numbers waiting to be discovered) a well-defined "smallest n which Mma incorrectly claims is prime." Does anyone here know enough to estimate its size? (Or what its prime factorization is likely to look like? i.e. must all pq fail M-R for base 2 or 3?) --Michael Kleber kleber(a)brandeis.edu _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

Re: [math-fun] Lunar occultation of Mars
by Henry Baker 15 Jul '03

15 Jul '03

Yes, a friend from NASA tells me that due to the closeness, the new Mars probes will take only 6 months to get there. I guess that we missed one of the best chances to get men to Mars for quite a while. At 01:31 PM 7/14/03 -0700, Eugene Salamin wrote: > >Mars is approaching opposition in late August, and this will be its >closest approach to Earth in human history. Already it is very bright >in the night sky. At its peak, Mars will be magnitude -2.9 and 25.1" >diameter.

2 1

[math-fun] Prime Testing technology
by Richard Schroeppel 15 Jul '03

15 Jul '03

I think this is a size record for verifying a prime with a generic method (that doesn't use any special form information about the number). The number tested has 6959 digits (23116 bits). The test took 1.5 years. The first 25% of the elapsed time reduced the size of the number being checked by 8%. ECPP can be helped by parallelism. The most important reduction is to find D values such that P (or 4P) = X^2 + D Y^2, and then one of P+1+-2X (or +-X) can be factored as small-stuff * Q. Q is a somewhat smaller prime than P. Finding the D values can be parallelized, and factoring the P+1+xxx can also be parallelized. Rich ---------------------- From: Hans Rosenthal <hans.rosenthal(a)t-online.de> Subject: ECPP record: (32*10^6959-23)/99 proven prime with Primo To: NMBRTHRY(a)LISTSERV.NODAK.EDU I would like to inform you that I have certified the primality of (32*10^6959-23)/99, a smoothly undulating palindromic prime (SUPP) [1] having 6959 decimal digits, with the program Primo [2], Marcel Martin's implementation of the elliptic curve primality proving (ECPP) algorithm. The Primo certificate of primality is available at http://www.ellipsa.net/primo/ecpp6959.zip (4457 KB) The certification of this ordinary prime was started on 21 January 2002 with Primo 1.1.0 (tests 1 to 47) and completed on 7 July 2003 with Primo 2.0.0 (tests 48 to 953) on an AMD Athlon 1.4 GHz. There was one relevant interruption of the certification process from 29 March 2003, 6:47, until 3 April 2003, 22:45. So the total running time amounts to approximately 527 days. There is a kind of ECPP diary of the certification progress available, which was started on 9 June 2002 at 21310 (of 23116) bits (so it is not complete). This diary can be found at http://www.ellipsa.net/primo/ecpp6959_diary.txt (9 KB) I thank Marcel Martin for his help and advice, and most of all, for making the ECPP algorithm available to the world of PC users in the most comfortable form I can imagine: his marvellous Primo. Hans Rosenthal [1] http://www.worldofnumbers.com/undulat.htm# [2] http://www.ellipsa.net/primo/record.html

3 3

[math-fun] Lunar occultation of Mars
by Eugene Salamin 14 Jul '03

14 Jul '03

There will be close approach of the Moon to Mars on the night of July 16-17, and for observers in the southern tip of Florida, the Carribean, and southern Mexico to northwestern South America, it will be an occultation. Local times range from midnight on the West coast to 5 AM in the eastern US. The graze line runs SW to NE through Florida from Ft. Meyers, north of Lake Okeechobee, to Sebastian. Mars will have magnitude -1.9 at the time. Poke around http://www.skyandtelescope.com for more details. Mars is approaching opposition in late August, and this will be its closest approach to Earth in human history. Already it is very bright in the night sky. At its peak, Mars will be magnitude -2.9 and 25.1" diameter. __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com

1 0

Re: [math-fun] Marilyn Vos Savant again ?????
by Dan Hoey 14 Jul '03

14 Jul '03

"Bernie Cosell" <bernie(a)fantasyfarm.com> wrote: > Right, and just to summarize here: it seems to be identical with the > Monty Hall problem, EXCEPT: that the instructor informed the > students of a wrong-choice on the exam *without* knowing which > choice the student had made. The question addressed is whether the > instructor's 'revelation' being random, rather than knowingly NOT > selecting the one the player/student chose, affects the odds. Just to be complete, I should say that the instructor informed the students that choice C was wrong. The question was asked from the standpoint of a student who initially answered A. Of course, the students who chose C should change their answer, just as when Monty Hall shows you a goat behind the door you picked, and asks you if you want to switch. In case that's too hard to figure, he could show you the car behind a door you didn't pick and ask you if you want to switch. Of course, MvS is still is ignoring the case where the host doesn't always give the contestant a chance to switch. Dan

1 0

Re: [math-fun] Marilyn Vos Savant again ?????
by Dan Hoey 14 Jul '03

14 Jul '03

Dan Asimov wrote: > The world's smartest human has posted a probability problem, and her > answer to it, on this webpage > <http://www.parade.com/current/columns/askmarilyn.html>. That URL demanded cookies and a zip code, which I am not inclined to supply. BUt it also included a pointer to a "text-only page", <http://local.parade.com/> , which has a "fascinating new probability problem about a student taking a test" buried in a bunch of ... other material. Dan Hoey(a)AIC.NRL.Navy.Mil

2 1

[math-fun] Marilyn Vos Savant again ?????
by asimovd＠aol.com 14 Jul '03

14 Jul '03

The world's smartest human has posted a probability problem, and her answer to it, on this webpage <http://www.parade.com/current/columns/askmarilyn.html>. I have already decided what my take is on the problem, which resembles the Monty Hall problem (which itself is referred to on that webpage), but I'll wait to hear what others have to say before prejudicing y'all with my answer. --Dan

1 0

Re: [math-fun] circular discs in corners
by asimovd＠aol.com 12 Jul '03

12 Jul '03

Apropos this problem, suppose we're given any triangle T and its incircle C. C is tangent at 3 points of T = T_1, which we take as vertices of a new triangle T_2. Etc. If this procedure is repeated infinitely many times, the T_k's seem to converge to a single point P = P(T). Is this a well-known "triangle center", and if so what is it called and what are some of its known properties? Assuming this sequence always converges to a point, then in the unlikely event no one has named it yet, I propose calling it the "ultracenter" of T. --Dan

1 0

Re: [math-fun] matrix exp
by asimovd＠aol.com 11 Jul '03

11 Jul '03

Shel asks: << Is anyone's symbolic math package able to take the matrix exponential of [ 0 a 0 -d ] [ -a 0 b 0 ] [ 0 -b 0 c ] [ d 0 -c 0 ] >> I think this can be done pretty easily by hand. Any matrix M has to satisfy its characteristic equation P(x) = det(xI - M) = 0, where P is a polynomial of deg = 4. If you write down the first few terms of the series for exp(M), its easy to see how to use P(M) = 0 to express all M^k for k >= 4 in terms of powers of M no greater than the cube. This will yield exp(M) = aI + bM + cM^2 + dM^3, the only problem being that a,b,c,d will be infinite series. (For the skew-symmetric matrix above, though, I expect the series will be familiar ones for simple expressions using well-known analytic functions.) Of course its exp will be a 4D rotation matrix if a,b,c,d are real. Eigenvalues and eigenvectors should be even easier, since each eigenvector of M with eigenvalue lambda is an eigenvector of exp(M) with eigenvalue exp(lambda). Counting multiplicity I think these constitute all eigenvectors of exp(M). --Dan

1 0

Re: [math-fun] circular discs in corners
by Dan Hoey 11 Jul '03

11 Jul '03

About my remark that > > any way you lean a disc of radius r on the floor against two > > walls, the center will be sqrt(2)r from the corner. Henry Baker <hbaker1(a)pipeline.com> says: > You are absolutely right! I checked this using a symbolic algebra > package on the plane to Boston today. From one of my previous > forays, I already had a good method for finding the incenter of a > circle in 3D, so I found the incenter of the triangle (x,0,0), > (0,y,0), (0,0,z). I then found the distance^2 to the origin. I then > divided by the radius^2 of the incircle, and voila'! The ratio is > exactly _2_ ! Taking the square root, we get a ratio of sqrt(2) for > the ratio of the distance to the radius, as you point out. Well, that is even more startling, because it's a solution to a different problem! Your calculation is of a disc supported by three perpendicular lines; mine is of a disc supported by three perpendicular planes. Does this mean what I suspect it means--that if you support the disc on three perpendicular planes, the lines from the points of tangency to the origin must be mutually perpendicular? I'm becoming motivated to make sure I get this solved, just to verify that conjecture. > A man in the street could understand this -- nail one end of a > string into a corner of a room. Take a large circular table with a > small hole in the center, and put the string through the center. > Now push the table into the corner, and pull the string taut. You > can move the table around -- up to and including flat against one > wall, and you won't break the string, and the string won't become > slack either! I thought of a gadget something like that, only with a rigid strut holding the disc center to the corner. Then you don't have to watch it to know it doesn't go loose. Of course, neither of these tethers lets you turn the disc over, as you can in theory. (If the above plane-support=line=support conjecture is true, then you could also mount a tripod of perpendicular struts from the corner so that they meet the disc at the points of tangency.) I wonder if this linkage has any useful qualities as a somewhat universal joint? Say one that provides heavy-duty support (from the disc resting on the planes) and light-duty tension (from the strut). The strut can be connected with ball-and-socket joints on both ends, since it isn't subjected to great force. I don't know if there's a better way to support the disc than with sliding edges. If the planes are backed off, a carriage could be inserted that slides on the plane and accepts the disc in a groove. Optionally, a hole through the carriage could maintain alignment with the tripod leg, if that conjecture works out. This would be interesting just to watch. Meanwhile, I'm still trying to solve the original problem (which is the key to all the other stuff.) I looked at the two-dimensional problem to see if I could get anywhere. I think I've seen rectangles inscribed in rectangles before, but I'm not sure where, so I worked on it from scratch. Anyway, for an a x b rectangle is inscribed in a c x d rectangle, I get 0 = (a^2 - b^2)^2 - (ad - be)^2 - (ae - bd)^2 which means solving a quartic (unless I've overlooked some simplication.) (I find it interesting that this equation can also be written 0 = (a^2 - b^2)^2 - (a^2 + b^2) (d^2 + e^2) + 4 abde which is only quadratic in the reparameterization of the rectangles from (width,length) to (hypotenuse squared,area). And then the two kinds of parameters are nicely segregated from each other, though the a^2b^2 term is of ambiguous kind.) I still haven't worked out a way of using this to solve the three-dimensional problem. Dan Hoey(a)AIC.NRL.Navy.Mil

2 1