June 2003 - mathfun@mailman.xmission.com

RE: [math-fun] a prime in each row?
by Meeussen Wouter (bkarnd) 10 Jun '03

10 Jun '03

replying to myself :: netiquette for dummies. I thought that c=1/2 in a(n+1)=a(n)+a(n)^c was somewhat magical, in the sense that it's as low as you can go without primeless intervals ** at big n ** Some simple observational math (ahum) has changed my mind. Even sticking to the a(n+1)=Floor[a(n)+a(n)^c] with c=1/E=~ 0.37 shows the cloud rising from the 0-line: at n=10000, I have between 4 and 20 primes per interval, and rising. The last zero (primeless interval) was at n=1132, and the last 1 (mono-prime interval) at n=5296. Substituting Li[n] for PrimePi[n] gives an indication: density in the 'Conway intervals' with c=1/E rises with about 7 per 10000 at n=10000. Question: what value of c (or what interval definition other than n+n^c) would make its prime-density non-increasing? An interval of size 1/Li(n), no? Ah, meddling in matters way above my head again. This only serves to illuminate how big the gap is between the pro's and the computationally-endowed-but-otherwise-illiterate mainstream down here. just smile now, Wouter. -----Original Message----- From: Meeussen Wouter (bkarnd) [mailto:wouter.meeussen@vandemoortele.com] Sent: dinsdag 10 juni 2003 14:07 To: 'math-fun' Subject: RE: [math-fun] a prime in each row? since nesting n+n^(1/2) on 1 produces A002984,(a(n) = a(n-1)+[sqrt a(n-1)]) and changing floor to ceiling, we get A002620 (a(n) = Floor[n^2 /4] ), we should count primes in intervals from Floor[n^2 /4] to Floor[(n+1)^2 /4] giving, I recon : {0, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 1, 4, 1, 2, 2, 2, 3, 3, 2, 2, 2, 4, 2, 4, 3, 1, 4, 2, 4, 3, 3, 3, 4, 4, 3, 4, 3, 2, 4, 4, 5, 4, 4, 4, 3, 4, 4, 4, 5, 4, 4, 4, 4, 5, 5, 5, 4, 6, 4, 4, 5, 5, 5, 7, 2, 3, 6, 6, 6, 6, 5, 8, 4, 5, 6, 5, 4, 7, 5, 4, 7, 6, 7, 7, 3, 6, 7, ... (not yet EIS) de amatoribus nihil sed bonum. W. -----Original Message----- From: John Conway [mailto:conway@Math.Princeton.EDU] Sent: donderdag 5 juni 2003 17:07 To: math-fun Subject: Re: [math-fun] a prime in each row? On Thu, 5 Jun 2003 asimovd(a)aol.com wrote: > David Wilson writes: > > << > Propp's conjecture* would imply a prime between n^2 and (n+1)^2, > which conjecture I believe is stil outstanding. > > Question: > Where does the conjectural territory first begin? [2n+1,3n] ? [3n+1,4n] ? > Etc. > > --Dan > All of these are fine - we know for any positive epsilon that there's a prime between n and n(1+epsilon) for all sufficiently large n (and explicit bounds can be given for how large n need be). The right question to ask is for which c there's necessarily a prime between n and n + n^c (for all sufficiently large n). The Riemann hypothesis would tell us that this is true for any c > 1/2. Ingham proved it for c = 3/5, remarking that his methods would give a strictly smaller number, and later people have explicitly produced values that are strictly smaller, but not by very much. John conway _______________________________________________ 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. _______________________________________________ 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.

2 1

[math-fun] Primes in a square
by David Wilson 10 Jun '03

10 Jun '03

Sorry if this has all been covered, but: The existence of a prime in every row of the n x n square of lexically ordered numbers 1 through n^2 follows if the largest run of composites on [1, n^2] is less than n. Empirically, this seems to be true for all n > 2 except n = 12 or 13, in which case there is the run of 13 nonprimes [114, 126] on [1, n^2]. I was hoping that there might be some useful asymptotics on prime gaps, specifically, I was hoping that the size of prime gaps near n were known to be less than O(sqrt(n)), but reflection tells me that this is probably not known, otherwise we would have a prime between n^2 and (n+1)^2 for sufficient n. Wild goose chase, oh well.

1 0

RE: [math-fun] a prime in each row?
by Meeussen Wouter (bkarnd) 10 Jun '03

10 Jun '03

since nesting n+n^(1/2) on 1 produces A002984,(a(n) = a(n-1)+[sqrt a(n-1)]) and changing floor to ceiling, we get A002620 (a(n) = Floor[n^2 /4] ), we should count primes in intervals from Floor[n^2 /4] to Floor[(n+1)^2 /4] giving, I recon : {0, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 1, 4, 1, 2, 2, 2, 3, 3, 2, 2, 2, 4, 2, 4, 3, 1, 4, 2, 4, 3, 3, 3, 4, 4, 3, 4, 3, 2, 4, 4, 5, 4, 4, 4, 3, 4, 4, 4, 5, 4, 4, 4, 4, 5, 5, 5, 4, 6, 4, 4, 5, 5, 5, 7, 2, 3, 6, 6, 6, 6, 5, 8, 4, 5, 6, 5, 4, 7, 5, 4, 7, 6, 7, 7, 3, 6, 7, ... (not yet EIS) de amatoribus nihil sed bonum. W. -----Original Message----- From: John Conway [mailto:conway@Math.Princeton.EDU] Sent: donderdag 5 juni 2003 17:07 To: math-fun Subject: Re: [math-fun] a prime in each row? On Thu, 5 Jun 2003 asimovd(a)aol.com wrote: > David Wilson writes: > > << > Propp's conjecture* would imply a prime between n^2 and (n+1)^2, > which conjecture I believe is stil outstanding. > > Question: > Where does the conjectural territory first begin? [2n+1,3n] ? [3n+1,4n] ? > Etc. > > --Dan > All of these are fine - we know for any positive epsilon that there's a prime between n and n(1+epsilon) for all sufficiently large n (and explicit bounds can be given for how large n need be). The right question to ask is for which c there's necessarily a prime between n and n + n^c (for all sufficiently large n). The Riemann hypothesis would tell us that this is true for any c > 1/2. Ingham proved it for c = 3/5, remarking that his methods would give a strictly smaller number, and later people have explicitly produced values that are strictly smaller, but not by very much. John conway _______________________________________________ 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] a prime in each row?
by James Propp 09 Jun '03

09 Jun '03

When you write the numbers from 1 to n^2 in n rows of length n (with n > 1 arbitrary), does each row contain a prime? Jim Propp

4 3

Re: [math-fun] Car talk puzzler
by Dan Hoey 09 Jun '03

09 Jun '03

Michael Kleber <kleber(a)brandeis.edu> writes: > Dan Hoey wrote: > > There are a lot of crossing problems, but this one is quite > > familiar. It has been kicking around rec.puzzles since 1996[...] > Over lunch, I mentioned it to Dimitry Kleinbock, who said he saw it > in a Quantum Magazine even before that (and culled it for a Math > Circle type thing he was doing in NJ, and he might be able to dig up > a citation). Neat. I didn't think it was likely to be a Microsoft original. I wonder if I saw that Quantum. I remember thinking the puzzle looked familiar when I saw it in rec.puzzles. > But any reference for >4 crossers? I don't know of any. I wonder if anything useful comes of bridges that hold three people? Or flashlights that require two people to carry? When I wrote: > > I know that for N=6 we can force 11 crossings.... I was wrong. Somehow I thought the case with 1,2 small and 3,4,5,6 large would require that, but your strategy > 12, 1, 34, 2, 12, 1, 56, 2, 12 is clearly the solution. I haven't got a proof, but I suspect 2N-3 crossings is always best. > Which of the three N=6 strategies is preferable depends on how 2 a2 > compares to a1+a3 and a1+a5. I don't know if it would help to consider the first differences of the parameters (since if the number of crossings is constant, they are all that matter). Then the criteria would be d1:d2 and d1:d2+d3+d4. Dan

1 0

Re: [math-fun] Car talk puzzler
by Dan Hoey 09 Jun '03

09 Jun '03

Michael Kleber <kleber(a)brandeis.edu> writes: > Last week's Car Talk puzzler might have some interesting math. > (Tom and Ray said this has been floating around, but I haven't > heard it before; am I behind the curve here?)... There are a lot of crossing problems, but this one is quite familiar. It has been kicking around rec.puzzles since 1996, when it was said to be a Microsoft interview puzzle: http://groups.google.com/groups?selm=01bbc5b7%242146dd80%247b839bce%40redpw… Somewhere along the line it was dressed up as being the four members of the band "U2" who had to get across to make their concert on time. (Do bands start on time now? It's been a long time since I was at a rock concert.) > 1) If you have 2n people, how many different undominated strategies > are there, and what structure does this set have? I don't see why you want the number of people to be even. For N people, the minimum number of crossings is 2N-3, but that may not be optimal in all cases. I know that for N=6 we can force 11 crossings, but I don't know if there's an optimal 9-crossing solution for N=5. Dan Hoey(a)AIC.NRL.Navy.Mil

2 1

[math-fun] Car talk puzzler
by Michael Kleber 09 Jun '03

09 Jun '03

Last week's Car Talk puzzler might have some interesting math. (Tom and Ray said this has been floating around, but I haven't heard it before; am I behind the curve here?) Copied from http://cartalk.cars.com/Radio/Puzzler/Transcripts/200322/index.html --------- "It was a dark, moonless night in France, 1943, deep within German-held territory. Out of the inky shadows comes Claudette, the beautiful French resistance fighter, followed by three downed Allied crew members, who she must get back into friendly hands. They must cross a bridge, and they know the Germans are not far behind. It's an old, treacherous bridge, and they have only one flashlight among them to see. The bridge can support only two of them at a time. Three on the bridge, and it's curtains. "Pairs crossing can do so only as quickly as the slower member of the pair, because they need the flashlight to see. Each time a pair crosses, someone has to return with the flashlight, until they're all safely across. "Unfortunately, the three downed airmen are injured. Here are the times each person takes to cross the bridge: Claudette can do it in a minute. Major Johnson has a twisted ankle, and takes 2 minutes. Captain Kangaroo got shot up pretty bad. He has to hop on one foot, and it takes him 5 minutes. Colonel Mustard is in worse shape. It takes him 10 minutes to cross the bridge. "Claudette has rigged the bridge with explosives so that their pursuers can't follow. She's about to set the timer." Here's the puzzler: What's the shortest time she can set and get everyone safely across the bridge before it blows up? --------- Pause reading now if you want to think about it yourself, answer and musings follow. The natural thing to want to do is have Claudette ferry each person across and dash back with the flashlight; this takes 2+1+5+1+10+1 = 19 minutes. The first interesting part is that you can do better. Of course the trick is to have the 5 and 10 minute guys cross the bridge together, and you can accomplish this by sending 1,2 over together, 1 coming back, then sending 5,10 over at once, then 2 coming back with the light, and 1,2 going over together again. This takes 2+1+10+2+2 = 17 minutes instead. So if the four people take time 0 <= a1<= a2 <= a3 <= a4 to cross the bridge, then the first strategy takes time 2 a1 + a2 + a3 + a4, while the second takes time a1 + 3 a2 + a4; you have the option of trading in a1+a3 for 2 a2, which is a good idea here, with 1+5>2+2. So the questions that leap to my mind are: 1) If you have 2n people, how many different undominated strategies are there, and what structure does this set have? One strategy dominates another, of course, if the first is better for all values of the a's with 0 <= a1 <= ... <= a_2n. Then you need to say what "different" means -- probably two strategies are "the same" if their respective unordered multisets of bridge crossers coincide, though some subtlety lurks in that -- the strategies above have 3! and 2! implementations respectively, and they are pretty obvious, but there might be more different-looking strategies that I've defined as "the same", perhaps foolishly. Or even more coursely, we could just identify strategies that take the same total time. 2) What does the complex of regions where each strategy dominates look like? Or how about set of separating hyperplanes? For 4 people it was a1 - 2 a2 + a3, quite suggestive. --Michael Kleber kleber(a)brandeis.edu

