- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Re: Rotor-router article
by James Propp 10 Feb '05

10 Feb '05

Michael Kleber wrote: >My publications list, with "Goldbug Variations" at the top, is at > > http://people.brandeis.edu/~kleber/pubs.html > >There's also a link to just download/view the blob picture alone. Does anyone have any ideas about how one could mechanically implement bugs and rotor-routers, in a fashion suitable for a classroom demo or a science museum display? (Hal Canary and Francis Wong created a software implementation of some of the variations; you can find an outdated version of the "1.0" release of their applet at http://www.math.wisc.edu/~propp/rotor-router-1.0/ . To play with the goldbug, click "The Applet", change "1-D Aggregation" to "1-D Walk", and click on "Paused (Press to Resume)".) Jim Propp

1 0

[math-fun] ~s gears
by R. William Gosper 09 Feb '05

09 Feb '05

John McCarthy collects inventions that came too late to do much good, e.g., the non-pulsating candle wick. In this era of numerical machi- ning, we ought to be able to make interesting gears to solve mechanical problems of yesteryear. As a minor (and probably unoriginal) example, to minimize stripping, a smaller gear ought to have broader teeth and narrower notches than the larger gear it meshes with. This must be geometrically possible, at least sometimes, since you could delete alternate teeth from a(n even-toothed) larger gear and fill in the corresponding notches of the smaller one. However, if we view this as a deformation of gears with half as many teeth, we have lost something like half the tooth amplitude (proper term?), so there may be little advantage in desymmetrizing. We might get certain exotic ratios with differential planetaries where the ring and central gears differ by an odd number of teeth. This might be possible if those gears are in slightly different planes, slightly beveled, with slightly tilted planets spanning the gap. The planets or ring might have a hollow shaft coaxial with the central's, both driven (at different speeds) by one adjoining shaft bearing two gears. This would require "continuous" scalability of one gear and its mate on one of the coaxial shafts. I'd like to animate gears with improbably small numbers of teeth (3??, 4?). Can anyone save me the trouble of deriving the involute curves that avoid sliding friction? --rwg PS, apologies for my churlish Mahalingam ouburst. A few minutes of Google, or consulting with any Subcontinental would have taught me that it is a proud old name of long standing. E.g., Welcome to Shankar Mahalingam's homepage. Professor and Chair Department of Mechanical Engineering University of California, Riverside ... This gentleman has *absolutely no connection* with the villain in the up-and-coming Goldmember sequel. And all this is dinky by comparison with former African head-of-state Houphouet Boigny, which in his own language means "Pit of Excrement". "Oh Miss Rice, here's some xylo- caine in case you need to bite your cheeks during the introductions." SUBNARCOTIC OBSCURANTIC BUCCINATORS (You bet your mahalingam.)

5 4

[math-fun] 10,000 year gear train
by Danny Hillis 06 Feb '05

06 Feb '05

I am building a mechanical clock that is intended to show the position of the visible planets and the phase of the moon over the next ten thousand years. Thus, I would like a gear train that computes all the following ratios using a small number of gears. 29.53058853, 87.96925718, 224.7007992, 365.2563554, 686.9795859, 4332.820129, 10755.69864 The gear train must use gears with tooth number not less than 12 and not greater that 400. I want to integrate daily rotations to show the orbital position within a few percent after 10,000 years, so I need accuracy to at least 6 places. After playing around with this problem using lattice methods, I realized that (a) there were like some very good solutions in the space and (b) that Bill Gosper would probably be better at finding them than I would. Indeed, RWG took up the challenge and kindly suggested the following solution (note the shared gears): RWG wrote: > 293 149 157 > (--- ---) --- = 29.5350888532671 +.3 lsd > 12 83 233 > > 293 152 358 101 61 > (--- --- ---) --- -- = 87.9692571945795 1.4 lsd > 12 107 295 67 44 > > 293 152 149 > (---) --- --- = 224.700799133144 -.7 lsd > 12 107 23 > > (Don't see how to reuse 149.) > > 293 152 358 269 > (--- ---) --- --- = 365.256355463807 +.6 lsd > 12 107 295 31 > > 293 152 358 101 263 267 > (--- --- --- ---) --- --- = 686.979585832448 -.7 lsd > 12 107 295 67 47 138 > > 293 152 358 101 263 322 281 272 > (--- --- --- --- --- ---) --- --- = 4332.8201300432 1 lsd > 12 107 295 67 47 103 107 183 > > (Don't see how to reuse 281.) > > 293 152 358 101 263 322 281 > (--- --- --- --- ---) --- --- = 10755.6986519239 1.2 lsd > 12 107 295 67 47 103 29 > > Beat that! > --Bill I post his solution here because it is lovely and also in the faint hope that someone on the list may be able to do better. I offer a $1 prize to the first person (including Bill) who can beat this solution, by reducing the number of gears size without decreasing the worst-case accuracy. -Danny

