April 2007 - mathfun@mailman.xmission.com

[math-fun] April 2007 update of multimagie.com
by Christian Boyer 23 Apr '07

23 Apr '07

The April 2007 update of www.multimagie.com/indexengl.htm is online. You will see a new page on the first bimagic square of primes, already announced through [math-fun], but also some other news. Reminder of the main unsolved problems. Intriguing, because on small objects. Is it possible to construct, using distinct integers: -a 3x3 magic square of squares? -a 3x3 semi-magic square of cubes? -a 4x4 magic square of cubes? or 5x5, 6x6, 7x7, 8x8? -a 5x5 bimagic square? -a ?x?x? multiplicative magic cube using distinct integers < 416? Christian.

2 1

[math-fun] Gray-Champernowne sequence [was Path Question]
by Fred lunnon 21 Apr '07

21 Apr '07

> On 4/16/07, James Propp <propp(a)math.wisc.edu> wrote: > > > > This topic provides me with a good opportunity to raise a question that has > > been on my mind for a year or two: > > > > Can anyone find an explicit construction of an infinite sequence S of 0's > > and 1's with the property that for any finite bit-string s, the relative > > frequency with which s occurs in the first N bits of S converges to > > (1/2)^(length of s) with error that falls like (log N)/N? > > > > Note that the Champernowne sequence A030190 has error 1/(log N). > > An explicit construction of Alon, Kohayakawa, Mauduit, Moreira and > > R\"odl allows one to achieve error 1/N^c for any exponent c greater > > than 2/3 (which beats what one would get from a random sequence of > > bits). [*Less than* 2/3? Gareth McCaughan] > > > > Jim Propp Suppose we lower our sights, and just try to improve the dismal performance of the Champernowne sequence. Here's a couple of plausible-looking upgrades: firstly, instead of cheerfully dropping initial zeros, at iteration n we append a block in which every binary n-bit word in full is concatenated; secondly, instead of the conventional binary ordering, we arrange these words in Gray-code order. Also I've just noticed that my program reverses the conventional digit-order within a word: least significant bit on the left! The blocks of this "Gray-Champernowne" sequence up to span n = 4 are: 0 1 00 10 11 01 000 100 110 010 011 111 101 001 0000 1000 1100 0100 0110 1110 1010 0010 0011 1011 1111 0111 0101 1101 1001 0001 At first sight these improvements appear singularly unsuccessful: the frequency of words of size n in block n still varies wildly from 1 to 2n-1. But a closer look reveals the astonishing fact that the frequencies of all smaller sizes m < n in block n are constant! For example, continuing up to span n = 10, every word of length m = 5 occurs in the final (cyclic) block 320 times; over the concatenated initial segment of the complete sequence, the frequencies vary only between 569 and 583. Of course, to satisfy Jim's constraint, the variation in frequency throughout each block must be estimated, rather than just at the boundaries ... Fred Lunnon

3 4

[math-fun] Re: Path Question
by James Propp 19 Apr '07

19 Apr '07

Fred Lunnon writes: >Even if the following were to work, it would hardly qualify as an "explicit" >construction: but for what it's worth, suppose we have already to hand >a (cyclic) deBruijn sequence S_n in which every binary word of length n occurs >as a factor exactly once. > >... > >Lest this all seem absurdly half-baked, here's an example: > >n = 4: 00101101 00001111 > >n = 5: 00101101 11010100010011 0000011111 A very nice idea! Can it be taken out to infinity? Jim

2 2

[math-fun] the terrible teens
by James Propp 19 Apr '07

19 Apr '07

When is 15 pronounced "FIF-teen", and when is it pronounced "fif-TEEN"? I'm a mathematician, and my wife teaches English as a Second Language, so you'd think we'd know the answer to this one, but the tacit rules followed by American speakers seem to be a bit complicated. When counting from one to twenty, we say "FIF-teen". When it's quarter past the hour and we're telling someone the time in hours and minutes, we say "fif-TEEN". When talking about a year in the 1500's, we say "FIF-teen". When talking about a young person's age, we say "fif-TEEN". When talking about how many dollars something costs, the two syllables get almost equal stress, but the first syllable gets slightly more. Do you folks agree with these examples? Is there a general rule lurking here for numbers between 12 and 20? Jim

6 6

[math-fun] Re: Path Question
by James Propp 18 Apr '07

18 Apr '07

I wrote: >Good question! What I think I mean is that if we let k denote the length >of s and define f(N) as the number of occurrences of s in the first N bits >of S, then the discrepancy d(N) = f(N) - (N-k+1)/2^k satisfies >|d(N)| < C (log N) / N for some constant C, when N is sufficiently large. Oops: make that "|d(N)| < C (log N)"! (Note that the difference between (N-k+1)/2^k and N/2^k is constant and hence less than log N for N sufficiently large; so another way to state the desired inequality is |f(N)/N - 1/2^k| < C (log N) / N.) I hope I have that right now... Fred Lunnon wrote: >Perhaps it's worth mentioning a bomb-proof but clumsier alternative. >deBruijn sequences --- (k!)^k^(n-1)/k^n disitnct ones, modulo cyclic shift >--- exist for every span n and base k (with k = 2 here). So at each iteration >pick any one with span n' = 2^n, then shift it until the previous one with >span n appears at the front. Can you explain in more detail how this works? I'm not seeing it. Jim