1 0

Re: [math-fun] Geometry/topology question about planar graphs
by Erik Demaine 05 Jun '03

05 Jun '03

On Thu, 5 Jun 2003, Dan Asimov wrote: > But given that a graph G that can embedded in the plane can be embedded with > all edges straight, however, doesn't immediately imply that the straight-line > embedding *is* topologically equivalent to the original embedding (even > though the graph itself is of course topologically the same). If the graph is 3-connected, then the topological embedding is unique up to the choice of the outer face. Tutte's "How to Draw a Graph" allows you to specify the outer face in the straight-line drawing it produces. So for 3-connected graphs, you get exactly the topological embedding you want. For graphs that are not 3-connected (like your square + a degree-2 vertex in the center), I assume you can decompose... E.g., suppose there is a vertex 2-cut {v,w}, and on one side you have G_1 and the other side you have G_2 (both of which contain v & w, and that is their only overlap). Let G'_1 be the graph & topological embedding obtained from G_1 with the edge {v,w} added where G_2 used to be. Ditto for G'_2. Then you can draw G'_1 and G'_2 by induction, and then nonuniformly scale G'_2's drawing down to be squished against the edge {v,w}, and then place it against the appropriate side of {v,w} in the drawing of G'_1. Erik -- Erik Demaine | edemaine(a)mit.edu | http://theory.lcs.mit.edu/~edemaine/

