December 2002 - mathfun@mailman.xmission.com

Re: [math-fun] Maximum orbit of an n-bit register with monotonic update rule
by Henry Baker 06 Dec '02

06 Dec '02

Power consumption per unit area, partially due to 'leakage current' from transistors which are 'turned off', is currently one of the largest problems at the highest levels of integration. So, yes, real estate -- per se -- is not quite as big of a deal, although it is still very expensive. At 10:00 PM 12/5/02 -0500, Allan C. Wechsler wrote: >At 10:03 AM 11/30/02 -0500, Tom Knight wrote: >> A 3-metabit counter begins to count like this: >> > >> > 10 10 10 >> > 10 10 01 >> > 10 01 10 >> > 10 01 01 >> >>This is a very common strategy in current generation (hardware) logic >>design, where certain logic styles such as domino logic allow only >>monotonic logic functions. Using so-called "dual rail" logic, >>representing each bit in both possible polarities, and generating, at >>each stage, both possible polarities, allows this to be a general >>logic family (with speed advantages). There is no need for negation, >>of course, since one can choose the polarity of any signal >>arbitrarily. > >This is very cool. I suppose that advances in fabrication techniques mean >that we are not as obsessive about chip real estate as we used to >be. Using this protocol, it is not only the case that inverters take zero >area, but also AND and OR gates are essentially identical. > >>There are other important reasons to use dual rail logic -- one which >>the group might appreciate is to reduce the data-dependent noise in >>cryptographic processors. When the same number of bits go up as down, >>it is much more difficult to look at e.g. power supply current to >>determine what the processor is doing. More mundanely, dual rail >>logic is very good in reducing electromagnetic interference, and, with >>differential receivers, very resistant to noise. > >I wonder if it simplifies power supply design to have the total amount of >drawn current vary so little. > >-A

1 0

[math-fun] Re: Number of ones in the binary expansion of 3^n
by Allan C. Wechsler 05 Dec '02

05 Dec '02

At 10:36 PM 12/3/02 -0500, you wrote: >I saw your name listed by information about the number of ones in the >binary expansion of 3^n. Do you know any way of getting an analytic >formula or references to any material relating to a formula for this? > >Gershon Bialer I assume you are talking about my credit on Sloane's Encyclopedia of Integer Sequences, sequence A011754. I had written a program to display the powers of 3 as a bit-raster (a rather interesting display, it turns out) and it was cheap to count the ones. So I did, and it turned out that Sloane didn't have that one, so I got credit. If you actually look at the bit-map (this is probably a three-line program in Mathematica, or you can look at the picture in the given reference at EIS), you will see why I think there will be no easy formula for this sequence. I'd bet that the cheapest way to calculate the nth element of the sequence will always be to actually compute 3^n and just count. I have taken the liberty of cc-ing this answer to a list of recreational math enthusiasts, one of whom may have more insight. -A

3 3

[math-fun] Square (& other) chains and necklaces.
by Richard Guy 05 Dec '02

05 Dec '02

I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32. 28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18 This can be upped to 33 by inserting ... 9 16 33 31 18 7 29 20 5 11 ... so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??). This (and 32 33 ... for necklaces) seem to be in too much of an inchoate state for acceptance as sequences for OEIS ?? Finding Hamilton paths is NP-hard in general, but those of us who don't know about such things can often find them in particular cases. Any offers for contributions to knowledge, or references to existing knowledge that Ed Pegg hasn't told me about? R.

8 16

[math-fun] Laces high
by Helger Lipmaa 05 Dec '02

05 Dec '02

Today's Nature has an interesting article - a survey is available from http://www.nature.com/nsu/021202/021202-4.html Paper itself: -- Mathematics: What is the best way to lace your shoes? BURKARD POLSTER School of Mathematical Sciences, PO Box 28M, Monash University, Victoria 3800, Australia e-mail: burkard.polster(a)sci.monash.edu.au The two most popular ways to lace shoes have historically been to use 'criss-cross' or 'straight' lacing but are these the most efficient? Here we demonstrate mathematically that the shortest lacing is neither of these, but instead is a rarely used and unexpected type of lacing known as 'bowtie' lacing. However, the traditional favourite lacings are still the strongest. -- Helger