5 4

[math-fun] A missing sequence from group theory?
by N. J. A. Sloane 04 Feb '05

04 Feb '05

To MathFun and SeqFans: A possibly new sequence? Could someone calculate it? Let t(G) = no. of unitary factors of the abelian group G, and let T(n) = Sum t(G) taken over all abelian groups of order <= n. There are several papers giving estimates for T(n), e.g. T(x) = c_1 x (log x + 2 gamma - 1) + c_2 x + ... My question is, how does the sequence T(n) begin? References and definitions follow, from MSN. NJAS MR1850168 Zhai, Wen Guang On the average number of unitary factors of finite abelian groups. II [MR1813450 (2001j:11092)]. (Chinese) Acta Math. Sinica 44 (2001), no. 4, 667--672. 11N45 MR1813450 (2001j:11092) Zhai, Wenguang On the average number of unitary factors of finite abelian groups. II. Acta Math. Sin. (Engl. Ser.) 16 (2000), no. 4, 549--554. (Reviewer: R. C. Baker) 11N45 (11L07 20K01) MR1641042 (99e:11124) Zhai, Wenguang; Cao, Xiaodong On the average number of unitary factors of finite abelian groups. Acta Arith. 85 (1998), no. 4, 293--300. (Reviewer: R. C. Baker) 11N45 MR1613290 (99f:11124) Wu, J. On the average number of unitary factors of finite abelian groups. Acta Arith. 84 (1998), no. 1, 17--29. (Reviewer: R. C. Baker) 11N45 (11L07 20K01) 1225427 (94k:11108) Schmidt, Peter Georg(D-MRBG) Zur Anzahl unitrer Faktoren abelscher Gruppen. (German) [On the number of unitary factors in abelian groups] Acta Arith. 64 (1993), no. 3, 237--248. Part of this review follows: Let $\scr A$ denote the set of all abelian groups. Under the operation of direct product, $\scr A$ is a semigroup with identity element $E$, the group with one element. $G_1$ and $G_2$ are relatively prime (German: teilerfremd) if the only common direct factor of $G_1$ and $G_2$ is $E$. We say that $G_1$ and $G_2$ are unitary factors of $G$ if $G=G_1\times G_2$ and $G_1,G_2$ are relatively prime. Let $t(G)$ denote the number of unitary factors of $G$, and let $T(x)=\sum_{G\in {\scr A}, |G|\le x} t(G).$ There are constants $A,B,$ and $C$ such that $\Delta(x)\colon =H(x)-Ax\log x - Bx -C\sqrt x=o(\sqrt x).$ In this paper, the author shows that $\Delta(x)\ll x^{3/8} \log^{7/2}x.$ The previous best estimate for $\Delta(x)$ had been $\Delta(x)\ll x^{31/82} \log^2 x$; this was given by H. Menzer \ref["Exponentialsummen und verallgemeinerte Teilerprobleme", Habilitationsschrift, Friedrich-Schiller-Univ., Jena, 1992; per bibl.]. Further references from the Wu (1998) paper: Many accented letters have been dropped! # R. C. Baker and G. Harman, Numbers with a large prime factor, Acta Arith. 73 (1995), 119--145. MR1358192 (97a:11138) # E. Cohen, On the average number of direct factors of a finite abelian group, ibid. 6 (1960), 159--173. MR0118764 (22 #9535) # E. Fouvry and H. Iwaniec, Exponential sums with monomials, J. Number Theory 33 (1989), 311--333. MR1027058 (91b:11097) # S. W. Graham and G. Kolesnik, Van der Corput's Method of Exponential Sums, Cambridge Univ. Press, Cambridge, 1991. MR1145488 (92k:11082) # C. H. Jia, The distribution of square-free numbers, Sci. China Ser. A 36 (1993), 154--169. MR1223084 (94f:11095) # G. Kolesnik, On the number of abelian groups of a given order, J. Reine Angew. Math. 329 (1981), 164--175. MR0636451 (83b:10055) # E. Krtzel, On the average number of direct factors of a finite abelian group, Acta Arith. 51 (1988), 369--379. MR0971087 (89m:11091) # H.-Q. Liu, The greatest prime factor of the integers in an interval, ibid. 65 (1993), 302--328. MR1259341 (95d:11117) # H.-Q. Liu, On some divisor problems, ibid. 68 (1994), 193--200. MR1305200 (96a:11089) # H.-Q. Liu, Divisor problems of 4 and 3 dimensions, ibid. 73 (1995), 249--269. MR1364462 (96k:11118) # P. G. Schmidt, Zur Anzahl unit\"arer Faktoren abelscher Gruppen, ibid. 64 (1993), 237--248. MR1225427 (94k:11108) # P. Sargos and J. Wu, Multiple exponential sums with monomials and their applications in number theory, Prpublications 97/ n37 de l'Institut lie Cartan, Universit Henri Poincar (Nancy 1). # J. Wu, On the distribution of square-full and cube-full integers, Monatsh. Math., to appear. cf. MR1657818 (2000a:11125)