2 3

Re: [math-fun] the terrible teens
by David Gale 18 Apr '07

18 Apr '07

* This is not just a teen problem. The number is "twenty-ONE", but it's a "twenty-one" gun salute. Also, something else I never realized. The way we distinguish fif-TEEN from FIF-teen is not by making one syllable louder than the other but by raising or lowering the pitch. Maybe you already knew that. dg At 09:07 PM 4/17/2007, you wrote: >Thought I'd bagged one, but no: > >Henry V, Act I, scene I: > >CANTERBURY: Full fifteen earls and fifteen hundred knights, > Six thousand and two hundred good esquires; > >On 4/17/07, Thane Plambeck <tplambeck(a)gmail.com> wrote: >>Confirming the Speciner hypothesis, but there's got to be some iambic >>pentameter >>with the fifteen carrying the opposite stress I'd think: >> >>http://members.tripod.com/~charleswolff/ROTS/r1.html >> >>[ Turco86 ] describes an interesting variation on the sonnet, which he >>calls the Blues Sonnet. He describes the blues sonnet as "a triplet >>stanza derived from the Black jazz tradition of lamentation or >>complaint, rhyming Aaa. Usually written in loose iambic pentameter >>measures, the second line [is] an incremental repetition of the first >>line, and the third line is a synthetic parallel giving a consequence >>of the first two lines." An example, in strict iambic pentameter: >> >> The train she rides is fifteen coaches long. >> The train she rides is fifteen coaches long. >> The girl I love is on that train and gone. >> >>On 4/17/07, Mike Speciner <ms(a)alum.mit.edu> wrote: >> >> > Hypothesis: When fifteen is the last word of the phrase, it's pronounced >> > fifTEEN; otherwise it's FIFteen. >> > >> > --ms >> > >> > -----Original Message----- >> > From: math-fun-bounces+ms=alum.mit.edu(a)mailman.xmission.com >> > [mailto:math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com]On Behalf >> > Of James Propp >> > Sent: Tuesday, April 17, 2007 19:01 >> > To: math-fun(a)mailman.xmission.com >> > Subject: [math-fun] the terrible teens >> > >> > >> > When is 15 pronounced "FIF-teen", and when is it pronounced "fif-TEEN"? >> > >> > I'm a mathematician, and my wife teaches English as a Second Language, >> > so you'd think we'd know the answer to this one, but the tacit rules >> > followed by American speakers seem to be a bit complicated. >> > >> > When counting from one to twenty, we say "FIF-teen". >> > >> > When it's quarter past the hour and we're telling someone the time >> > in hours and minutes, we say "fif-TEEN". >> > >> > When talking about a year in the 1500's, we say "FIF-teen". >> > >> > When talking about a young person's age, we say "fif-TEEN". >> > >> > When talking about how many dollars something costs, the two syllables >> > get almost equal stress, but the first syllable gets slightly more. >> > >> > Do you folks agree with these examples? Is there a general rule lurking >> > here for numbers between 12 and 20? >> > >> > Jim >> > >> > _______________________________________________ >> > math-fun mailing list >> > math-fun(a)mailman.xmission.com >> > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >> > >> > _______________________________________________ >> > math-fun mailing list >> > math-fun(a)mailman.xmission.com >> > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >> >> >>-- >>Thane Plambeck >>tplambeck(a)gmail.com >>http://www.plambeck.org/ehome.htm > > >-- >Thane Plambeck >tplambeck(a)gmail.com >http://www.plambeck.org/ehome.htm > >_______________________________________________ >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: Path Question
by James Propp 18 Apr '07

18 Apr '07

I wrote: >Can anyone find an explicit construction of an infinite sequence S of 0's >and 1's with the property that for any finite bit-string s, the relative >frequency with which s occurs in the first N bits of S converges to >(1/2)^(length of s) with error that falls like (log N)/N? Dan Asimov asked: >May I ask for a clarification of exactly what >"error that falls like (log N)/N" means? Good question! What I think I mean is that if we let k denote the length of s and define f(N) as the number of occurrences of s in the first N bits of S, then the discrepancy d(N) = f(N) - (N-k+1)/2^k satisfies |d(N)| < C (log N) / N for some constant C, when N is sufficiently large. Note that I used (N-k+1)/2^k instead of N/2^k since a bit string of length k only gets N-k+1 chances to occur in a bit string of length N. Incidentally, that was a fun problem about the 3-torus, Dan! Jim

