April 2006 - mathfun@mailman.xmission.com

Re: [math-fun] Indoor sports: arctan relations
by Phil Carmody 12 Apr '06

12 Apr '06

From: Joerg Arndt <arndt(a)jjj.de> > > > You can generate ordinary integers in order, along with their prime > > > factorizations, using a priority-queue-like scheme. > > > > "Lenstra's Algorithm". By default doesn't give you the factorisations, > > but that part is trivial post facto. > > Dijkstra's algorithm (your follow-up). > Clueless me: > <cite http://en.wikipedia.org/wiki/Dijkstra's_algorithm> > Dijkstra's algorithm, named after its discoverer, Dutch computer > scientist Edsger Dijkstra, is an algorithm that solves the > single-source shortest path problem for a directed graph with > nonnegative edge weights. > </cite> > I do not see the connection, or is there other "Dijkstra's algorithm"s? Given my brain presently, it's entirely possible that it was neither Dijkstra nor Lenstra! It's a fresher algorithmics exercise, normally done with primes {2,3,5}. Seed the list with { 1 }, and point a 2-pointer, 3-pointer and 5-pointer at it. 1 ^^^ 235 Then compare the value of 2*[2-pointer], 3*[3-pointer] and 5*[5-pointer]. Select the smallest, append to the list, and advance the appropriate pointer: 1, 2 ^^ ^ 35 2 Now compare 4,3,5 select the smallest, append, update 1, 2, 3 ^ ^^ 5 23 Now compare 4,6,5, select the smallest, append, update 1, 2, 3, 4 ^ ^ ^ 5 3 2 Now compare 6,6,5 1, 2, 3, 4, 5, ^^ ^ 35 2 Now compare 6,6,10. Here we need to include some arbitration to handle the equality of 2*3 and 3*2. One can simply advance both pointers. 1, 2, 3, 4, 5, 6 ^ ^ ^ 5 3 2 Now compare 8,9,10 As you can see, the list grows faster than the pointers advance, which means that this algorithm is impractical for really huge tasks. > > > A similar method should work for X+i, using complex primes. > > > Unclear if it's any faster than just sieving large blocks of X+i. > > > > The set { x^2+1 } is so sparse that sieving just along that polynomial > > will be fairly fast. O(R^(1/2)). > > > > > Both methods are faster than factoring N (or X^2+1) one-at-a-time. > > > > But using Euler's factoring shortcut (the original block-GCD method), > > factoring is exceptionally fast. > > Can you give me a reference? Yup - but first $mypreviouspost =~ s/Euler/Euclid/; :-| Riesel PNaCMfF. Precompute the product of all the primes you are interested in, including conservative multiplicities. Then you just need to see if gcd(testnum,product)==testnum, or quicker and more simply product%testnum==0. However, due to both of the above missing extreme powers the slower test gcd(testnum,product)*primemax>testnum could be used. > I definitely want to learn about the method. > How long does it take for p<=761 and (10^7)^2? > Here are my figures: > mm=10^6; \\ 10^6 == 13 sec \\ 4620 > mm=10^7; \\ 10^7 == 131 sec \\ 8169 > mm=10^10; \\ 10^10 == \\ 37h > > Share that one-liner? No, problem. 'taint no rocket science. Precomputation of product: ? pr=2^9;forprime(p=3,761,if(p%4==1,pp=p;while(pp*p<761,pp*=p);pr*=pp)) Naive GCD: ? c=0;for(x=1,10^6,x2p1=x^2+1;if(gcd(pr,x2p1)==x2p1,print(x" "x2p1);c++));c time = 5,490 ms. 3919 Shortcut: ? for(x=1,10^6,x2p1=x^2+1;if(pr%x2p1,,print(x" "x2p1))) time = 3,610 ms. 3919 Catching higher multiplicities: ? c=0;for(x=1,10^6,x2p1=x^2+1;if(gcd(pr,x2p1)*768>=x2p1,print(x" "x2p1);c++));c time = 5,580 ms. 4568 Of course, one could simply crank up the powers in the prime product to catch some of the more extreme ones (every prime has one higher exponent here): ? pr=2^10;forprime(p=3,761,if(p%4==1,pp=p;while(pp<761,pp*=p);pr*=pp)) ? c=0;for(x=1,10^6,x2p1=x^2+1;if(pr%x2p1,,print(x" "x2p1);c++));c time = 4,580 ms. 4563 Combining both safety nets: ? c=0;for(x=1,10^6,x2p1=x^2+1;if(gcd(pr,x2p1)*768>=x2p1,print(x" "x2p1);c++));c time = 6,510 ms. 4618 All times on a 2GHz Athlon. > > > Both methods adapt to ignoring large prime divisors, just keeping those > > > up to some limit. > > > > Lenstra's method is defined in those terms. > > Alas it's something like O(f(R)*#p) for f(R)=o(R) by default - the larger > your > > set, the more collisions you have, and the more time you spend hopping down > > lists trying to find the right place to insert values. So it tends to slow > down > > for large sets of divisors, and may take a while before the > > smoothness-contraint causes the unspecified o(R) to become preferable to > the > > square+1 constraint's O(R^(1/2)). > > > > I have a 'Lenstra Engine' somewhere - if someone wants me to perform some > > actual hunts for smooth numbers with it, just let me know the details, and > I'll > > get a spare machine onto it immmediately. > > Here! I can mail, or stick on my website, or both, the source. It seems to go bang and run out of memory for the kinds of huge jobs you're looking at. > Another one I though about: > For all small primes P compute the square roots of minus one > mod P, mod P^2, mod P^3, etc. > Do sieving as follows: Multiplication is barely slower than addition nowadays, so you might as well just accumulate the full values, and not bother with logs. Sure, RAM is thrashed more, but that just means you need to optimise memory access rather than optimise maths. Whoever mentioned the divide and conquer method ('twas Richard, I'm sure) had the right solution for large jobs. DJB's sortedsums has the core code required. Phil () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

