June 2003 - mathfun@mailman.xmission.com

FW: Re: [math-fun] distinct and square-free factorizations
by James Tanton 13 Aug '03

13 Aug '03

Let D_k (n) = number of partitions of n with any number repeated at most k times. (Thus D_1(n) = D(n).) O_k (n) = number of partitions of n into numbers none of which is a multiple of k. ( Thus O_2(n) = O(n).) Then D_k (n) = O_(k+1) (n) for all n. The argument using generating functions to establish D(n) = O(n) easily generalises to establish this, but the kids (ages 11 - 17) at the Boston Math Circle recently came up with a nice fun proof of this in terms of representing numbers base k. - JT > [Original Message] > From: R. William Gosper <rwg(a)spnet.com> > To: <math-fun(a)mailman.xmission.com> > Date: 5/18/2003 4:11:57 PM > Subject: Re: [math-fun] distinct and square-free factorizations > > mlb>In fact, recalling this, I'd hoped to retrieve some collective memories! > > acw>> Gosper showed me an absurdly intricate _analytic_ proof of this, and > >>bewailed the lack of a _combinatorial_ proof; > > Here are my memories. Unfortunately, the TeX sources appear to to have been > abandoned at Xerox PARC. Shortly after the announcement of the factorization > of 2^2^2^3+1, I sent a(n unrelated) letter to the the usual gang of maniacs > (Dick Askey, George Andrews, George Gasper (I think), Rich&Hilarie, etc.) > that began: "Dear Thai food lovers and Rich," > answering Hilarie's challenge to find a bijection between the *complements* > of the odd partitions and distinct partitions. I.e., pair the not-all-differents > with the not-all-odds. A very young Peter Weyhrauch and I came up with one, > and then a PARC coworker, Ted Kaehler, came up with a different one! I > then found a generalization of the theorem to residue classes mod k, of which > #(some evens) = #(some duplicates) was the case k=2. This led to a nonobvious > generating function identity. > It would be nice to locate a hardcopy of that letter. > --rwg > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ========================= James Tanton mathcircle(a)earthlink.net P.O. Box 2344 Acton MA 01720 978 635 8036 FIND *MATH CIRCLE* ON THE WEB AT: www.themathcircle.org

2 1

Re: [math-fun] triple star
by Henry Baker 05 Jul '03

05 Jul '03

