October 2009 - mathfun@mailman.xmission.com

[math-fun] Diffie-Hellman vs. exponentiation
by Mike Stay 08 Oct '09

08 Oct '09

The Diffie-Hellman operation a # b = exp(ln(a) ln(b)). This is clearly commutative, unlike exponentiation, but it still distributes over multiplication. This can be extended to an infinite series of operations in both directions: . . . a $ b = ln(exp(a) @ exp(b)) a @ b = ln(exp(a) + exp(b)) = exp(ln(a) $ ln(b)) a + b = ln(exp(a) * exp(b)) = exp(ln(a) @ ln(b)) a * b = ln(exp(a) # exp(b)) = exp(ln(a) + ln(b)) a # b = exp(ln(a) * ln(b)) . . . The operation @ is roughly max (Maslov dequantization can deform it into max). Each operation distributes over the operation above it. What is this sequence called? -- Mike Stay - metaweta(a)gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com

2 2

Re: [math-fun] Diffie-Hellman vs. exponentiation
by N. J. A. Sloane 08 Oct '09

08 Oct '09

> The Diffie-Hellman operation a # b = exp(ln(a) ln(b)). This reminds me of Marc LeBrun's map (a,b) -> a_b, where if a = Sum c_i 10^i (0 <= c_i <= 9) is the decimal expansion of a, then a_b = Sum c_i b^i, which we studied in arXiv:math.NT/0611293. It satisfies 10^( [ln a] ln b ) <= a_b <= 10^( ln a ln b ) and has a number of other nice properties! Neil

1 0

[math-fun] Little math competition problem
by Dan Asimov 08 Oct '09

08 Oct '09

I recently heard this not-too-hard but fun problem: << Find all rational solutions of x^2 + y^2 + z^2 + 3(x + y + z) + 5 = 0. >> --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] Diffie-Hellman vs. exponentiation
by Dan Asimov 08 Oct '09

08 Oct '09

What a nice sequence of operations! It would be great if a natural continuous interpolation of operations could be found. --Dan Mike Stay wrote: << The Diffie-Hellman operation a # b = exp(ln(a) ln(b)). This is clearly commutative, unlike exponentiation, but it still distributes over multiplication. This can be extended to an infinite series of operations in both directions: . . . a $ b = ln(exp(a) @ exp(b)) a @ b = ln(exp(a) + exp(b)) = exp(ln(a) $ ln(b)) a + b = ln(exp(a) * exp(b)) = exp(ln(a) @ ln(b)) a * b = ln(exp(a) # exp(b)) = exp(ln(a) + ln(b)) a # b = exp(ln(a) * ln(b)) . . . The operation @ is roughly max (Maslov dequantization can deform it into max). Each operation distributes over the operation above it. What is this sequence called? >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Israel Gelfond has died
by Bernie Cosell 08 Oct '09

08 Oct '09

<http://www.nytimes.com/2009/10/08/science/08gelfand.html> Israel M. Gelfand, one of the giants of 20th-century mathematics, whose work cleared paths for other thinkers in fields as diverse as physics and medical imaging, died on Monday in New Brunswick, N.J. He was 96. /B\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

1 0

Re: [math-fun] clumpy heapsort tree
by Steve Witham 08 Oct '09

08 Oct '09

It turns out the clumpy layout is a particular example of what's called the "Van Emde Boas layout." Here's a Google Books reference, including a nice illustration: http://tinyurl.com/emdeboas "Split the tree in the middle, at height h/2. This breaks the tree into a top recursive subtree of height floor(h/2) and several bottom subtrees of height ceil(h/2). There are sqrt(N) bottom subtrees, each of size sqrt(N)." Algorithms using recursively-divided layouts (or access patterns) to take advantage of caches, without knowing the characteristics of the caches in advance, are called "cache-oblivious," and there seems to have been work about cache-oblivious heapsorts. --Steve

1 0

[math-fun] A trillion triangles and congruent numbers
by Bernie Cosell 07 Oct '09

07 Oct '09

<http://www.eurekalert.org/pub_releases/2009-09/aiom-att091809.php> Mathematicians from North America, Europe, Australia, and South America have resolved the first one trillion cases of an ancient mathematics problem. ... The problem, which was first posed more than a thousand years ago, concerns the areas of right-angled triangles. The surprisingly difficult problem is to determine which whole numbers can be the area of a right- angled triangle whose sides are whole numbers or fractions. ... /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

8 10

Re: [math-fun] clumpy heapsort tree
by Steve Witham 07 Oct '09

07 Oct '09

>From: rcs(a)xmission.com > >The tree is recursive, building the lower sections >as copies of the upper part. 345 follows the pattern >of 012, just adding 3 to each node. 15-29 is a +15 >copy of 0-14. The next levels will be 255-509. Yup. >If we added 1 to each entry, the bit patterns might >be enlightening. Maybe, the math involves multiples of 3, 15, 255, etc. >What's the point? >Is this a worst case for heapsort? No, I'm wondering whether a different arrangement, where locations on a path down the tree tend to be closer together, (better "locality of reference") would let heapsort take better advantage of caching and virtual memory. Here is a graph of some timing tests so far. "Vanilla" is the classic heap, "Clumpy" is the one I've been talking about here, and there are other arrangements I've been trying. http://www.tiac.net/~sw/2009/10/Clumpy_heapsort >From: "N. J. A. Sloane" <njas(a)research.att.com> > >what was the rule that made you write > > 18 > 19 20 > >under 16, rather than as the right-hand daughter of 4 ? > >Could you spell out the rules more explicitly? The rule is that you build clump of 3: one parent node with two daughter nodes clump of 15: one upper clump of 3, + 4 lower clumps of 3 clump of 255: one upper clump of 15, 16 lower clumps of 15 65535 = (1 + 256) * 255 etc. So 18 goes under 16 because my rule says to build clumps of 15 (rather than just clumps of 3) starting at 15. The right-hand daughter of 4 is the next clump of 15. Here is one way to describe the sequence of numbers in a row of the clumpy tree. Say that S( i, r, h ) is row r (starting at 0) of a clump of height >= h, whose root is i. S( i, r, h ) = if r = 0: the sequence [ i ] if r >= h: S( i, r, 2h ) # see below else if r < h/2: S( i, r, h/2 ) else the concatenation of the sequences, for j = 1 to 2^(h/2) of S( i + j * ( 2^(h/2) - 1 ), r - h/2, h/2 ) The second case covers all the rows of an infinite tree, by doubling the height until it's enough. So, the whole sequence is the concatenation of the rows: S( 0, 0, 1 ), S( 0, 1, 1 ), S( 0, 2, 1 ), S( 0, 3, 1 )... --Steve

1 0

[math-fun] How round is your circle?
by Jason 06 Oct '09

06 Oct '09

I hadn't heard of Chebyshev's paradoxical mechanism before: http://www.howround.com/

1 0

Re: [math-fun] Which letters are used as variables in which languages?
by Marc LeBrun 06 Oct '09

06 Oct '09

>=Dan Asimov >>=Andy >> After all, English mathematics routinely uses i as a variable in subscripts, >> and as the square root of -1, and that never seems to be a problem. > I don't have any info about your other comments, but I can confirm that in English mathematics where the > (or a) square root of -1 plays an important role, the subscript i (for an integer) is usually avoided. Moreover, there's some element of the engineering world that eschews i in favor of j.

3 2