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

Re: [math-fun] Strip of squares in space puzzle (new & improved)
by Dan Asimov 17 Mar '18

17 Mar '18

As always, I need to adjust the wording of a previous post, the SSS puzzle (corrected version below). I neglected to add one essential condition. So I will restate the whole thing from scratch with better numbering. The only actual difference is the addition of 4., which I had accidentally left out — sorry! — and question C. Strip of squares in space puzzles (new & improved): --------------------------------------------------- Let a "strip of squares in space" (SSS) satisfy these conditions: 1. An SSS X is a union, of some collection of unit squares in R^3, with all vertices having integer coordinates. 2. Each square Q in X intersects exactly 2 other squares (Q-, Q+) in the strip along *entire edges*. 3. The edges in 2. are *adjacent edges* in Q. 4. The 3 squares Q, Q-, Q+ mentioned in 2. lie in mutually perpendicular planes. 5. There may exist additional intersections between pairs of squares of X, as long as these are only along common vertices. Let the "size" of X be how many squares are in X. PUZZLES: ------- A. What is the smallest number of squares in an SSS that is topologically a cylinder, if possible? B. What is the smallest number of squares in an SSS that is topologically a Möbius band, if possible? C. What is the smallest number of squares in an SSS that is knotted? (I still don't know the answers.) —Dan -----

1 0

[math-fun] Strip of squares in space puzzle
by Dan Asimov 17 Mar '18

17 Mar '18

Let a "strip of squares in space" (SSS) satisfy these conditions: 1. An SSS X is a union of a collection of unit squares in R^3, with all vertices having integer coordinates. 2. Each square Q in X intersects exactly 2 other squares in the strip along *entire edges*, and these are *adjacent edges* in Q. 3. There may exist additional intersections between pairs of squares of X, as long as these are only along common vertices. Let the "size" of X be how many squares are in X. PUZZLES: ------- A. What is the smallest number of squares in an SSS that is topologically a cylinder, if possible? B. What is the smallest number of squares in an SSS that is topologically a Möbius band, if possible? (Actually I shouldn't call it a puzzle, since I don't know the answers.) —Dan

3 2

[math-fun] Deterministic scheduling of Zipf's Law visits ?
by Henry Baker 17 Mar '18

17 Mar '18

Suppose that I'm a Fedex driver and I have N houses to visit, but only exactly 1 house every day (i.e., this is NOT a route planning problem). Since I'm an unimaginative Fedex driver, it's simply easier to go to the houses in the same order every cycle of days, whether or not I have something to deliver. I'd like to come up with a *simple* house visit scheduling algorithm with the following properties: * For each N, the output is a *fixed* *cyclic* schedule; i.e., after some # of days the entire schedule repeats; we'd like the cycle length to be relatively short and will accept some amount of deviation from Zipf's Law in return * The % of visits to house #i in each cycle is very roughly proportional to 1/i * Ideally, the deliveries to house #i should be spread out as much as possible -- i.e., not all bunched together on successive days * The schedule for N+1 houses is simply computed from the schedule for N houses (alternatively, the schedule for N is computed from an a priori fixed number of schedules from smaller N's) Here's an example of what NOT to do for Zipf's Law: Suppose we have 4 houses, with visits scheduled like so: 1 1 2 1 2 3 1 2 3 4 Thus, we have 10 total visits each cycle, but the ratios are 40%, 30%, 20%, 10% -- i.e., this is a linear "tail", rather than a Zipf's Law tail. Is there such an algorithm which approximates a Zipf's Law distribution? What about other power laws/long-tail distributions -- e.g., i^(-2) ? Other common distributions?

3 3

Re: [math-fun] Deterministic scheduling of Zipf's Law visits ?
by Henry Baker 17 Mar '18

17 Mar '18

Adam, that's very cool! Another not-so-long-tail interesting case is i^(-3/2). I can't think of an elegant enumeration. "not-so-long-tail" <=> integral converges. 4-house case: quite a steep dropoff (needs to be unbunched): 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 4 4 27 total visits ~ 1 month cycle. --- BTW, I know nothing of "Jim Propp's de-randomization tricks". They sound quite interesting. Any references/links? At 12:27 PM 3/17/2018, Adam P. Goucher wrote: >For the n^-2 case, a beautiful aperiodic solution is to visit house >gcd(a, b) at time t, where T(a) is the largest triangular number below >t, and b = t - T(a). > >Best wishes, > >Adam P. Goucher > >> Sent: Saturday, March 17, 2018 at 4:53 PM >> From: "Michael Kleber" <michael.kleber(a)gmail.com> >> To: math-fun <math-fun(a)mailman.xmission.com> >> Subject: Re: [math-fun] Deterministic scheduling of Zipf's Law visits ? >> >> This sounds like a problem for Jim Propp's de-randomization tricks -- >> converting a random method that has the right asymptotic distribution to a >> deterministic method that approximates its behavior. But I don't know what >> the random method with Zipfian distribution would be. >> >> --Michael >> >> On Sat, Mar 17, 2018 at 11:07 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> >> > Suppose that I'm a Fedex driver and I have N houses to visit, but only >> > exactly 1 house every day (i.e., this is NOT a route planning problem). >> > Since I'm an unimaginative Fedex driver, it's simply easier to go to the >> > houses in the same order every cycle of days, whether or not I have >> > something to deliver. >> > >> > I'd like to come up with a *simple* house visit scheduling algorithm with >> > the following properties: >> > >> > * For each N, the output is a *fixed* *cyclic* schedule; i.e., after some >> > # of days the entire schedule repeats; we'd like the cycle length to be >> > relatively short and will accept some amount of deviation from Zipf's Law >> > in return >> > >> > * The % of visits to house #i in each cycle is very roughly proportional >> > to 1/i >> > >> > * Ideally, the deliveries to house #i should be spread out as much as >> > possible -- i.e., not all bunched together on successive days >> > >> > * The schedule for N+1 houses is simply computed from the schedule for N >> > houses (alternatively, the schedule for N is computed from an a priori >> > fixed number of schedules from smaller N's) >> > >> > Here's an example of what NOT to do for Zipf's Law: >> > >> > Suppose we have 4 houses, with visits scheduled like so: >> > >> > 1 >> > 1 2 >> > 1 2 3 >> > 1 2 3 4 >> > >> > Thus, we have 10 total visits each cycle, but the ratios are 40%, 30%, >> > 20%, 10% -- i.e., this is a linear "tail", rather than a Zipf's Law tail. >> > >> > Is there such an algorithm which approximates a Zipf's Law distribution? >> > >> > What about other power laws/long-tail distributions -- e.g., i^(-2) ? >> > Other common distributions? >> -- >> Forewarned is worth an octopus in the bush.