8 12

[math-fun] graph question
by Chris Landauer 03 Feb '05

03 Feb '05

hihi. all - let's start by stating the problem in a way that can be solved the graph certainly needs to be finite and connected in addition, you also have to limit the number of times each edge can be retraced, or else it is trivial to draw any connected finite graph with a continuous path, whether or not there are odd order vertices (pick any one vertex - connected means there is a path, so just draw all the paths from that vertex to the others and back) the usual restriction is to limit each edge to exactly one traversal (so the order of a vertex is the total number of arrivals and departures it encounters in the continuous path), which is called an eulerian path (the seven bridges of koenigsburg apparently brought the problem to his attention) there are no finite graphs with exactly one odd order vertex it is clear that any eulerian path in a graph with two odd order vertices will necessarily start at one of them and end at the other also, it is clear that any eulerian path for a graph with no odd order vertices must end at the same vertex at which it starts i expect there is a reasonably straightforward induction proof - it is certainly an old theorem more later, cal

2 1

Re: [math-fun] Marc Paulhus and BYN?
by Michael Kleber 03 Feb '05

03 Feb '05

Hi Marc, Glad to hear from you again, and thanks for setting the record straight. I still wonder where the claim of the result came from, but if it had nothing to do with you, I'm no longer worried that it's somehow true and I did something wrong. > I have attached what was my last word on the subject which appeared in the > AMM. I recall that the final published version did credit Michael with the > longest hand... to my knowledge that record still stands. My program has been and still is running in the background of whatever computer happens to be sitting on my desk, and every year or so it seems to find a new record. The current one is 1:-J--KA----A-Q--Q-A----KJ-- 2:A------QKJ--Q-------KJ---- which terminates after 893 "tricks" (compared to 805 for the one that did indeed appear in the AMM note). --Michael Kleber > From: Marc Paulhus <paulhus(a)wanadoo.nl> > To: Michael Kleber <michael.kleber(a)gmail.com> > Cc: Richard Guy <rkg(a)cpsc.ucalgary.ca> > Date: Thu, 3 Feb 2005 09:19:46 +0100 > Subject: Re: [math-fun] Marc Paulhus and BYN? > > Hello Michael and Richard, > > This is a very interesting claim. Unfortunately it is not true. Or, at > least, it cannot be credited to me. > > I, like Michael, wrote a computer program that played many hands and never > found a cycle in a standard deck. > > I have attached what was my last word on the subject which appeared in the > AMM. I recall that the final published version did credit Michael with the > longest hand... to my knowledge that record still stands. > > Marc. > > ----- Original Message ----- > From: "Michael Kleber" <michael.kleber(a)gmail.com> > To: "Richard Guy" <rkg(a)cpsc.ucalgary.ca> > Cc: "math-fun" <math-fun(a)mailman.xmission.com>; "Marc Paulhus" > <paulhus(a)wanadoo.nl> > Sent: Wednesday, February 02, 2005 5:24 PM > Subject: Re: [math-fun] Marc Paulhus and BYN? > > Thanks, Richard -- glad Marc is traceable. > > The paper you include looks old: I think it's from before he ran > something in the Monthly unanswered questions column in > February '99. In fact, that's outside the 5-year window, so on JSTOR: > http://links.jstor.org/sici?sici=0002-9890%28199902%29106%3A2%3C162%3ABMN%3… > > In particular the "very long hand" included in that tex file is the one > Marc had in the Monthly piece. We first learned about each other while > that was in press, and he added a note mentioning the significantly > longer hand that was my record at the time -- the only time my name > has appeared in that fine publication, I think. Ah, fame :-) > > --Michael > > On Wed, 2 Feb 2005 08:58:28 -0700 (MST), Richard Guy > <rkg(a)cpsc.ucalgary.ca> wrote: > > I'm copying this to Marc, who can best > > answer it. There is a paper somewhere > > --- too lazy to put my hand on it, but > > I attach a 2003-09-22 version of it, > > in case it is of help. R. > > > > On Wed, 2 Feb 2005, Michael Kleber wrote: > > > > > Does anyone know where Marc Paulhus is now? > > > His email address at Calgary bounces. > > > > > > Arturo Magidin just pointed out to me that in the new > > > release of Winning Ways Vol 4 (on p.892), they claim > > > that Marc found a non-terminating game of Beggar- > > > Your-Neighbor. But they don't cite or present the hand. > > > > > > WW also says, though, that Marc says that one out of > > > 150,000 hands will not terminate, and I find that hard to > > > believe -- I wrote a computer program (some ten years > > > ago) that plays random deals, and it's played hundreds > > > of billions of hands without finding one that cycles. > > > So I'm hoping to find out what the story really is... > > > > > > --Michael > > > -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

