April 2019 - mathfun@mailman.xmission.com

Re: [math-fun] Restaurant placemat mazes
by Keith F. Lynch 10 Apr '19

10 Apr '19

James Propp <jamespropp(a)gmail.com> wrote: > I?m looking for an example of a maze that could be challenging > (just a little) if you approach it in the naive way ? start at the > beginning, make choices along the way, backtrack when a choice leads > to a dead end ? but becomes easy when you construct the solution > path from both ends. (These are the sort of mazes I remember > finding on restaurant placemats when I was young.) There are actually four ends if you also try to solve the dual of the maze, i.e. to follow the solid lines rather than the spaces between them. Doing so rules out areas of the maze that can be ignored. I used such duals to think about random mazes. Consider a large square lattice, i.e. a large square tiled with a large number of identical small squares that meet at their corners. Some proportion of the edges of the small squares are randomly and independently removed. My first question was, if you're dropped into a random small square near the middle of such a maze, what's the expected number of other small squares you can reach, as a function of the proportion of removed edges? It occurred to me that it's always either possible to traverse the maze west-to-east or to traverse the dual of the maze north-to-south, never both and never neither. (There can be a canal though Panama or a highway between North and South America, but not both (ignoring bridges and tunnels)). And the dual is the same size as the original maze, just with the probability of an edge being missing being changed to one minus that probability. As such, there must be a phase transition at exactly 0.5. If more than half the edges are removed, you can probably visit most of the small squares. Otherwise, you almost certainly can't. (Nitpick: They aren't quite the same size, due to fencepost error. This can be fixed by removing, e.g., all west edges from the westernmost small squares and all south edges from the southernmost small squares.) > Abstractly, such a maze is associated with a weighted graph, where > the vertices represent choice-points, the edges represent (twisty > but choice-free) path-segments, and the weight of an edge represents > the length of the path-segment. (I mention this to facilitate > possible future discussion of ?How could we quantify how hard it is > to solve a maze via the naive backtracking approach?? but won?t > discuss it further.) I associate my random maze with a graph, but a little differently. Every small square is a node. A graph-edge between nodes exists only if the small squares are adjacent and the maze-edge between them is missing. Also, every small square is adjacent to itself. I then construct an adjacency matrix. (Actually, I *start* with the adjacency matrix.) An adjacency matrix has both a row and a column for every node. Matrix element A,B is 1 if nodes A and B are adjacent (i.e. an graph-edge links them), otherwise 0. Raise the matrix to the Nth power, and matrix element A,B will equal the number of ways to get from A to B in N or fewer steps. Most of these ways involve senseless drunkard's walks, and the numbers get very large very quickly. So you might as well reset all non-zero matrix values to 1 at each step. Stop multiplying matrices when the number of zeros in the Nth power matrix stops going down. The matrix then tells you which small squares can be reached from which other small squares. The number of non-zero entries in the A row is how many small squares can be reached from A. Of course you can do the same with the dual of the graph. That's perhaps more intuitive, since the corners are nodes and the maze- edges are graph-edges. I haven't yet figured out how to generalize my dual insight to three-dimensional graphs. Non-mathematical digression: I've long been fascinated by mazes. They're perhaps the first mathematical concept I was exposed to, other than counting, simple shapes, and possibly addition. I'm the anti Marie Kondo. Since I pay more for space than for everything else put together, I consider any empty space in my home in excess of that which I need to access my stuff to be a waste of money. So I keep everything unless I'm certain I will never have any use for it. This of course makes my home a maze. > Of course such tactics do you no good if you?re actually walking > through a maze! You haven't said whether you're restricting the mazes to those with only one path. If there's only one path, you can always find it by keeping your right hand on the wall as you walk forwards. (Or your left hand, but don't switch hands in the middle.)

3 2

[math-fun] That curve I regrettably named flowsnake
by Bill Gosper 10 Apr '19

10 Apr '19

