October 2007 - mathfun@mailman.xmission.com

[math-fun] Re: Submarine problem
by Steve Witham 29 Oct '07

29 Oct '07

My computer just finished trying (& failing) to find a 16-or-fewer- shot solution for n = 10, so (edited): n=10, 17 shots: 0 0 0 0 0 1 1 6 1 4 8 5 3 9 2 7 7 total_shots_tried = ~4.0e08 shots_tried: 1 1 1 1 1 2 12 1.2e02 1.2e03 1.2e04 1.1e05 9.7e05 7.4e06 4.7e07 1.8e08 1.6e08 2.8e06 hopeless: 0 0 0 0 0 0 0 0 1 1.4e02 4.4e03 1.1e05 1.7e06 2.1e07 1.3e08 1.2e08 0 wasted: 0 0 0 0 0 0 0 0 5 85 1.2e04 1.2e05 1e+06 7.3e06 3.5e07 4.1e07 1.3e06 n=10, <=16 shots can't be done. total_shots_tried = ~1.1e11 shots_tried: 1 1 4 40 4e02 4e03 4e04 4e05 4e06 4e07 3.9e08 3.3e09 2.2e10 6.6e10 2.2e10 6.6e07 hopeless: 0 0 0 0 0 0 0 1 1e03 2.5e05 1.8e07 7.3e08 1.3e10 5.4e10 1.7e10 0 wasted: 0 0 0 0 0 0 6 3.2e02 1.5e04 2.9e05 4.2e07 3.7e08 2.8e09 9.7e09 4.9e09 2.9e07 "shots_tried" shows how many shots were made at each level. You can see it multiply by 10 for about 8 levels. "hopeless" shows how many subtrees were cut off at each level by the "hopeless" rule: too many subs at one velocity to shoot with the remaining shots. "wasted" shows prunings due to the rule that you might as well use a shot that hits at least one previously-unhit sub. You can see that "wasted" takes effect sooner (which means bigger subtrees are pruned), but "hopeless" cuts off more shallow subtrees. I test for Wasted first & if so, don't test for Hopeless (which is harder to test for), so I don't know their intersection. But their combined effect in this case seems to be that the search took ~10^11 moves instead of ~4x10^13. There is a solution for n = 9 with 17 shots. Proving it can't be done in 16 shots takes longer than for n = 10 because Hopeless kicks in a move later. Current state of the code: http://www.tiac.net/~sw/math-fun I know solving cases by brute force is useless but I was sort of hoping to see patterns or something! Or, in the course of inventing optimizations, to get some insight. I don't feel insightful yet. Another trick should reduce the search by another factor of about 20 for n = 9: scan combinations (instead of cross-product) of moves at the same time (mod n). Maybe this will let me tackle n = 12, too. --Steve -- My apples and oranges are beyond compare!

2 1

Re: [math-fun] Re: Teabag Problem
by Dan Asimov 28 Oct '07

28 Oct '07

Bill T. writes: << . . . [T]here's a general principle, I think due to Nash (who proved a C^1 isometric embedding theorem) that was motivational at least implicitly if not explicit in some of Gromov's early work on partial differential inequalities, that any sub-isometric smooth embedding of a surface in space can be approximated by an isometric embedding. If you accept this principle, it's very easy to enclose a positive volume by gluing together two C^1 smooth disks which contract distances, then approximating by an isometric embedding. . . . . . . >> Let S^2 denote the unit sphere in R^3. The Nash embedding theorem -- as improved by Kuiper (cf. http://en.wikipedia.org/wiki/Nash_embedding_theorem ) -- implies that S^2 can be C^1 isometrically embedded into an arbitrarily small ball of R^3. QUESTION: Suppose we consider only isometric embeddings h_1 that arise from a continuous family of isometric embeddings h_t: S^2 -> R^3, 0 <= t <= 1, where h_0 is the inclusion mapping. Does there still exist an isometry h_1 of S^2 into an arbitrarily small ball in R^3? If not, how small can the image of such an isometry be? (It's not immediately obvious that the image can even have a smaller diameter than the original sphere, but it can.) --Dan

5 6

Re: [math-fun] Re: radio math
by Eugene Salamin 28 Oct '07

28 Oct '07