Bill: I did some reading & searching about these kinds of issues several years ago. Answer: triple systems _are_ highly unstable, and _do_ fly apart. As you point out, the "stable" ones are hierarchical -- there's such a vast scale difference between the masses, that the small perturbations take a long time to build up to something meaningful. There's another problem with stars that isn't true of point masses -- you can bring point masses arbitrarily close together, but when you do this with stars, they get pulled apart like taffee (sp?). I think that the star systems that we see in reasonable quantities are those which _have_ managed to remain "stable" over a reasonable period of time. So to find the "unstable" ones, you have to look quickly before they fall apart. There's been some progress in improving simulations to preserve important quantities -- e.g., energy, angular momentum, etc. I don't know whether it's possible to _guarantee_ such preservation to a large number of digits, though. Hopefully, someone on this list will give a better report on the state of the art of conservation of "constants of integration" in modern simulation algorithms. I have a small simulation on my Palm Pilot (called "asteroids" or some such). I downloaded it from one of the Palm Pilot freeware download sites. (BTW, I'd love a Palm Pilot version of the original MIT space war, if anyone is aware of such a thing.) ------ At 11:52 AM 6/27/03 -0700, R. William Gosper wrote: >http://www.freewebz.com/vitaliy/triApplet/triGrav.html >is an interesting three-body simulation applet with colored, fading >trails. Unfortunately, you don't get to play with the initial >conditions, which are equal (point) masses, zero net momentum, zero net >angular momentum (wrt origin), fixed or slightly randomized initial >positions, and slightly randomized initial velocities. Chaos quickly >magnifies the initial perturbations into qualitatively different runs. > >The bodies spend some of their time "braiding", but most of their time >approximating two "two body problems", with a pair of bodies in a tight >orbit simulating a double mass about which the third body describes a >larger orbit that frequently crosses the screen boundaries. However, >due to the zero initial angular momentum, these larger orbits are highly >eccentric and terminate after only one period in a sort of "elastic >collision" which shuffles the orbital relationships. > >Sooner or later you have to restart because one of these >collisions leaves two bodies in such a tight, low energy orbit >that the liberated kinetic energy imparts the third body with >escape velocity, the tight pair flying off in the opposite >direction. (Occasionally, there is not quite escape velocity, > and the bodies return after several minutes.) > >So why don't triple star systems fly apart, too? One obvious >difference is that "collisions" are vastly less frequent in 3-space >than 2-space. Another is that heavenly masses are typically highly >unequal (e.g., Sun, Earth, Moon). Another possibility is spurious >energy buildup in the simulation from accumulated Runge-Kutta errors. >A sensitive test of this would be if we could initialize to the >recently discovered (barely) stable braiding orbit. > >But I think the main source of instability is the absence of net >angular momentum. My guess is that the author nulled out the >angular momentum because stability is visually boring compared >to braiding and "colliding", even at the cost of impermanence. >Or perhaps someone has found a chaotic triple star that proves >me wrong? >--rwg >PS: Does anyone know of tumbling brick/asteroid animation on the Web?

2 1

[math-fun] triple star
by R. William Gosper 04 Jul '03

04 Jul '03

http://www.freewebz.com/vitaliy/triApplet/triGrav.html is an interesting three-body simulation applet with colored, fading trails. Unfortunately, you don't get to play with the initial conditions, which are equal (point) masses, zero net momentum, zero net angular momentum (wrt origin), fixed or slightly randomized initial positions, and slightly randomized initial velocities. Chaos quickly magnifies the initial perturbations into qualitatively different runs. The bodies spend some of their time "braiding", but most of their time approximating two "two body problems", with a pair of bodies in a tight orbit simulating a double mass about which the third body describes a larger orbit that frequently crosses the screen boundaries. However, due to the zero initial angular momentum, these larger orbits are highly eccentric and terminate after only one period in a sort of "elastic collision" which shuffles the orbital relationships. Sooner or later you have to restart because one of these collisions leaves two bodies in such a tight, low energy orbit that the liberated kinetic energy imparts the third body with escape velocity, the tight pair flying off in the opposite direction. (Occasionally, there is not quite escape velocity, and the bodies return after several minutes.) So why don't triple star systems fly apart, too? One obvious difference is that "collisions" are vastly less frequent in 3-space than 2-space. Another is that heavenly masses are typically highly unequal (e.g., Sun, Earth, Moon). Another possibility is spurious energy buildup in the simulation from accumulated Runge-Kutta errors. A sensitive test of this would be if we could initialize to the recently discovered (barely) stable braiding orbit. But I think the main source of instability is the absence of net angular momentum. My guess is that the author nulled out the angular momentum because stability is visually boring compared to braiding and "colliding", even at the cost of impermanence. Or perhaps someone has found a chaotic triple star that proves me wrong? --rwg PS: Does anyone know of tumbling brick/asteroid animation on the Web?

3 3

Re: [math-fun] Emacs Tetris & statistics
by Henry Baker 30 Jun '03

30 Jun '03

This Emacs Lisp Tetris code is now available at: http://home.pipeline.com/~hbaker1/emacs/tetris.el ----- At 03:06 PM 6/20/03 -0700, Henry Baker wrote: >I have become intrigued by Tetris, not as a game, but >as an online packing problem. I'm not interested in >the optimum solution, per se, but in the statistics >of the problem. > >Normally, Tetris has 10 columns and 7 tetraminos -- >2x2 "block", 2 "L"'s (L, L', mirror images), 2 "Z"'s >(Z, Z', mirror images), 1 "T", and a 4x1 "line". Each >tetramino has an area of 4 units. These tetraminos show >up randomly, but with a uniform distribution -- the 7 different >types are equally distributed. > >I'm curious about the interaction between the packing >strategies/heuristics and the probability distribution of >the pieces. Everyone who has played the game has noticed >how the 4x1 pieces appear critical to achieving a high >score -- if they show up too rarely, you quickly run out >of space as things stack up. > >Tetris appears to be very close to "criticality", in the sense >that with the right heuristics and statistics, one might achieve >an unbounded score. One way to understand this phenomenon is to >embed enough quality-playing heuristics, and then play (automatically) >lots of games with slightly varying statistics of the pieces to see >how the average score changes. > >Clearly, on a Tetris board with 14 columns, one could devote every >pair of columns to a single piece type. Since each piece type can >efficiently pack with itself in a 2-wide column, and since each type >has the same probability and the same area, each of the column pairs >will fill at the same rate, on average. So only large variances will >cause the game to terminate. When the game is squeezed to only 10 >columns, things get much more interesting, as there does not appear >to be any similar strict "ghetto" strategy. > >I have taken the standard Lisp tetris code distributed with Emacs >and made some radical changes to allow the parameters of the game to be >modified. For example, you can now change the width (# columns) >of the game and choose the probability distribution (I use >Walker's algorithm, see Knuth, v.II). I intend to implement >backing up (so you can practise better), additional levels of >lookahead, automatic placement according to certain heuristics, >etc. > >If anyone else on this list is interested, I'll be happy to post the >code on my web site. I'll go with the usual Gnu GPL, and my changes >are public domain if anyone cares. I make no guarantees about quality >or reliability of the code, and it will get modified sporadically with >no warning. > >Henry Baker

1 0

Re: [math-fun] triple star
by Henry Baker 30 Jun '03

30 Jun '03

There is a group at the U. of Tokyo which developed a "GRAPE" ("gravity pipeline", I'm glad you asked) processor for doing massively parallel processing on these types of problems. See Supercomputer Conference from 2002 for more details (http://www.supercomp.org/sc2002/) They simulated 1.8 million particles/protoplanets in the vicinity of Jupiter, Uranus & Neptune to try to understand where comets come from. Apparently, large-scale simulations of this sort are on the "cutting edge" of parallel processing, because there are no known good methods for doing such large scale simulations. Barnes-Hut, Greengard, etc., are good theoretical results, but don't parallelize readily. There are quite a few PhD theses available in this area. At 06:12 PM 6/27/03 EDT, asimovd(a)aol.com wrote: >I am curious whether anyone has done large-scale simulations of point masses in 3-space with random initial positions and velocities, under Newtonian mechanics & gravity. > >I'm especially curious whether that's enough for galaxy-shaped objects to appear. > >--Dan

1 0

Re: [math-fun] triple star
by Henry Baker 28 Jun '03

28 Jun '03

Yes, but is this _Newtonian_ mechanics & gravity? Most astronomers that I know want to know about the real (relativistic) universe, not the Newtonian universe. Most of the articles I've seen recently appear to have relativistic mechanics built in. At 04:40 PM 6/27/03 -0700, Eugene Salamin wrote: >The answer is "yes" to both questions. This has been around for years >in the computational physics/astronomy journals. > >--- asimovd(a)aol.com wrote: >> I am curious whether anyone has done large-scale simulations of point masses >> in 3-space with random initial positions and velocities, under Newtonian >> mechanics & gravity. >> >> I'm especially curious whether that's enough for galaxy-shaped objects to >> appear. >> >> --Dan

2 1

Re: [math-fun] triple star
by asimovd＠aol.com 28 Jun '03

28 Jun '03

I am curious whether anyone has done large-scale simulations of point masses in 3-space with random initial positions and velocities, under Newtonian mechanics & gravity. I'm especially curious whether that's enough for galaxy-shaped objects to appear. --Dan

6 5

Ignore my previous message!!! Re: [math-fun] Probabilistic harmonic serie
by asimovd＠aol.com 24 Jun '03

24 Jun '03

I was trying to delete my initial thoughts -- which I think are wrong, anyway -- when I accidentally sent the message. Apologies. --Dan

1 0

Re: [math-fun] Probabilistic harmonic series
by asimovd＠aol.com 24 Jun '03

24 Jun '03

Harmut Holtzwart (hartmut.holzwart(a)allianz.de) asks << Related question not treated in Schmulands article: What is known about the distribution of Z = e_1 + 1/3 e_2 + 1/5 e_3 + 1/7 e_4 + .... with e_i i.i.d. +/-1? >> If X = sum from 1 to oo of e_k (1/k) is the random variable for the sum of the random harmonic series, then clearly Z = X_1 - 2*X_2 (where X_1 and X_2 are independent and have the same distribution as X).

1 0

Re: Re: [math-fun] Probabilistic harmonic series
by hartmut.holzwart＠allianz.de 24 Jun '03

24 Jun '03

Related question not treated in Schmulands article: What is known about the distribution of Z = e_1 + 1/3 e_2 + 1/5 e_3 + 1/7 e_4 + .... with e_i i.i.d. +/-1? Remark: If X is the random harmonic series, then X = Y * Z, where Y is equally distributed in (-1,1). Any hints would be appreciated. Cheers, Hartmut asimovd@aol.com@mailman.xmission.com on 06.05.2003 11:06:04 Bitte antworten an math-fun(a)mailman.xmission.com Gesendet von: math-fun-bounces(a)mailman.xmission.com An: math-fun(a)mailman.xmission.com Kopie: Thema: Re: [math-fun] Probabilistic harmonic series The question was, What is the distribution of the sum of the random harmonic series ±1 ± 1/2 ± 1/3 ± ... ? By amazing synchronicity, an article on this very subject, "Random harmonic series" by Byron Schmuland, appears in the May, 2003 issue of the American Mathematical Monthly and is available from the author's website. (Thanks, Neil, for pointing this out.) As E. Clark mentioned, the article's available for downloading at <http://www.stat.ualberta.ca/people/schmu/publications.html>. I haven't studied every detail of this paper, but it's very interesting, with a number of graphs of the distribution function and related functions (like the distribution function if the same question is asked about placing random signs in front of the series of *squares* of reciprocal integers). This paper rewards whatever level of perusal you feel like giving it. It uses a clever series-rearrangement trick to nail down the distribution function in question. The author proves that this distribution function is infinitely differentiable, though he wrote me in private e-mail that for 15 years before solving the question, he believed it would not even be differentiable at all. He wrote that he did not know whether it is real analytic. In case anyone is interested, I'll mention that I've proved it's in fact real analytic. --Dan ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun -------------------------------------------------------------------------------

1 0