Mandelbrot detested the name. Then he discovered a spacefill of Koch's Snowflake. The worthy claimant to the Flowsnake name! Which he still detested. I recently realized how little I know about my own curve, which fills the FranceFlake, the fundamental region for the positional number system Base: 2 + i^(2/3) = √7 e^(i arccos(11/14)/2) and the (necessarily) seven digits 0 and the 6th roots of 1. If FranceFill(0)= 0+0i, FranceFill(1) = 1 + 0i: 1) What is the area of a FranceFlake? 2) Where is its centroid? 3) Is its circumradius √(52/147) ? 4) Ironically, it was popular partly for how completely its canonical sampling (at 0/7, 1/7,...,1) self-avoided. But like all true spacefills, it is *dense* with *triple* points. E.g., what are the preimages of (9 + i √3)/21? —rwg

2 2

[math-fun] [arndt@jjj.de: Re: To Joerg Re: Fun with shift register sequences (connecting A000031 and A000016)]
by Joerg Arndt 08 Apr '19

08 Apr '19

Mostly to Dan Asimov. Earthlink doesn't like my mail server, the message below wasn't delivered. Best regards, jj ----- Forwarded message from Joerg Arndt <arndt(a)jjj.de> ----- Date: Sun, 7 Apr 2019 14:00:08 +0200 From: Joerg Arndt <arndt(a)jjj.de> To: Dan Asimov <dasimov(a)earthlink.net> Subject: Re: To Joerg Re: [math-fun] Fun with shift register sequences (connecting A000031 and A000016) * Dan Asimov <dasimov(a)earthlink.net> [Apr 03. 2019 13:07]: > Joerg, > > Maybe I missed something, but I don't know what necklaces you are > referring to here. > > I thought it might be all circular sequences of two colors of beads, > but your examples don't seem to confirm that. That is correct. I show only the primitive part, so instead of . ....1 ...11 ..1.1 ..111 .1.11 .1111 1 you may want to see ..... ....1 ...11 ..1.1 ..111 .1.11 .1111 11111 (first and last have period 1). Does this make things clear? Best regards, Joerg > > I hope you won't mind clarifying ... > > Thanks, > > Dan > > > Joerg Arndt a Ã©crit: > ----- > To generate the necklaces for length n... > ... > ... > ----- ----- End forwarded message -----

1 0

[math-fun] Restaurant placemat mazes
by James Propp 06 Apr '19

06 Apr '19

I’m looking for an example of a maze that could be challenging (just a little) if you approach it in the naive way — start at the beginning, make choices along the way, backtrack when a choice leads to a dead end — but becomes easy when you construct the solution path from both ends. (These are the sort of mazes I remember finding on restaurant placemats when I was young.) Abstractly, such a maze is associated with a weighted graph, where the vertices represent choice-points, the edges represent (twisty but choice-free) path-segments, and the weight of an edge represents the length of the path-segment. (I mention this to facilitate possible future discussion of “How could we quantify how hard it is to solve a maze via the naive backtracking approach?” but won’t discuss it further.) Example: Picture a maze in which your goal is to get from A to D, in which the solution path goes from A to B to C to D (here A, B, C, and D are choice-points and there are no other choice-points along the path). Suppose that all the paths from A lead to dead ends pretty quickly except the one to B, and that all the backward paths from D lead to dead ends pretty quickly except the one to C, and that there is a short path from B to C, but that there are lots of paths from B and from C that take a long time to lead to dead ends. If you try to solve the maze naively, you might explore lots of the long paths from B that lead to dead ends (possibly by way of other choice points); and even if by luck one of the first paths from B that you try is the one that leads to C, you might take a bad path from C. But if you work from both A and D, you quickly discover that both B and C must lie along the solution path, so you’ve reduced the problem “How do I get from A to D?” to the problem “How do I get from B to C?”, and there’s a short path that does that which you can easily find once you think to look for it. I’d like to include such a maze in one of my monthly essays, as a metaphor for the process of constructing proofs. But I don’t want to construct such a maze myself, and I don’t want to just type “maze” into Google Images and try maze after maze after maze until I find what I want. Ideally I’d like two mazes: one as described above, and one that’s even easier because the B and C vertices are the same. (That’s like constructing a proof from both ends where you discover that no actual ideas are needed; e.g., where you prove that two complicated expressions are equal by putting them in standard form.) Surely someone has written about the work-from-both-ends tactic, and has an example that I could borrow (with permission). The Wikipedia page on mazes didn’t talk about it, though it mentions dead-end filling, which is similar in spirit. Of course such tactics do you no good if you’re actually walking through a maze! But they work pretty well if the maze is placemat-sized and you’re hovering above it, pencil in hand. Jim Propp