----- Original Message ---- From: Fred lunnon <fred.lunnon(a)gmail.com> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Saturday, October 27, 2007 12:44:41 PM Subject: Re: [math-fun] Re: radio math On 10/27/07, Henry Baker <hbaker1(a)pipeline.com> wrote: > > Cantor-type diagonalization is the major tool Goedel's work and in computational complexity, so Cantor's work does find a role in certain parts of computer science. > > It's an interesting challenge to figure out what role diagonalization might play in "real" life. I'm not entirely convinced that the similarity of the Cantor diagonal argument to the Russell paradox / Goedel proof / Cretan liar et al is sufficient grounds for drawing the latter into a discussion about infinities. Perhaps it might be argued that diagonalisation leads to a new object in an open-ended system (e.g. the continuum in the cardinals); but in a closed system it leads to a contradiction. At any rate, I am convinced that diagonalisation by itself does impinge very immediately on "real life", in a manner which does not seem well appreciated. There is an obscure corner of mathematical logic and computer science known as "situation theory" [one reason for its low profile may well be that none of its practitioners will actually admit to being a situation theorist!]. Situation theory employs axiomatic set theory to model the concept of truth in a closed universe where the active agents are capable of self-reference. The central revelation is that (loosely) in such situation, either there is are questions whose answers are unknown to some agents, or else there are answers about which agents must disagree. There is a very readable account of all this material in Jon Barwise & John Etchemendy's book "The Liar". Failure to appreciate the ramfiications of this theorem have resulted elsewhere in the generation of an enormous amount of otherwise (possibly) well-informed and entertaining twaddle --- a situation which will doubtless persist, whatever I say! Fred, This sounds interesting. Can you give us an example of how situation theory impacts ordinary life? Gene __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

2 1

Re: [math-fun] radio math
by Dan Asimov 27 Oct '07

27 Oct '07

Gene asked << I wrote: << I would *not* recommend "1,2,3,...Infinity" by George Gamow, as it contains crucial errors in its discussion of infinities. And Dover has refused to fix any of these, despite my reporting them over 10 years ago. >> What are all the errors? It's been a long time since I read the book, and the only one that I remember is the misuse of the aleph notation. The book is now historical, and I would not expect the publisher to make any alterations. Another suggestion for the interview is to be prepared with an inventory of short arguments that quickly lead to their conclusion. This is an interview, not a lecture, and your presentation will be constantly deflected by the interviewer's questions. >> Errors with aleph notation are what I'm referring to (big errors): He get aleph_0 right, but states that aleph_1 = c (the Continuum Hypothesis, which has been shown undecidable in ZF+AC by (the combined work of) Goedel & Cohen. If I recall, he then says aleph_2 = the number of curves, aleph_3 = the number of surfaces, etc. -- but all of these are also = c. What' worse is that these errors, never corrected in any later edition, have been propagated by later authors who took them as gospel (e.g., Michael Guillen in "Bridges to Infinity"). --Dan

1 0

Re: [math-fun] radio math
by Eugene Salamin 27 Oct '07

27 Oct '07

----- Original Message ---- From: Dan Asimov <dasimov(a)earthlink.net> To: math-fun <math-fun(a)mailman.xmission.com> Sent: Thursday, October 25, 2007 3:46:09 PM Subject: Re: [math-fun] radio math I'd recommend that anyone going on the radio to ad lib a mini-lecture on math for lay listeners first practice in private on non-mathematician friends to see what works, and to develop confidence in their ability to give a successful ad lib mini lecture. --Dan P.S. ... I would *not* recommend "1,2,3,...Infinity" by George Gamow, as it contains crucial errors in its discussion of infinities. And Dover has refused to fix any of these, despite my reporting them over 10 years ago. Dan, What are all the errors? It's been a long time since I read the book, and the only one that I remember is the misuse of the aleph notation. The book is now historical, and I would not expect the publisher to make any alterations. Another suggestion for the interview is to be prepared with an inventory of short arguments that quickly lead to their conclusion. This is an interview, not a lecture, and your presentation will be constantly deflected by the interviewer's questions. Gene __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

Re: [math-fun] Re: radio math
by James Propp 27 Oct '07

27 Oct '07