2 1

[math-fun] Laces high
by John McCarthy 05 Dec '02

05 Dec '02

It seems to me that the main objective of a shoe lacing scheme should be to produce a uniform force pulling the two sides of the uppers together. This doesn't come up in the article.

1 0

[math-fun] ANKOS after 180 days
by mcintosh＠servidor.unam.mx 05 Dec '02

05 Dec '02

>From Edwin Clark, 20 Nov 2002: > Speaking of reviews of ANKOS. Here's a review by Lawrence Gray that is > somewhat more substantial than Kranz's review: > > www.math.umn.edu/~gray/pdf/wolfram.pdf > ... Well worth reading; he was apparently present at the 1998 Santa Fe meeting. Having hinted at the legal wrangle, let us hope that he is correct in saying that Cook's paper may finally be released. The proceedings have kept being put off and off (latest estimate January 2003); dare one hope to see it there? Melanie Mitchell has an extremely perceptive review of ANKOS in Science, which had not yet arrived in Puebla at the time of my last posting (but by now E.C. has included it in his list). > And by the way, does anyone know if Mathew Cook's proof of the > universality of CA 110 (as presented in ANKOS) has been verified by > workers in the area? Some progress has been reported in this area; see my previous postings or the postings in the ``cellular automata'' usenet group. The necessary collisions are spectacular and were easy to verify, given that we had already done considerable work in this area. Global synchronization is harder to check because it takes place over such a wide area and long time span. Apparently there is nothing better to do than to sit in front of a screen and watch it, although segments can always be captured and printed. What at first seemed to be an error or a mislabelling turns out to be due to the sketchy nature of the information presented in the book. More aspects of the collisions have to be taken into account than are shown in the figures. Inviting people to run the Mathematica programs associated with the book does not lead to independent confirmation of the assertions in the text. Using a proprietary language which can only be run in a proprietary operating system does not necessarily imply falsification of the results (but look at what that boy Schoen just did at Bell Labs). We have just had some discussion here on math-fun of the acceptability of the Four Color Theorem, wherein be it noted that running an independently written program on a different model of computer was considered to be reassuring. What is for sure is that the pictures in the book were carefully selected and hopefully no mistakes were made in transcribing their code into the manuscript. Handsome indeed are the results. But lacking even an attempt to explain the programs, how would one go about trying experiments of one's own? Such as bombarding the data with a string of nulls, or trying to merely copy or complement an incoming data stream? Or writing that binary counter? Supposing that all the adjustments which are inherent in the collision parameters can successfully be made (and bear in mind that the scheme outlined in ANKOS practically forces the use of a cyclic system), the larger question arises as to whether there is a Turing Machine lurking in the background somewhere. We are offered Kolakoski's automatic substitution systems, and we can search the literature of small Turing Machines. There isn't much to work with here in Puebla except the Internet, but we haven't been able to find any paper giving an explicit connection. Maybe soomeone can offer some references? - hvm

1 0

[math-fun] totient blooper, segment arc, pestilent vectors
by R. William Gosper 04 Dec '02

04 Dec '02