2 2

[math-fun] [math-] Fun with shift register sequences (connecting A000031 and A000016)
by Bill Gosper 03 Apr '19

03 Apr '19

-------- Original Message -------- Date: 2019-04-01 07:18 From: Joerg Arndt <arndt(a)jjj.de> To: math-fun <math-fun(a)mailman.xmission.com> Reply-To: math-fun <math-fun(a)mailman.xmission.com> To generate the necklaces for length n... Let N = 2^n and f(j) = 2*j if j < N/2, otherwise (2*j+1) (mod N). This induces a permutation of the elements [0...N-1]. Now write down the cycles, and for a cycle (r, s, t, ..., z), map its elements to {0,1} using m(x) = 0 if x < N/2, otherwise 1. An example for n=5. The cycles are (0) (1 2 4 8 16) (3 6 12 24 17) (5 10 20 9 18) (7 14 28 25 19) (11 22 13 26 21) (15 30 29 27 23) (31) The map m gives (dots for zeros) . ....1 ...11 ..1.1 ..111 .1.11 .1111 1 These are the primitive parts of the necklaces of length n. In other words: the Lyndon words whose length divide[s] n. (Btw. for n prime this gives a neat algorithm to generate a random Lyndon word of length n with just n operations). This is implied in section "Example using inverse Burrows-Wheeler transform" in https://en.wikipedia.org/wiki/De_Bruijn_sequence All this is likely known but I have not seen it in this particular form. (Btw. the generalization from binary to k-ary is easy). Now here is a twist: Using the map f(j) = 2*j if j >= N/2, otherwise (2*j+1) (mod N). (note "j >= N/2", the condition is "swapped") and otherwise the procedure above I get n = 0: . # = 1 n = 1: .1 # = 1 n = 2: ..11 # = 1 n = 3: ...111 .1 # = 2 n = 4: ....1111 ..1.11.1 # = 2 n = 5: .....11111 ...1.111.1 ..1..11.11 .1 # = 4 n = 6: ......111111 ....1.1111.1 ...1..111.11 ...11.111..1 ..1.1.11.1.1 ..11 # = 6 n = 7: .......1111111 .....1.11111.1 ....1..1111.11 ....11.1111..1 ...1...111.111 ...1.1.111.1.1 ...11..111..11 ..1..1.11.11.1 ..1.1..11.1.11 .1 # = 10 These do seem to be the shift register sequences counted in A000016. IS THIS CORRECT? If it is, I'll enter comments to both sequences. Best regards, jj Golly animation of a shift register sequence: #Life 1.05 #D Pseudorandom LWSS generator with p46 logic #D A lightweight spaceship stream is emitted representing a #D pseudorandom binary sequence satisfying the recursion #D a[n] = a[n-1] XOR a[n-19]. (By spreading out the pattern, #D the 19 can be changed.) The sequence has period 413385, #D so the gun has period 46*413385 = 19015710. #D Built by Bill Gosper, October 1989 or earlier #D (Header by Dean Hickerson, 4/11/93) x = 167, y = 139, rule = B3/S23 77b2o7b2o$77b2o6bo2b2o$76bo2bo4b6o$77b2obo5b4o$77b2obo2$77b2obo$77b2ob o5b4o$74b2ob3o4b6o11b2o$74bobobo6bo2b2o11b2o$75b4o7b2o$76b2o40$22b2o$ 22b2o5$157b2o$157b2o5$23b2o3b2o5$21b2obo3bob2o$21bo2bo3bo2bo$22b3o3b3o 126b2o5b2o$156bobo5bobo$156bo2bo3bo2bo$157b2o5b2o5$22b2o$22b2o5$157b2o $157b2o9$2b2o$2b2o6$2b3o3b3o$bo2bo3bo2bo$bo3bobo3bo$2obobobobob2o$2ob 2o3b2ob2o69b2o$b3o5b3o69bo2b2o$49b2o30bo3bo$48bo2bo30bo2bo$48bo2bo30b 3o$49b3o$82b3o$9bo72bo2bo$8bobo58b2o10bo3bo10b2o$7bo3bo37b3o17b2o10bo 2b2o10b2o$7b5o24b2o10bo2bo11b2o17b2o$6bobobobo23b2o10bo2bo11b2o$7bo3bo 37b2o2$7bo3bo$6bobobobo$2b2o3b5o76b2o$2b2o3bo3bo75bobo$8bobo75b2obo$9b o38b3o3bo32b2o26b2o$46b5o2bobo32bo25b2ob2o$41bo3b2o3b2o3bo59bo2bo$36bo 3bo4b3o3bo2bo33bo26bo2bo$35bo8bob2o3b3o33b2o27b2o$35bo2b2o5bo32b2o6b2o bo$36b2o5bo2b2o3b3o24b2o7bobo26b2o$37b3o3b5o3bo2bo33b2o25bo2bo$45b2o3b 2o3bo12b2o45bo2bo6b2o$37b3o3b8o2bobo12b2o44b2ob2o6b2o$36b2o5bo2bob3o3b o60b2o$21b2o12bo2b2o5bo$21b2o12bo8b2o$36bo3bo$41bo! Period 46 ⨉ 2088705 = 96080430 version (stifled) x = 180, y = 162, rule = B3/S23 56b2o7b2o$56b2o6bo2b2o$55bo2bo4b6o$56b2obo5b4o$56b2obo2$56b2obo$56b2ob o5b4o$53b2ob3o4b6o11b2o$53bobobo6bo2b2o11b2o$54b4o7b2o$55b2o40$b2o5bo$ b2o4b3o$6b2ob2o2$5bobobobo2$6b2ob2o$6b2ob2o$8bo9$2obo3bob2o$o2bo3bo2bo $b3o3b3o8$b2o$b2o$159b2o$159b2o12$160bo5bo$159b3o3b3o$158bo3bobo3bo$ 158bo9bo$159b3o3b3o5$161b2ob2o$162bobo$158b2ob2ob2ob2o$158bo2bo3bobo$ 158bo7bo$158bo2bo$159b2o9$4b2o$4b2o172b2o$178bo$176bobo$46bo2bo42bo2bo 42bo2bo34b2o$24b4o22bo19b4o22bo19b4o22bo19b4o$23bo3bo18bo3bo18bo3bo18b o3bo18bo3bo18bo3bo18bo3bo$4b3o3b3o14bo19b4o22bo19b4o22bo19b4o22bo$3bo 2bo3bo2bo9bo2bo42bo2bo42bo2bo42bo2bo$3bo3bobo3bo$2b2obobobobob2o69b2o$ 2b2ob2o3b2ob2o59b2o10bo$3b3o5b3o9b2o47bo3b2o5b2o2bo$22b2o17b2o7b3o19bo 4bo6bo2bo$24bo15bo2bo4bo4bo18bo3b2o7bobo$40bo2bo4bo5bo19b2o9b2o$40bo3b o8bo$41b2o8b2o32b2o32b3o$11bo73bobo33bo$10bobo28b2o8b2o18b2o11bo2bo10b 2o20bo$9bo3bo30bo8bo17b2o10b2o2bo10b2o$9b5o24b2o8bo5bo10b2o19bo$8bobob obo23bo9bo4bo11b2o17b2o$9bo3bo21bo6bo7b3o$34b2o3bo2bo$9bo3bo20bobo$8bo bobobo$4b2o3b5o76b2o$4b2o3bo3bo75bobo16b2o$10bobo75b2obo15bobo$11bo38b 3o3bo32b2o18bo7b2o$48b5o2bobo32bo25b2ob2o$43bo3b2o3b2o3bo59bo2bo$38bo 3bo4b3o3bo2bo33bo26bo2bo$37bo8bob2o3b3o33b2o27b2o$37bo2b2o5bo32b2o6b2o bo$38b2o5bo2b2o3b3o24b2o7bobo26b2o$39b3o3b5o3bo2bo33b2o25bo2bo$47b2o3b 2o3bo12b2o45bo2bo6b2o$39b3o3b8o2bobo12b2o44b2ob2o6b2o$38b2o5bo2bob3o3b o60b2o$23b2o12bo2b2o5bo$23b2o12bo8b2o$38bo3bo$43bo! (If you are a sequence person but not a Golly person, you're missing out.) —rwg