1 0

[math-fun] 3-state cellular automata with von Neumann neighborhood
by Dean Hickerson 18 Apr '07

18 Apr '07

Richard Schroeppel wrote: > It's easy to show that a cellular automaton with two states and a 4-cell > neighborhood (using only the orthogonally adjacent cells, and not the > diagonal cells) is relatively boring: The pattern > > - 0 - > 0 0 1 > - 0 - > > must produce a 1 in the center, or else the rule won't let patterns grow. > And if this pattern produces a 1, then patterns grow in all directions at > speed 1. (This does include Winograd's xor rule, which is surprising but > still has quite limited behavior complexity.) Conway's great idea was to > use the 8-cell neighborhood, including the diagonal neighbors. This leads > to Life, and a raft of interesting goodies. > My question: Suppose we stick with the 4-cell neighborhood, but break the > 2-state limitation. If we allow three states, can we get interesting stuff? We can get around the problem described above if we have the transitions - 0 - - 0 - 0 0 1 -> 2 and 0 0 2 -> 0 - 0 - - 0 - and some way for a 2 to change into a 1. I've been playing around with such rules for a few days. I haven't found any that are very Life-like, and I haven't found any good ones that have simple verbal descriptions like Life does. But there are some that are at least somewhat unpredictable. The most interesting that I've seen has a c/6 spaceship, two 2c/4 spaceships, an 8c/16 puffer producing period 6 oscillators, and a lengthening spaceship that grows at 8c/16 (producting a period 10 wick) and decays at c/7. The wickstretcher can also decay at 6c/22, leaving behind period 3 oscillators. For anyone using Mirek's Cellebration, here's a pattern showing all of those: #MCell 4.20 #GAME Neumann binary #RULE 3020220000200220000002000001220020000220220000000000000000000201 #RULE 0000000000010001001010101000101000001000000000101000001000010100 #RULE 0001000010000000000001000000000000210100010000000000010200200000 #RULE 0000000000000000002000000100000220000000200000000000 #BOARD 1500x1500 #WRAP 1 #CCOLORS 3 #L 27.A$28.A$28.A$27.A9$24.B..AA8$19.B$18.BA.A..B$19.BA.A4.AA$20.B8$8.B.B #L 11.A.B$B.B4.BA.AB4.A3.A.B4.AA$8.B.B11.A.B9$18.B8.AA$14.B3.AB.A..B$18.B #L 8$8.B.B7.B8.AA$7.BA.A.A.B3.AB.A..B$8.B.B7.B Small random patterns usually settle down to a few oscillators and some of the moving things shown above. Larger random patterns seem to grow slowly for a while, often emitting some of the things shown above. But eventually they also produce messy 2c/4 puffers, which increase the rate at which they expand, since such puffers emit perpendicular puffers, which emit others, etc., filling space with their debris. (Unfortunately, MCell on my old PC isn't fast enough to see much of that.) To describe the rule, I'll write "c/nesw -> d" to mean that if a cell is in state c and its neighbors to the north, east, south, and west are in states n, e, s, and w, respectively, then the cell will change to state d in the next generation. The rule is symmetric, so I'll only list one transition from each equivalent group. E.g. 0/0001 -> 2 also implies 0/0010 -> 2, 0/0100 -> 2, and 0/1000 -> 2. The rule is: 0/0001 -> 2 0/0011 -> 2 0/0111 -> 2 0/1111 -> 2 0/0202 -> 2 0/0222 -> 1 1/0000 -> 1 1/0002 -> 1 1/0011 -> 1 1/0101 -> 1 1/1112 -> 1 1/2222 -> 1 2/0000 -> 1 2/0002 -> 1 2/0202 -> 2 2/0212 -> 2 Except for these, all transitions have the form c/nesw -> 0. This rule convinces me that there are interesting ones of this type, but it's probably not the best of the bunch. Dean Hickerson dean(a)math.ucdavis.edu

1 0

[math-fun] Permuter Puzzle
by David Wilson 18 Apr '07

18 Apr '07

Suppose you have a box with a hole on the top and the side. When you feed 10 marbles into the top hole, a mechanism in the box shuffles the marbles and sends them out in a specific permuted order. If you have 5 identical white and 5 identical black marbles, how many tries are necessary to determine the permutation?

2 1

Re: [math-fun] Re: Path Question
by Daniel Asimov 17 Apr '07

17 Apr '07

Jim writes: << Can anyone find an explicit construction of an infinite sequence S of 0's and 1's with the property that for any finite bit-string s, the relative frequency with which s occurs in the first N bits of S converges to (1/2)^(length of s) with error that falls like (log N)/N? >> May I ask for a clarification of exactly what "error that falls like (log N)/N" means? I think I know what this means, but would like to see the condition expressed in formal language, just to be certain. --Dan

1 0