1 0

[math-fun] complex #'s explore circle group; quaternions explore SU(2) ?
by Henry Baker 17 Mar '18

17 Mar '18

We know that the circle group is enumerated uniformly by cos(t)+i*sin(t), for i in [0,2*pi) using a single (real) parameter t. Is there a way of uniformly enumerating the unit quaternions * with 1 parameter (probably some sort of random walk) ? * with 2 parameters (probably some sort of random walk) ? * with 1 complex parameter ????? * with 3 parameters ???

3 5

[math-fun] RUPORT POSTS?
by John E. Wetzel 17 Mar '18

17 Mar '18

A friend told me that sometime in the recent past there were posts on this list having to do with the Rupert property of solids. [You will recall that in the 17th century Prince Rupert of the Rhine won a wager that a hole could be cut in a cube large enough that a second cube of the same size could pass completely through it.] Now that I am a list member, I suppose I could browse through the Archives month by month and eventually find what is there to be found. But I hope that some member with a long memory can tell me approximately when the Rupert property was discussed and give me a time-saving lead. I would be most grateful for any such assistance. As a new member, I'm not yet familiar with the practices and customs of posting to this list, so forgive me please if I inadvertently have trod on anyone's sensibilities. John Wetzel

3 2

Re: [math-fun] complex #'s explore circle group; quaternions explore SU(2) ?
by Henry Baker 16 Mar '18