2 1

[math-fun] Re: a prime in each row?
by James Propp 05 Jun '03

05 Jun '03

I wrote: >Moreover, if one looks at the minimum (over k) of the number of primes in >the kth row of the n-by-n square, one gets the sequence > >1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 3, 2, 2, 2, 3, 4, 4, 3, 4, 3, 3, 4, >5, 4, 3, 4, 5, 4, 4, 5, 4, 4, 5, 5, 2, 6, 6, 5, 4, 6, 4, 5, 7, 7, 3, >7, 8, 4, 5, 10, 7, 5, 6, 5, 5, 10, 7, 8, 8, 6, 10, 7, 5, 5, 8, 7, 7, >5, 10, 7, 8, 10, 7, 7, 10, 10, 9, 12, 7, 11, 10, 10, 9, 7, 13, 11, >10, 10, 11, 10, 11, 10, 11, 12, 11, 8, 11, 9 Neil Sloane wrote to me saying that his own calculations disagreed with mine. He's right; this is not how the sequence goes. Here's how the sequence actually starts: 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 2, 3, 4, 3, 3, 4, 3, 3, 4, 3, 3, 4, 4, 4, 3, 3, 4, 5, 4, 3, 4, 5, 4, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 6, 4, 5, 6, 6, 5, 6, 6, 6, 6, 6, 7, 7, 6, 6, 6, 7, 7, 7, 7, 6, 6, 7, 7, 7 Thanks, Neil! Jim Propp

1 0

Re: [math-fun] Geometry/topology question about planar graphs (fwd)
by asimovd＠aol.com 05 Jun '03

05 Jun '03

Erik Demaine asks: << Can't any two topologically equivalent embeddings (in the sense that the cyclic order around each vertex is identical in two embeddings) be obtained by continuous deformation? >> This looks fairly easy to prove. And I'm fairly convinced of John's assertion that a straight-line embedding of a graph G in the plane *can* be obtained by a continuous deformation of an arbitrary planar embedding of G. But given that a graph G that can embedded in the plane can be embedded with all edges straight, however, doesn't immediately imply that the straight-line embedding *is* topologically equivalent to the original embedding (even though the graph itself is of course topologically the same). For example consider a square with a 5th node making a triangle with one side of the square -- a graph with 5 nodes and 6 edges. This can be embedded in the plane with the 5th node either inside or outside the square. (Of course, straightenability is not an issue here.) --Dan

1 0