March 2003 - mathfun@mailman.xmission.com

[math-fun] Why is e the "best" base? + A symmetrical way to treat digits 0,1,2 base e
by asimovd＠aol.com 07 Mar '03

07 Mar '03

I forget who mentioned that e was found to be the "best" number base. I would like to know in what sense it is best -- or is this just some kind of offhand, non-rigorous comment? I chose to look at e simply because it seems to be the math constant (other than 2) whose powers (not necessary integer) arise most commonly. There is the old chestnut that (modulo details) if we start with a real number K >> 0 and wish to break K up into the sum of positive pieces with maximum product, this is attained by making each piece = e. (This is exactly true if K = ne, but needs some modification otherwise, of course.) Is this relevant here? ------------------------------------------------------------------------------ ---------------------------------------- ALSO: There's something unappealing about the asymmetry inherent in using the greedy algorithm to represent a number to (say) base e, since 0 and 1 play a role different from the other digit, 2. One way to avoid this would be as follows. Suppose we want to represent K > 0 to the base e, and suppose that e^r is the largest integer power of e that does not exceed K. Hence K = c (e^r) where 0 <= c < e. Then we use as highest-order digit d = 0, 1, 2 according as 0 <= c < e/3; e/3 <= c < 2e/3; 2e/3 <= c < e, or in brief, d = [3c/e]. (Of course, the calculation of digits continues by applying the above to the quantity K - d(e^r), now using e^(r-1) in place of e^r, ad infinitum.) I wonder if anything nifty comes from treating the digits in this symmetrical fashion. --Dan

5 6

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

07 Mar '03

>=Andy Latto > You get the quantity -ln(p) of information from a message that > occurs with probability p, but you only get that information > with probability p, so the expected amount of information > received is the sum of -p(ln(p)) over all possible messages > you might receive. Andy, thanks for the clarification of the provenance of this formula. So this sum measures the average information delivered by the channel, versus that of a single message. But the maximum of such a sum isn't necessarily the maximum of the summand. Applying the above by viewing a number as a stream of digits: for a given base b we sum over the b possible "messages", each of which (presumably) occurs with equal probability p=1/b, giving b (-1/b ln(1/b)) = -ln(1/b) = ln(b) which says the larger the base the higher the information, not that the maximum occurs when b=e. What's wrong with this picture?

2 1

[math-fun] New topic: a near vector space please
by Guy Haworth 07 Mar '03

07 Mar '03

Is there a simple example of a structure that satisfies every vector space property except: k1 * (k2 @ V) = (k1 * k2) @ V k1, k2 in the underlying field K; @ == Field/Vector operation TIA - Guy

2 1

Re: [math-fun] Why is e the "best" base?
by asimovd＠aol.com 07 Mar '03

07 Mar '03

I don't know much about information entropy E , but I do know that it's usually defined as a function of a *partition* of the unit interval into disjoint subintervals, aka the probaiblities p_i of a discrete probability measure. So E is a function of the collection (multiset) of values P = {p_1,p_2,p_3,...} and is defined via E(P) = sum over i of (-p_i log(p_i)) Among partitions of size n, the maximum-entropy partition P_M(n) is into equal intervals, giving E(P_M(n)) = log(n). --Dan

1 0

[math-fun] Question
by David Wilson 07 Mar '03

07 Mar '03

Let p be a finite sequence of positive integers, WLOG nondecreasing. Call p "good" (for lack of a better term), if for each p(i) there exists 0 < q(i) < p(i) such that for every integer n, n == q(i) (mod p(i)) for some i. For example, let p = (3, 3, 6, 6), and let q = (0, 1, 2, 5). Since every integer n is of the form 0 (mod 3), 1 (mod 3), 2 (mod 6) or 5 (mod 6), p is good. Clearly, for p to be good, it is necessary that SUM 1/p(i) >= 1, but this is not sufficient. Is there an efficient method to tell if a given p is good?

2 1

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

07 Mar '03

> -----Original Message----- > From: Marc LeBrun [mailto:mlb@fxpt.com] > Sent: Friday, March 07, 2003 12:24 PM > 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!"<;-) You get the quantity -ln(p) of information from a message that occurs with probability p, but you only get that information with probability p, so the expected amount of information received is the sum of -p(ln(p)) over all possible messages you might receive. Andy Latto andy.latto(a)pobox.com

1 0

[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