May 2004 - mathfun@mailman.xmission.com

[math-fun] Mersenne Composites
by Richard Schroeppel 24 May '04

24 May '04

GuyH> Somewhat to my surprise, I seem to have been the discoverer since 1983 > of the largest known composite M(p), namely M(M(31)). DJR: Ah yes, it's divisible by 295257526626031. > Amazing what you could do with an evening's mainframe idle time and a > short program in bc. DJR: Today's tools are better: 72280004994623 | M(M(31)+12) <...> Hardy & Wright mention that if P = 3(mod4) and Q = 2P+1 are both prime, then Q | 2^P - 1. This is because Q = 7(mod8), so 2 is a quadratic residue of Q, so 2^((Q-1)/2) = 1 (mod Q). Smallest example is 7 | M3, and smallest example that factors the Mp is 23 | M11 = 2047 = 23*89. I don't know if Fermat ever mentioned this explicitly in his letters, but he knew the small examples. I think Guy meant to claim he found the largest (known) Mersenne prime MP such that MMP is composite. As Don's arithmetic shows, it's very easy to find P such that MP is composite. In fact, the prime moduli that we recommend for the IPSEC/IKE/OAKLEY key exchange algorithm (courtesy of Messers Diffie and Hellman) are Sophie Germain primes (actually the Q=2P+1) that are 7(mod 8), and, by the H&W theorem, they provide very large primes P such that MP has a known divisor Q=2P+1. I computed Qs just a tad under 2^768, 2^1024, and 2^1536, and other people have continued at least to 2^2048. Rich rcs(a)cs.arizona.edu

1 0

RE: [math-fun] Re Mersenne Numbers
by Schroeppel, Richard 24 May '04

24 May '04

I think I've seen a small net-project to look for factors of MM61. Presumably they are trying possible "small" divisors, (8k+0,2) * M61 + 1, with a bit of sieving thrown in. In other news, George Woltman reports that the new candidate Mp passed the preliminary check (repeating the tail end of the LL calculation). I assume a couple of machines are somewhere beavering away on the full check. The "new" number is apparently < 10^10^7, so p<33.2M. Rich -----Original Message----- From: Guy Haworth To: math-fun(a)mailman.xmission.com Sent: 5/22/2004 4:53 PM Subject: [math-fun] Re Mersenne Numbers Far too much interest in prime M(p). Composite M(p) - that's where the future is - more of them. Somewhat to my surprise, I seem to have been the discoverer since 1983 of the largest known composite M(p), namely M(M(31)). That's 21 years - and you've got no chance of that if you go chasing prime M(p). And all without the aid of gymnasia or fancy drugs. Amazing what you could do with an evening's mainframe idle time and a short program in bc. Of course, I could be wrong: if so, do let me know. Guy :-) _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] Re Mersenne Numbers
by Guy Haworth 22 May '04

22 May '04

Far too much interest in prime M(p). Composite M(p) - that's where the future is - more of them. Somewhat to my surprise, I seem to have been the discoverer since 1983 of the largest known composite M(p), namely M(M(31)). That's 21 years - and you've got no chance of that if you go chasing prime M(p). And all without the aid of gymnasia or fancy drugs. Amazing what you could do with an evening's mainframe idle time and a short program in bc. Of course, I could be wrong: if so, do let me know. Guy :-)

1 0

[math-fun] Division rings?
by Richard Guy 21 May '04

21 May '04