I said k - 1 ==== \ k + 1 k - j > B ( ) n U (n) / j + 1 j + 1 j ==== ==== k + 1 \ k j = 1 phi(n ) > t = ----------------------------------- + -----------, / k + 1 k + 1 ==== t < n (t,n)=1 >where B are Bernoulli numbers, > j > a b c a-1 b-1 c-1 > phi(p q r ...) := p (1 - p) q (1 - q) r (1 - r) ..., >and > a b c k k k > U (p q r ...) := (1 - p ) (1 - q ) (1 - r ) ..., > k >where p, q, r, ... are distinct primes. In fact, a b c a-1 b-1 c-1 phi(p q r ...) := p (p - 1) q (q - 1) r (r - 1) ..., as in the earlier message (and which you all know). --------- I added "volume" and "surface" of segment of n-sphere to Macsyma's GeoFuncs package, e.g., (c355) block([radexpand:false],sphere_segment_curved_surface(n,r,t)) n - 1 ----- n - 1 3 n n 1 t 2 hyper_2f1(-----, - - -, - + -, ---) (2 %pi r t) 2 2 2 2 2 2 r (d355) ---------------------------------------------------- n - 1 (-----)! 2 (t is thickness. radexpand:false just prevents the exponent in the numerator from distributing.) You can also give two abscissae instead of the thickness, getting powerseries in x1 and x2 instead of t=r-x1 and r-x2. (Perhaps I should have left it an integral, but half the time, the series terminate in just n/2 terms.) Try the n=2 case: On a circle of radius r, the chord of a segment of thickness t subtends what angle? Expecting something like 2 cos((r-t)/r), or even 2 atan(sqrt(r^2-(r-t)^2)/(r-t)), I was surprised by (c356) (assume(r>0), hypersimp(subst(2,n,%))/r) sqrt(t) (d356) 4 asin(---------------) sqrt(2) sqrt(r) (c357) rootscontract(%) t (d357) 4 asin(sqrt(---)) 2 r This says that the chord from an endpoint of the original chord to the midpoint of the arc is twice the mean proportional of the thickness and half the radius. Can this be seen directly, as opposed to via two Pythagorisms? -------- Apropos RKG's pun typo, mathematicians can indeed be vectors. I infected a 7th grader with the following diseased factoid, probably caught from a confused highschool teacher, and never examined critically: :-( :-( :-( :-( :-( :-( :-( :-( :-( :-( :-( "The gravitational effect of an extended body on a point outside its convex hull is the same as if all its mass were concentrated at its center of gravity." )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: )-: The absurdity of this is evident from comparing the force at the origin due to aligned unit masses at distances 1 and 3, vs a two-unit mass at 2. Otherwise, masscons would not perturb lunar orbits, and the oblateness of the Sun would not contribute to the precession of Mercury. --rwg

2 1

Re: [math-fun] n-complements, squared
by Henry Baker 04 Dec '02

04 Dec '02

Knuth talks about this in the later editions. I seem to recall that this is Volume II. It's in one of the exercises. At 08:02 AM 12/4/02 -0800, Eugene Salamin wrote: >--- Don Reble <djr(a)nk.ca> wrote: >> I think the two-square-sum problem has been done to >> death. If you can factor X, it's easy to determine >whether it has such representations; does anyone know >>how to generate them? > >Maple has a function "sum2sqr" which lists all the >representations. You could examine the code. > >Gene

1 0

Re: [math-fun] Square (& other) chains and necklaces.
by Dan Hoey 03 Dec '02

03 Dec '02

Dan Asimov wrote: > Nice example! Now suppose every vertex is required to have finite > valence. Then I think this slight modification of Mike's example > will still serve as a graph where every {1,...,n} has a Hamiltonian > path, but not {1,2,3,...}. (This is a slight modification of Dan's graph.) 4--3--5--7--9---11--- | /| /| /| / | / ... |/ |/ |/ | / | / 1--2--6--8--10---12-- Now suppose we require Hamiltonian cycles for every {1,...,n}. Is there then a Hamiltonian path for N (there can't be a cycle). Suppose we require Hamiltonian cycles for every {a, ..., b} for a,b in Z? Can we then find a Hamiltonian path through Z? Dan (not that Dan, this Dan) Hoey(a)AIC.NRL.Navy.Mil

2 1

Re: [math-fun] infinite paths & cycles
by Dan Hoey 03 Dec '02

03 Dec '02

When I said, "The only kind of graph connectedness I know of is finite," I meant that a path with two endpoints has to have finite length. So the distance between any two points is finite if it exists. Dan

1 0