January 2009 - mathfun@mailman.xmission.com

Re: [math-fun] Encoding sorted lists with duplicates
by Steve Witham 22 Jan '09

22 Jan '09

Okay, encoding differences between successive elements (deltas) of a sorted list of r integers in { 0 .. n-1 }. This came from a programming puzzle I saw floating around the net: sort 1 million 32-bit ints in 2 million bytes of memory. 32 million bits is 4 million bytes, but for r = 1,000,000 and n = 2^32, a sorted list ought to be representable in ( r + n - 1 )! log ( -------------- ) ~= 13,511,284 bits = 1,688,910.5 bytes. 2 r! ( n - 1 )! The key is that the total of the deltas is less than 2^32. Once I started thinking about limiting how fast you use up bits vs. how fast you close in on that total--as a ratio to apply to the individual codewords--I was driven against my will to encode a delta d as floor( d / 2^12 ) one bits, a zero bit, and twelve binary bits. With this mixture of unary and binary, sizeof(d) <= 13 + d / 2^12 which makes it easy to see that for a million deltas totalling < 2^32, sum( sizeof(d) ) < 13,000,000 + 2^32 / 2^12 = 13,000,000 + 2^20 = 14,048,576 bits. Which is about 6/10 of a bit more per codeword than the the best possible. Just the fact that it uses a whole number of bits for each codword accounts for half a bit. I don't know whether this is an old trick, I haven't found another solution to the problem (as I understand it) on the web. --Steve

1 0

[math-fun] muffin(2,3,5)
by rcs＠xmission.com 22 Jan '09

22 Jan '09

Taking up an earlier suggestion about looking for corefinements of 1 into several sets of unit fractions ... Define Muffin(a,b,...) be the minimum piece size of a corefinement of 1 into pieces of size 1/a, and of 1/b, etc. Muffin(2,3,5) seems to be the smallest interesting case. I get M(2,3) = 1/6, M(2,5) = 1/10, and M(3,5) = 1/12. The M(3,5) split, normalized to 60ths, is 4*5 + 2*6 + 4*7. Thirds: 20 = 4*5 = [2]*(6+7+7). Fifths: 12 = [4]*(5+7) = 6+6. This also works for M(2,3,5): 30 = [2]*(5+5+6+7+7). So M(2,3,5) = 1/12. Rich

2 1

Re: [math-fun] Gödel book
by Dan Asimov 21 Jan '09

21 Jan '09

Gareth wrote: << On Wednesday 21 January 2009, Dan Asimov wrote: [me:] > Is an echolaliste someone who suffers from echolalia? > And if so, how does the other half of the pun work? (Does > "echo" mean the same in French as in english, or does it > e.g. mean "behold" following Latin "ecce" or something? ) [Dan:] > Yeah. And also, Eric wrote: Are you saying "yes" to some or all of my questions, or saying that you too would like to know the answers? >> I meant, Yeah, I have the same questions. << [Dan:] > Okay, thanks. Now is "guère épais" a group of some kind, like Oulipo ? A three-way pun there would be too much to expect, no? >> Didn't mean to suggest yet another pun. It's just that casual googling seemed to indicate a group of some kind called "guère épais". --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Gödel book
by Dan Asimov 21 Jan '09

21 Jan '09

Gareth wrote: << On Wednesday 21 January 2009, Eric Angelini wrote: > ... this is exactly Math-Fun, I guess: > http://www.echolaliste.com/l1213.htm Is an echolaliste someone who suffers from echolalia? And if so, how does the other half of the pun work? (Does "echo" mean the same in French as in english, or does it e.g. mean "behold" following Latin "ecce" or something? >> Yeah. And also, Eric wrote: << > "guère épais". ... "not that thick" --> wordplay on "Guerre et paix" (by Tolstoi) = "War and Peace" >> Okay, thanks. Now is "guère épais" a group of some kind, like Oulipo ? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] Estimating Inauguration crowds
by Steve Witham 21 Jan '09

21 Jan '09

http://specials.washingtonpost.com/inauguration/satellite/ This is a view of the Washington Mall. We have tools for these things. (Although the javascript is a bit flakey.) --Steve

1 0

[math-fun] Gödel book
by Eric Angelini 21 Jan '09

21 Jan '09

... this is exactly Math-Fun, I guess: http://www.echolaliste.com/l1213.htm Regards, É. --- « Werner Heisenberg might have slept here ».

3 2

Re: [math-fun] Gödel book
by Eric Angelini 21 Jan '09

21 Jan '09

Hello Dan, > "guère épais". ... "not that thick" --> wordplay on "Guerre et paix" (by Tolstoi) = "War and Peace" Best, É. -----Message d'origine----- De : math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] De la part de Dan Asimov Envoyé : mercredi 21 janvier 2009 19:11 À : math-fun Objet : Re: [math-fun] Gödel book The book titles I understood that didn't depend on knowledge of people I never heard of were pretty funny. Eric, s'il vous plaît, expliquez ce que veut dire "guère épais". Merci bien. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] Gödel book
by Dan Asimov 21 Jan '09

21 Jan '09

The book titles I understood that didn't depend on knowledge of people I never heard of were pretty funny. Eric, s'il vous plaît, expliquez ce que veut dire "guère épais". Merci bien. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Gödel book
by Eric Angelini 21 Jan '09

21 Jan '09

Eugene Salamin: > But not with Pauli. ;-))))))))))

1 0

[math-fun] Putnam mis-reading
by Dave Blackston 20 Jan '09

20 Jan '09

Hi all, I'm probably not alone on this list in that I like to try my hand at the Putnam problems each year. This past December, problem A2 was the following... Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008x2008 array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is non-zero; Barbara wins if it is zero. Which player has a winning strategy? This is not an overly challenging problem. Unfortunately for me, I misread the problem and tried to solve the game where Alan is trying to force the zero determinant. This seems a lot more challenging -- I have yet to solve it, though I am pretty convinced I know which player actually has the strategy. Do any math-funners want to give this a try? Dave

2 3