Re: [math-fun] high school mathematics
by Henry Baker 12 Apr '06

12 Apr '06

Mathematicians obviously know nothing (nil?) about natural numbers. :-) Amer Math Monthly has a picture of the Fields Medal, which has the date MCNXXXIII, which mistakenly uses "N" instead of "M". Apparently, all 44 awarded medals have this same error. Perhaps all of you should check your medals for this flaw. A non-mathematician, Alan Chodos of the American Physical Society noticed that: "There could also be a danger to teaching too much math. In many states, the proceeds from the lottery go to education. If you teach people about probability, they'll be much less likely to play the lottery. So paradoxically, the better you teach math, the less funding you may have to teach it." Math. Magazine, April 2006. At 09:22 AM 4/12/2006, Schroeppel, Richard wrote: >A note from Dylan Thurston <dthurston(a)barnard.edu>: >----- > >My favorite example is even earlier: in elementary school or middle >school, we were learning about the "natural", "counting", and "whole" >numbers. (These are varieties of positive/nonnegative integers.) I had >a little trouble keeping them straight, and so I asked my father (also a >mathematician) which was which. He didn't know and said he used >"positive" or "nonnegative"; that made me think something was fishy. >I don't think mathematicians are consistent about whether the natural >numbers (N) include 0 or not; I suspect this occassionally leads to >confusion. >Peace, > Dylan

1 0

Re: [math-fun] high school mathematics
by Schroeppel, Richard 12 Apr '06

12 Apr '06

A note from Dylan Thurston <dthurston(a)barnard.edu>: ----- My favorite example is even earlier: in elementary school or middle school, we were learning about the "natural", "counting", and "whole" numbers. (These are varieties of positive/nonnegative integers.) I had a little trouble keeping them straight, and so I asked my father (also a mathematician) which was which. He didn't know and said he used "positive" or "nonnegative"; that made me think something was fishy. I don't think mathematicians are consistent about whether the natural numbers (N) include 0 or not; I suspect this occassionally leads to confusion. Peace, Dylan

1 0

[math-fun] Handy dandy metric hypervolume conversion formula
by R. William Gosper 12 Apr '06

12 Apr '06