1 0

[math-fun] Best geometric representation of a number
by Dan Asimov 02 Apr '19

02 Apr '19

Some years ago we discussed the optimal not-too-symmetrical egg shape. I sometimes enjoy a hobby of trying to represent a positive integer by an arrangement of dots in the plane (or sometimes 3-space), as symmetrical as possible. This can be fun, but there are still plenty of degrees of freedom. Say N = 4. Should it be the 4 corners of a square in R^2, or maybe the corners of a regular tetrahedron in R^3 ??? (We're not concerned here with how the dot pattern is depicted, just with the conceptual arrangement. Or technically, generalized to any given integer N > 0: Question: ----- What metric should we put on N points to make it best represent N-ness??? ----- NOTE: This is *more general* than the original question. I'm most interested in this more general question. So, a challenge: Come up with the most symmetrical N-dot arrangements, in your opinion, for N equal to each of the first 100 positive integers. No, ignore that. Here's the *real question*: The *real question*: -------------------- If you were the judge of such a contest, what is the optimal mathematical criterion to use to judge it as fairly as possible? ----- Note: ----- * If morally speaking, ties for first place are inevitable (as they may be for at least some N), then the optimal judging criterion should recognize such ties. * Even better than merely picking best or tied for best would be a mathematically defined: *partial ordering on all entries*. ----- —Dan

1 0

[math-fun] Fun with shift register sequences (connecting A000031 and A000016)
by Joerg Arndt 01 Apr '19

01 Apr '19

To generate the necklaces for length n... Let N = 2^n and f(j) = 2*j if j < N/2, otherwise (2*j+1) (mod N). This induces a permutation of the elements [0...N-1]. Now write down the cycles, and for a cycle (r, s, t, ..., z), map its elements to {0,1} using m(x) = 0 if x < N/2, otherwise 1. An example for n=5. The cycles are (0) (1 2 4 8 16) (3 6 12 24 17) (5 10 20 9 18) (7 14 28 25 19) (11 22 13 26 21) (15 30 29 27 23) (31) The map m gives (dots for zeros) . ....1 ...11 ..1.1 ..111 .1.11 .1111 1 These are the primitive parts of the necklaces of length n. In other words: the Lyndon words whose length divide n. (Btw. for n prime this gives a neat algorithm to generate a random Lyndon word of length n with just n operations). This is implied in section "Example using inverse Burrows-Wheeler transform" in https://en.wikipedia.org/wiki/De_Bruijn_sequence All this is likely known but I have not seen it in this particular form. (Btw. the generalization from binary to k-ary is easy). Now here is a twist: Using the map f(j) = 2*j if j >= N/2, otherwise (2*j+1) (mod N). (note "j >= N/2", the condition is "swapped") and otherwise the procedure above I get n = 0: . # = 1 n = 1: .1 # = 1 n = 2: ..11 # = 1 n = 3: ...111 .1 # = 2 n = 4: ....1111 ..1.11.1 # = 2 n = 5: .....11111 ...1.111.1 ..1..11.11 .1 # = 4 n = 6: ......111111 ....1.1111.1 ...1..111.11 ...11.111..1 ..1.1.11.1.1 ..11 # = 6 n = 7: .......1111111 .....1.11111.1 ....1..1111.11 ....11.1111..1 ...1...111.111 ...1.1.111.1.1 ...11..111..11 ..1..1.11.11.1 ..1.1..11.1.11 .1 # = 10 These do seem to be the shift register sequences counted in A000016. IS THIS CORRECT? If it is, I'll enter comments to both sequences. Best regards, jj

1 0