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

[math-fun] non-adjacent partitioning
by Meeussen Wouter (bkarnd) 07 Mar '03

07 Mar '03

a set of integers {1...n}, to be partitioned such that neighbours are in different subsets: {{1,3,5},{2,4}} {{1},{2,4},{3,5}} {{1,3},{2,4},{5}} {{1,3},{2,5},{4}} {{1,4},{2},{3,5}} {{1,4},{2,5},{3}} {{1,5},{2,4},{3}} {{1,3,5},{2},{4}} {{1},{2},{3,5},{4}} {{1},{2,4},{3},{5}} {{1},{2,5},{3},{4}} {{1,3},{2},{4},{5}} {{1,4},{2},{3},{5}} {{1,5},{2},{3},{4}} {{1},{2},{3},{4},{5}} this turns out to be Bell numbers, and by lengths they subttotal to StirlingS2: 1,7,6,1 but wasn't that "the number of ways of partitioning a set of n elements into m non-empty subsets" ? like 4 elements into 1..4 non-empty subsets? {{1,2,3,4}} {{1},{2,3,4}} {{1,2},{3,4}} {{1,3},{2,4}} {{1,4},{2,3}} {{1,2,3},{4}} {{1,2,4},{3}} {{1,3,4},{2}} {{1},{2},{3,4}} {{1},{2,3},{4}} {{1},{2,4},{3}} {{1,2},{3},{4}} {{1,3},{2},{4}} {{1,4},{2},{3}} {{1},{2},{3},{4}} Aaach, Math is *really* Fun ! Wouter =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

1 0

RE: [math-fun] Why is e the "best" base? + A symmetrical way to treat digits 0,1,2 base e
by Meeussen Wouter (bkarnd) 07 Mar '03

07 Mar '03

> p = 0 and p = 1, with a maximum somewhere inbetween, say at p = 1/e. Blasphemy ! -p*log(p) - (1-p)*log(1-p) goes maximal at at p=1/2, the point of 'least information', or equal probability for p=(1-p)=1/2. Wouter. -----Original Message----- From: Marc LeBrun [mailto:mlb@fxpt.com] Sent: vrijdag 7 maart 2003 18:24 To: math-fun(a)mailman.xmission.com Subject: Re: [math-fun] Why is e the "best" base? + A symmetrical way to treat digits 0,1,2 base e >=mcintosh(a)servidor.unam.mx > Entropy is p ln(p) summed over alternatives. It vanishes for > p = 0 and p = 1, with a maximum somewhere inbetween, say at p = 1/e. An interesting thing about this formula is that the maximum is independent of the base used for the logarithm. However, are you sure about that p factor? I thought the information content of a message was, roughly, how "surprising" it was, hence simply -ln(p) (which is why information gets called "negative entropy"). Getting an impossible message would be a miraculous epiphany, containing infinite information (alas of the form "everything you know is wrong!"<;-) I'll try to dig out my copy of Shannon's original paper and see what he said. By the way, is there an analogous "quantum entropy", which would involve taking the log of the "complex probability"? _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

1 0

[math-fun] mailing list upgrade for Math-Fun
by Richard Schroeppel 06 Mar '03

06 Mar '03

(to Math-Fun folks) The Xmission people are doing some kind of upgrade to the mailing list software this weekend. Send me a note if you see anything weird. It might be a good idea to save your settings if you've changed anything. I'll try to record the archives & membership list. Rich rcs(a)cs.arizona.edu

1 0

Re: [math-fun] Alternate bases
by Tom Knight 06 Mar '03

06 Mar '03

I don't think anyone has mentioned that the multiplier you are using in your machine is almost certainly using an expanded digit set, multiplying by the digits {-2, -1, 0, 1, 2} rather than {0,1,2,3} in bit pairwise fashion. Pairwise multiplication reduces the number of partial products, and eliminating the x3 multiplication makes it easy to compute the partial products. Conversion of radix 4 {0, 1, 2, 3} to radix 4 {-2, -1, 0, 1, 2} can be done with no carries, and is desirable from a hardware standpoint. These are called Booth multipliers. The inverse process can and often is used to derive an expanded digit version of a quotient.

1 0

[math-fun] RE: math-fun digest, Vol 1 #121 - 6 msgs ... Coughing up a Googol
by Guy Haworth 06 Mar '03

06 Mar '03

The accusation is that the Major was assisted. That is for the court to prove or reject. The transcript of the exchanges with coughs is at: http://news.bbc.co.uk/1/hi/uk/2823407.stm Assuming the coughs are meaningful, readers are challenged to speculate by working out the simplest syntax of communication ... and to relate this if possible to economical methods of communication used by the military. ... After all, if you guys can get N prisoners out of jail with the aid of two light switches and a protocol ... I should say that I have absolutely no connection with the defendants or the TV Program and have never met any of the protagonists. - guy

1 0

Re: [math-fun] Alternate bases
by Jeffrey Shallit 06 Mar '03

06 Mar '03