1 0

[math-fun] adding and multiplying fractions and tangles
by James Propp 02 Feb '05

02 Feb '05

Has anyone ever published Gosper's algorithms for adding and multiplying continued fractions? You can find his write-up on the web at http://www.tweedledum.com/rwg/cfup.htm The one-sentence abstract is a classic: "Contrary to everybody, this self contained paper will show that continued fractions are not only perfectly amenable to arithmetic, they are amenable to perfect arithmetic." Also: Is there a way to combine two rational tangles (as in Conway's "square dancing" game) so that the corresponding fractions add (in the ordinary sense or in the harmonic sense)? The obvious ways of doing this (called addition and multiplication of tangles --- see e.g. Figure 3 in http://users.ntua.gr/sofial/ratl.ps) do not have this property; e.g., if A and B are rational tangles, A+B need not be a rational tangle, nor must A+B be the same as B+A. Jim Propp

3 2

[math-fun] Marc Paulhus and BYN?
by Michael Kleber 02 Feb '05

02 Feb '05

Does anyone know where Marc Paulhus is now? His email address at Calgary bounces. Arturo Magidin just pointed out to me that in the new release of Winning Ways Vol 4 (on p.892), they claim that Marc found a non-terminating game of Beggar- Your-Neighbor. But they don't cite or present the hand. WW also says, though, that Marc says that one out of 150,000 hands will not terminate, and I find that hard to believe -- I wrote a computer program (some ten years ago) that plays random deals, and it's played hundreds of billions of hands without finding one that cycles. So I'm hoping to find out what the story really is... --Michael -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

2 2

RE: [math-fun] Re: covering all N with squares (2nd degree polynomialswith integer coeffs.).
by Daniel Asimov 27 Jan '05

27 Jan '05

1. Are there any restrictions on the cocefficients, or can they be arbitrary complex numbers? 2. As long as each natural number occurs somewhere in the array, does it matter what else is in the array? --Dan ------------------------------------------------------ Simon says: << ... let my try to restate the problem let's make a square array of numbers from wich each row is a 2nd degree pol. : apart from the first column, does the array covers ALL natural numbers with possibly some overlap? >>

2 1

[math-fun] Re: Marriage theorem generalization
by Andy Latto 27 Jan '05

27 Jan '05

> -----Original Message----- > From: math-fun-bounces+andy.latto=pobox.com(a)mailman.xmission.com > [mailto:math-fun-bounces+andy.latto=pobox.com@mailman.xmission.com]On > Behalf Of Thomas Colthurst > Sent: Thursday, January 27, 2005 1:24 PM > To: michael.kleber(a)gmail.com; math-fun(a)mailman.xmission.com > Cc: thomasc(a)bbn.com > Subject: [math-fun] Re: Marriage theorem generalization > > > > Well, here's a reduction to what is hopefully a well-studied > graph theory problem. > > Add two special sets: S, which contains only the interval [0,0], > and E, which contains only [n+1,n+1]. Now make a graph G with > a vertex for every interval and an edge between two intervals > iff (1) the union of the two intervals is itself an interval > and (2) the two intervals come from different sets. Thus, if > there were k sets of intervals in the beginning, G is (k+2)-partite > graph. The problem now becomes: find a path in G from > [0,0] in S to [n+1,n+1] in E that visits each part of G > at most once. > > As I said, I hope this is a well-studied problem, because all > I know are bad solutions to it. Well, it's a more difficult problem than finding Hamiltonian circuits in a graph, so it's NP-complete. Given a graph G with N vertices, you can construct a new graph G', with vertices in G X {1, 2,...,n} If G has an edge from x to y, then G' has an edge from {x, i} to {y, i+1} for all i. G' is n-partite, with projection to G giving the parts. Now G has a hamiltonian path starting at x and ending at y just if G' (an n-partite graph) has a path from {x, 1} to {y, n} that visits each part of G' at most once. So you've reduced what might be a hard problem, but might be an easy one, to a problem that's definitely hard. Andy Latto andy.latto(a)pobox.com

1 0