No, the title's been used already. So let's say `divisor necklaces' arising from the divisor chains which we were talking about a little while ago. Is it possible to arrange the numbers from 1 to n in a cycle, so that each is a divisor of the sum of the previous k members? There's a trivial example with n = 3 and k = 2, but I haven't found others. Is this because they don't exist, or is it just my incompetence? R.

2 5

[math-fun] onion of revolution?
by Marc LeBrun 17 May '04

17 May '04

Hold one end of a long string of beads and get it twirling around a vertical axis with a vigorous stirring motion (like in some cowboy lasso tricks, but without the noose loop). As the speed increases the middle of the string pulls outward, drawing the lower end up, until the bottom part looks horizontal. Since the top is basically fixed it makes a cusp, and overall the profile the whole string traces in the air is shaped something like an onion, oriented cusp-up, like the Mogul-style onion domes seen on many buildings. At high speeds the string gets sharply bent, like a hairpin. Can you give an expression describing the "onion curve" the string forms at a given speed? What path does the string's bottom end trace as a function of the speed of rotation?

3 2

[math-fun] lego robot solves rubik's cube
by Chris Landauer 17 May '04

17 May '04

------- Forwarded Message From: Brian Behlendorf <brian(a)collab.net> Date: Mon, 17 May 2004 13:08:31 -0700 (PDT) As a friend said, "this raises the bar." http://jpbrown.i8.com/cubesolver.html Brian ------- End of Forwarded Message

1 0

[math-fun] possible new Mersenne prime
by Richard Schroeppel 15 May '04

15 May '04

The GIMPS project has another report of a new Mersenne prime. If confirmed, this would be the 41st known. George Woltman is doing some preliminary checking to exclude the type of false report that happened a few months ago. After that, the full check takes a couple of weeks. The full check involves rerunning the Lucas-Lehmer test on different hardware and software. The preliminary check just rechecks the last few thousand steps in the LL test, rerunning from a saved intermediate residue. The recent false report is believed to have been caused by a "just at the wrong time" hardware failure, creating an accidental 0 residue. Rerunning the last few LL steps excludes this case. Rich rcs(a)cs.arizona.edu

1 0

RE: [math-fun] FW: funny limit to well known Generating Function
by Meeussen Wouter (bkarnd) 07 May '04

07 May '04

Ah, the 'real' rwg stood up. My Respects, Sir! The following generalisation pops up in my mind: ... can an algorithm be described that similarly simplifies any ratio of two (order n)polynomes, given that their coefficients of x^k in numerator and denominator are (* of closed form *) :: replace (* .. *) with "a non-recursive expression of n and k" as needed. Or will it always remain a job to be done by hand & eye? Application (for the mathematicaly underprivileged): There are loads of sequences whose GF can be approached by such f_n(x)/g_n(x) ratios. They occur as (I - x A)^-1 where I is the appropriate Identity matrix, and A is a substitution matrix symbolising for example (in the case at hand) the substitution game k->(1,2,...,k,k+1) that generates the Catalans. > -----Original Message----- > From: R. William Gosper [mailto:rwg@tc.spnet.com] > Sent: vrijdag 7 mei 2004 7:27 > To: math-fun(a)mailman.xmission.com > Subject: Re: [math-fun] FW: funny limit to well known Generating > Function > > > Wouter asked > >> f[x_] := Sum[(-1)^(n-j) Binomial[j,n-j] x^(n-j),{j,1,n}] / > Sum[(-1)^(n+2-j) Binomial[j,n+2-j] > >x^(n+2-j),{j,1,n+2}] > >> produces a well known Generating Function for the limit > n->Infinity. > > >> Q: What is needed to force Limit[f[x], n->Infinity] into > submission? > >> it equals (1-2x - Sqrt[1 - 4*x]) / (2 x^2) > > > >> Mathematica's package Calculus`Limit` doesn't feel like > tackling it. > >> Should it? > > and I blathered > > >Both Mma and Macsyma need a little help here. Just send the > sum limits > >to infinity first. It might also help to start from j=0, > which you may > >have intended. If not, Mma may need you to "manually" > subtract the j=0 > >term. Then you can even start from j=-inf. The resulting > sums are simple > >algebraics(n), and n->inf is a snap. > > Bull. This isn't even a limit problem. But it exposes > several defects > in my personally enhanced Macsyma. All that should have been > necessary > was (declare(n,integer), hypersimp(sum(...))). Instead, I have to > sum from floor(n/2) instead of 1: > (c225) > (declare(n,integer),sum((-1)^(n-j)*binomial(j,n-j)*x^(n-j),j,f > loor(n/2),n) > /sum((-1)^(n+2-j)*binomial(j,n+2-j)*x^(n+2-j),j,floor(n/2),n+2)) > > n > ==== > \ n + j n - j > > binomial(j, n - j) (- 1) x > / > ==== > n > j = floor(-) > 2 > (d225) --------------------------------------------------------- > n + 2 > ==== > \ n + j n - j + 2 > > binomial(j, n - j + 2) (- 1) x > / > ==== > n > j = floor(-) > 2 > > then manually reverse the summation direction, > (c226) rangereverse(%) > > n > floor(-) - 1 > 2 > ==== > \ n + j n - j > > binomial(j, n - j) (- 1) x > / > ==== > j = n + 1 > (d226) --------------------------------------------------------- > n > floor(-) - 1 > 2 > ==== > \ n + j n - j + 2 > > binomial(j, n - j + 2) (- 1) x > / > ==== > j = n + 3 > > and then manually change the summation variable: > (c227) linchange(%,n+1-j) > > n > n - floor(-) > 2 > ==== j > \ binomial(n - j, j) x > > (- ---------------------) > / j > ==== (- 1) > j = 0 > (d227) ---------------------------------------------- > n > n - floor(-) > 2 > ==== j + 2 > \ binomial(n - j, j + 2) x > > (- -----------------------------) > / j > ==== (- 1) > j = - 2 > > Finally, > (c228) hypersimp(%) > > 4 > (d228) -------------------- > 2 > (sqrt(1 - 4 x) + 1) > > I assume this is the square of what you'd have gotten with f(n)/f(n+1) > instead of f(n)/f(n+2). > --rwg > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

1 0

[math-fun] FW: funny limit to well known Generating Function
by Meeussen Wouter (bkarnd) 06 May '04

06 May '04

> hi all, > > (I tried to send this to rwg(a)tc.spnet.com but it bounced. Bill, where are you?) > > > f[x_] := Sum[(-1)^(n-j) Binomial[j,n-j] x^(n-j),{j,1,n}] / Sum[(-1)^(n+2-j) Binomial[j,n+2-j] x^(n+2-j),{j,1,n+2}] > produces a well known Generating Function for the limit n->Infinity. > > Q: What is needed to force Limit[f[x], n->Infinity] into submission? > it equals (1-2x - Sqrt[1 - 4*x]) / (2 x^2) > > Mathematica's package Calculus`Limit` doesn't feel like tackling it. > Should it? > > > Wouter. =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

3 3

[math-fun] Re: From Dan Asimov to Richard re: Divisor chains
by Richard Guy 05 May '04

05 May '04

Dan raises a question which has already been anticipated by some funsters. Many of you will now have several definitions. I (&/or Paul Vaderlind) originally meant `chain of order n beginning with n', but others have noted that they could begin with any number > 1. There is a question about `cyclic' chains (necklaces?). These have been defined as those whose first member divides n(n+1)/2, though that seems even more artificial. No chain can be truly cyclic, though one can ask for chains, or even necklaces, in which each member divides the sum of the previous k members. This is not possible for k = 1 or 2 [except for 4 2 3 1 -- which won't quite make a necklace, 'cos 2 doesn't divide 4+1], but perhaps for some larger k ? [for the first k members, `divisor of sum of all previous members'] Example of chain or necklace, or proof of impossibility ? R. On Tue, 4 May 2004, Daniel Asimov wrote: > Richard, [snip] > Do you mean to define a divisor chain or order n as necessarily > beginning with n ??? > > (That may lead to a trickier class of questions, but it seems a > bit artificial as a definition.) [snip] > > Dan Asimov > Visiting Scholar > Math Dept. > Univ. of Calif. > Berkeley, California > (510) 524-7789 >

1 0