I already pointed this out privately, but since it continues to be discussed I'll repeat and expand on my answer. Yes, expansions in alternate bases have been discussed in the literature, and in fact, enormously so. If you search the on-line Math Reviews (mathscinet) for "beta-expansion" you will get something on the order of 60 references. The connection with Pisot numbers has, in particular, been studied extensively by Bertrand-Mathis, Frougny, Boyd, Solomyak, and others. (You should also search for the term "theta-development", which has sometimes been used by French people who don't know any better.) On the other hand, expansions in base-k with alternate digits have also been intensively studied, and there are indeed some results on what sets of digits are necessary and sufficient to produce expansions for all numbers. For example, see the paper of Matula, Basic digit sets for radix representation, J. ACM 29 (1982), 1131-1143. There is also a paper by Odlyzko. Prof. Thurston has already mentioned the theory of "automatic groups", but I'd also like to advertise the area I work in: the area of "automatic sequences". In fact, Allouche and I have finished a 570-page book on the subject, which will be published soon by Cambridge University Press. This book has a chapter on representations in base k and other sorts of representations, including a presentation of Matula's result. Jeffrey Shallit

1 0

[math-fun] Coughing up a googol for a million
by Thane Plambeck 05 Mar '03

05 Mar '03

>From a news article at the UK Daily Telegraph, with title "19 coughs helped major to TV Millionaire cheque, Jury Told" * * * * * * * An army major cheated his way to the top prize on Who Wants To Be A Millionaire? with the help of a fellow contestant who coughed to signal the right answers, a court heard yesterday.... ...Jurors were asked to listen for 19 distinct coughs which the Crown claims were designed to help Ingram. The most dramatic was during the Â£500,000 question when the major appeared to be ready to say that Berlin was the city that Baron Hausmann was famed for designing. The cougher is clearly audible on the tape, masking the word "No" behind a splutter. Ingram changed his mind and opted for Paris, the correct answer. On the final question, about the name of a number that is made up of one followed by a hundred zeros, the major answered "googol" after admitting that he did not know what a googol was. * * * * * ** Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

[math-fun] Re: HTML in math-fun, seqfan posts
by David Wilson 05 Mar '03

05 Mar '03

I understand the tribulations of picking through MIME and HTML in a nonsupportive mail reader. But., my current version of MS Outlook includes HTML and MIME in outgoing messages by default, these features are preferable for most of my mail; I have to explicitly switch to plaintext mode for math-fun and seqfan postings, and sometimes I forget. I can't select HTML or plaintext per recipient, consequently slips will happen, and I can't be eternally apologetic. If people can't overlook the occasional slip on this account, I can easily go away. At some point, I think math-fun and seqfan will have to acknowledge that technology is moving on. Despite my personal distaste for Microsoft and its applications, the reality is that MS Outlook is now the most commonly-used email application, that it supports HTML and MIME, and that users rely heavily on the associated benefits, such as formatted and colored text, images, backgrounds, links, attachments, etc. I appreciate that math-fun and seqfan like to be accomodating, however, accomodating HTML-disabled users will increasingly disaffect a growing majority of HTML-enabled users, and will deprive math-fun and seqfan of some very useful technologies (when MathML browsers become common, will you not take advantage?). I understand wanting to accomodate HTML-disabled users, and the desire to save on server space; and undercurrents of nostalgia, UNIXphilia, and MSphobia all warm my heart. It may also be that math-fun and seqfan want to discourage a floodgate of membership, considering some recent incidents of inconsiderate new users disrupting our coffeehouse atmosphere. Notwithstanding, my considered opinion is that catering to the technologically lowest common denominator will become increasingly costly to math-fun and seqfan as technology advances.

8 11

RE: [math-fun] Irrational-base representation
by Loren Larson 04 Mar '03

04 Mar '03

In Volume 2 of Knuth's Art of Computer Programming, page 193, he mentions some research concerning questions about irrational radices and gives a reference to W. Parry, Acta Mathematica, Acad. Sci. Hung., 11, (1960), 401-416. LL I recently began wondering if anything special happens when one uses the scheme of decimal, binary, etc. representation -- as usual, via a sequence of integer coefficients no greater than the base -- but with an irrational base like e. Of course, the representation has much more leeway for nonuniqueness than for an integer base, unless an algorithm is specified making it unique. So, we use the obvious "greedy" algorithm to get a well-defined representation. With base e, heuristically, a generic number's representation would in the long run have fraction 1/e of its digits = 0, 1/e of its digits = 1, and (e-2)/e of them = 2. I've taken a look at a few numbers base e but haven't found any statistical or other abnormalities. For example, I don't know what distinguishes an integer = 2 from a noninteger, a rational from an irrational, a 1/prime from 1/nonprime, etc. Without evident pattern, it's still amusing to see pi expressed "base e". It starts: pi = 10.101002020002111120020101120001010200010012101202012100211200... Does anyone know of research on representing numbers via real irrational bases? --Dan

1 0

Re: [math-fun] Irrational-base representation (e optimal)
by Marc LeBrun 04 Mar '03

04 Mar '03

>=Kerry Mitchell > There was some research done and reported last year of so about e being the optimal base. This is an old chestnut. I wouldn't be surprised if it dates back at least to Claude Shannon. So, since 3 is closer to e than 2 is, I guess ternary is "better" than binary? I think Knuth talks about this too...

2 1