(c8) (4*floz*in/3,%%=uconv(%%,liter*mm)) 4 20031137357 (d8) - floz in = ----------- liter mm 3 20000000000 I.e., the moment of a fluidounce of stuff at 4" = the moment of a liter of it at 3 mm, to < .16%. (Can *your* units converter make liter*mm? Mine is free for the asking, but needs Macsyma or Maxima (maybe. The latter seems to be mutating.)) --rwg If you can handle AROMATIC MACROTIA, accept that TROPOSPHERIC PROSECTORSHIP and PRAISE GOD POSIGRADE, in keeping with DEASIL IDEALS.

3 3

[math-fun] $mypost =~ s/Len/Dijk/g;
by Phil Carmody 12 Apr '06

12 Apr '06

I was of course thinking of "Dijkstra's algorithm". () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

[math-fun] Choosing a grad school (for PhD in math)
by Jesse L. Liptrap 12 Apr '06

12 Apr '06

I'm a senior at Caltech, and this is my week to choose a grad school. Right now my interest lies mainly in geometry and topology, but I suppose it could shift. My options include UC Davis and the University of Southern California, and possibly will include UC Santa Barbara, CUNY, and Rutgers. Any advice or thoughts? thanks, Jesse Liptrap "Mathematics is music for the mind; music is mathematics for the soul."

1 0

Re: [math-fun] Indoor sports: arctan relations
by Marc LeBrun 11 Apr '06

11 Apr '06

>>=Joerg >> A future computation would require a better algorithm >> to compute all numbers X so that (X^2+1) is smooth. >=Dan > Would someone kindly explain to me what this sentence means? > I haven't the foggiest idea. http://mathworld.wolfram.com/SmoothNumber.html (and see also the See Also links) "Smooth" is like the familiar idea of a "round" number (which RCS advocated as an alternative nomenclature here) I haven't been tracking this thread closely, but in context it seems he wants an algorithm using some pool of candidates {X | isSmooth(X^2+1)} or the like.

1 0

Re: [math-fun] Indoor sports: arctan relations
by dasimov＠earthlink.net 11 Apr '06

11 Apr '06

Joerg writes: << . . . A future computation would require a better algorithm to compute all numbers X so that (X^2+1) is smooth. . . . >> Would someone kindly explain to me what this sentence means? I haven't the foggiest idea. Thanks. --Dan

1 0

[math-fun] placebos
by James Propp 11 Apr '06

11 Apr '06

I'll be teaching about the placebo effect in my quantitative reasoning class later today, and I just remembered having read a year or two ago about a study that claimed to actually disprove the existence of the effect. Do any of you remember this? What is the current scientific consensus about the study? Assuming that the placebo effect is as real as I've always heard it is, I'm also curious whether research on the placebo effect has included variants such as ones where the experimenter tells the subject "The pill I'm giving you is a placebo ...". (There are a variety of ways the explanation could be continued, such as: "There's no reason for it to work, but placebos seem to work, at least for people who think that they're real drugs, and we're trying to see whether the element of conscious deception is required; maybe it's enough to fool the parts of your mind that commune with your immune system." or (less honestly) "A recent study shows that placebos work even for people who know that they're taking placebos; we're just trying to replicate that study, although we're scientifically 100% certain that the study was correct." It would be interesting to know how the effects of such differing scenarios compare.) I myself was in the habit of taking echinacea for most of the '90s, and I made a conscious effort to maximize the placebo effect by trying to convince myself that if I could only convince myself that the capsules were likely to work, they'd be likely to work. But they didn't have any noticeable impact on my colds, and then I read a study that questioned their value, so I stopped taking them. (Of course, the fact that I could be so swayed by a mere *study* explains why echinacea never worked for me: obviously, I hadn't believed in it enough to begin with. :-) ) Jim Propp

2 1

[math-fun] Re: Handy dandy metric hypervolume conversion
by Phil Carmody 11 Apr '06

11 Apr '06

From: "R. William Gosper" <rwg(a)osots.com> > I.e., the moment of a fluidounce of stuff at 4" = the moment of > a liter of it at 3 mm, to < .16%. (Can *your* units converter > make liter*mm? Mine is free for the asking, but needs Macsyma > or Maxima (maybe. The latter seems to be mutating.)) http://www.google.fi/search?q=4+fluid+ounce+inches+in+liter+millimeters 4 (US fluid ounce inches) = 3.00467062 liter millimeters Phil () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

2 1