David Gale asks: >Query. Is there an easily described sequence which has been PROVED to be >finite but we don't know what the last term is? There used to be: There's a known finite list of principal ideal domains of the form Z[(1+sqrt(1-4k))/2] with k a positive integer, but for a while the state of affairs was that, although the list of known d's had not been proved to be complete, it had been proved that there was at most one other d missing from the list of known examples. So, at *that* time, this would have been an example of what David's looking for; but (a) it no longer is (since the original list has now been shown to be complete), and (b) the list is not so easily described (unless this d, like the number 41, would also have necessarily had the property that n^2 + n + d is prime for all n between 0 and d-2; I'm not sure about this). If you're willing to relax the notion of a sequence and settle for a set, then a contemporary answer to David's question is the set of non-trivial solutions to the Diophantine equation m^p - n^q = 1 (Catalan's equation). It's known that there are at most finitely many. Jim Propp

1 0

Re: [math-fun] radio math
by Henry Baker 26 Oct '07

26 Oct '07

Re infinities: Subscribe to the following podcast with iTunes & listen to the episodes from 11/10/05 and 11/14/05: http://comp.uark.edu/~strauss/mathfactor/podcast/MathFactor.xml Also the Math Factor blog: http://mathfactor.uark.edu/ (Perhaps the authors of this blog/podcast are subscribers to math-fun ? )

1 0

[math-fun] Re: nice little sin(a+b+c+...) formula
by Bill Gosper 26 Oct '07

26 Oct '07

hgb>I'm still looking for good formulae for the following cases: >sinh(x*2^k) = ?? >sinh(x+y) = ?? Well, as Joshua suggests, n n ==== /===\ \ k | | %i %pi k %i > (- 1) | | 2 %i sinh(-------- + a ) n / | | n + 1 j ==== ==== j = 0 \ k = 0 sinh( > a ) = - ---------------------------------------------- / k 2 n + 2 ==== k = 1 (with the fast stable recurrence still an option, and the prod becoming a power for a[k]:=x.) But sinh(i pi/2 +a) = i cosh(a), so I guess that's not your pleasure either. >asinh(x*2^k) = ?? >asinh(x+y) = ?? A special case of both of these is asinh(2*x), but all I see is 2 asinh(sqrt(x - 1) + x) = asinh(sqrt(x)) + asinh(sqrt(x - 1)). --rwg __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

[math-fun] Hello?
by Dan Asimov 26 Oct '07

26 Oct '07

Rich, I thought I had a promising idea re finding a unique flow for e^x (and if it works, it works equally for a^x, I think, at least for a > e^(1/e), and maybe all a <> 1 in (0,oo). So I was eager to hear your reponse. To repeat (tersely this time): Assume a > (e^(1/e) (though perhaps unnecessarily) and consider f_a(x) := a^x, x real. Conjugating with 1/x, use g_a(x) := a^(-1/x) for x > 0. To find *its* flow, first find the flow of g_(a,c)(x) := a^(-1/x) + c, which has a fixed point x_c > 0, satisfying 0 < g_(a,c)'(x_c) < 1. Now use our usual formula to get a unique flow for g_(a,c) (using only x > x_c). Letting c decrease to 0, I hope the limit of these flows is an analytic flow for a^(-1/x). Finally, conjugate the flow with 1/x again to recover the flow for a^x. (Which, if it works, would work for x < 0, but this can be easily extended to all x by applying log_a, etc.) What thinkst thou? --Dan

1 0

Re: [math-fun] branchless programming
by Henry Baker 26 Oct '07

26 Oct '07

This paper might be helpful in your analysis: http://home.pipeline.com/~hbaker1/sigplannotices/sigcol05.pdf At 12:06 PM 10/22/2007, Fred lunnon wrote: >I'm interested in algorithms which eliminate conditional branches: >the following problem turns up in attempting to design a robust, >straight-line, numerical quadratic equation solver, in the subcase >of a double root. > >Find functions f = f(a,b,c), g = g(a,b,c) such that, given any 3 real >numbers (a,b,c) /= (0,0,0) with b*b = a*c, it is guaranteed that > (f*a + g*b, f*b + g*c) /= (0,0). > >One way to do this (harking back to a related discussion on math-fun >a few years back) would be to set f = h(a a + b b), g = h(b b + c c), >where define > h(x) = ceiling(|x|) / max(1, ceiling(|x|)) > = 0 when x is zero, 1 otherwise. >[The absolute value is of course redundant in this application.] > >But I wonder whether it's possible to solve the problem more elegantly, >using (say) polynomial f,g; alternatively, is there some obvious reason >why this might be impossible? > >Fred Lunnon

1 0