16 Mar '18

Hi Rich: I'm not SUre that I understand your dimensions and trees. "All directions": is this in 3-space or 4-space? Is there any relation to the 24 Hurwitz quaternions? At 04:47 PM 3/15/2018, rcs(a)xmission.com wrote: >It's a different covering structure, but the products of 2+-i, 2+-j, 2+-k >generate a dense covering of all directions. (Divide the generators >by sqrt5 to get units.) Except for the cancellations of conjugates, >like (2+i)(2-i) = 5, every product is different. You can view the >pre-space as a tree with node degree 5, except the root is degree 6. >The post-space is points on the unit quaternion sphere. I assume the >covering is near uniform, but haven't seen the confirming theorem.

2 1

Re: [math-fun] Does this int seq have a name?
by Henry Baker 16 Mar '18

16 Mar '18

Yes, the 2nd sequence consists of the numerators to the convergents of 2pi. The 1st sequence is similar to the second, except that these are numerators of convergents that are always slightly > 2pi. More precisely, the 2nd sequence are N>1 s.t. 0<mod(N,2pi)<mod(M,2pi) for 0<M<N. The 1st sequence: N>1 s.t. 0<|rem(N,2pi)|<|rem(M,2pi)| for 0<M<N; rem(x,y) is least absolute remainder of x/y. Here's the setup (see yesterday's post re "exploring the circle group"): We all know that |exp(iN)|=1. But we're now interested in those N for which exp(iN)~1 (i.e., w/o the absolute value). exp(iN)=exp(i)^N "explores" the circle group uniformly; it just doesn't do it in a continuous fashion (unless someone here has a better ordering/metric for the circle group). Which now raises an interesting question: Given a unit complex number z (i.e., |z|=1), we'd like to find a good N, s.t. exp(i)^N ~ z. I.e., given a real tolerance epsilon>0 and complex z s.t. |z|=1, we'd like to find the smallest N>0, s.t. |exp(i)^N - z|<epsilon. Are there efficient algorithms to find such N's ? This question is almost, but not quite, the same as discreet logs (i.e., logs capable of protecting privacy). Also, check out CORDIC: https://en.wikipedia.org/wiki/CORDIC At 10:12 AM 3/16/2018, Allan Wechsler wrote: >OEIS recognized the second one: see http://oeis.org/A046955 > >You should submit the first, and add cross-references. > >On Fri, Mar 16, 2018 at 12:27 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> 1,7,13,19,44,377,710,104703,... >> >> and another closely related sequence >> >> 1,6,19,25,44,333,710,103993,... >> >> They are both monotonically increasing. >> >> This posting should have been made on pi day. >> >> The sequences are related to CORDIC.

2 1

[math-fun] Does this int seq have a name?
by Henry Baker 16 Mar '18

16 Mar '18

1,7,13,19,44,377,710,104703,... and another closely related sequence 1,6,19,25,44,333,710,103993,... They are both monotonically increasing. This posting should have been made on pi day. The sequences are related to CORDIC.

2 1

Re: [math-fun] XCT instruction
by Henry Baker 16 Mar '18

16 Mar '18

Problems with XCT (execute one instruction): * no clean/obvious semantics; semantics have to be worked out for each different instruction being "executed" * only one level of execute (at least for IBM) * originally used for *tables* of instructions, but what about variable-length instructions? (Similar problem to "skip" instructions) * what are the semantics in the case of interrupts? We now have architectures which support "virtual machines"; analogous problems at much larger scale. At 04:47 PM 3/15/2018, rcs(a)xmission.com wrote: >PS: Does anyone else miss the XCT instruction? The 7094 & PDP6/10 had >it, but it seems to have vanished. I guess it's an architectural >nightmare for the hardware folks. --Rich

7 9