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

Re: [math-fun] Permanents
by Mike Stay 13 Jan '05

13 Jan '05

Rich wrote: > Multiply together all the complex > numbers in V, and divide by the product of the complex > numbers in Z. ... > But the operation of choosing random > elements on the unit circle suggests that it might be a > good algorithm for quantum computing. It'll be hard to compute the product of the phases on a quantum computer, since if you could do that (and have a decent probability of measuring the resulting phase in comparison to a known phase), you could solve NP-complete problems. Create an equal superposition of solutions in some subset of the problem domain and let all the phases be 1. Then negate the phase of the component that satisfies the circuit. By computing the product of the phases, you can know whether the solution exists or not in that subset of the domain. Binary search for the solution. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

1 0

[math-fun] Permanents
by Richard Schroeppel 13 Jan '05

13 Jan '05

The Permanent is a function of a square matrix, a polynomial in the matrix elements. It's like the determinant, with N! terms, except that all the signs are +. [ A B ] Perm [ C D ] = AD+BC, while Det = AD-BC. It seems to be much harder to compute the permanent than the determinant. Some elementary row operations, like rowA += rowB, which preserve determinants, do not preserve permanents. These are what make the determinant easier to calculate. Permanents aren't nearly as useful as determinants, but they crop up in complexity theory. In particular, computing permanents can answer questions like "How many solutions are there to make this boolean formula true?" I have an "Is this known?" question for the group: Here's a theoretical way to compute the permanent of an NxN matrix M: Choose a random vector Z of N elements. Each entry is an independent randomly chosen complex number on the unit circle, |Zk|=1. Compute V = ZM, giving another vector of complex numbers. (The typical entry is unlikely to be on the unit circle.) Multiply together all the complex numbers in V, and divide by the product of the complex numbers in Z. In rough symbols, compute product(elements of V) ---------------------- = result P, another complex number. product(elements of Z) Then the expected value of P is the permanent of M. (I'm assuming the entries of Z are chosen uniformly.) [Is this already known?] This isn't a very practical way to compute permanents -- it bears a lot of similarity to Buffon's Needle method of computing pi. But the operation of choosing random elements on the unit circle suggests that it might be a good algorithm for quantum computing. Rich rcs(a)cs.arizona.edu

1 0

[math-fun] Maple LLL?
by R. William Gosper 13 Jan '05

13 Jan '05

Doc shows lattice([[1,2,3],[-1,0,1],[0,1,1]]); [[-1, 0, 1], [0, 1, 1], [0, -1, 1]] but then lattice([[-1,0,1],[0,1,1],[1,2,3]]); [[-1, 0, 1], [0, 1, 1], [1, -1, 0]] Why not some permutation of the first result? For less trivial lattices, the consequences of permuting the vectors become large, so that some of the shortest vectors are missing from most of the answers. E.g., looking for close products of small primes, I found 2 3 3 11 41 67 71 79 36100763589 31 41 59 79 20621900011 ----------------- = ----------- and --------------- = -----------, 3 36100763591 2 3 20621900013 19 23 31 47 59 3 11 13 37 73 but nothing this good when I reversed the list of vectors. Is this a bug in Maple, or a property of LLL? --rwg

1 0

[math-fun] puzzle
by David Wilson 12 Jan '05

12 Jan '05

Score card wise, how many different possible games of ten pins are there?

1 0

[math-fun] What is 3.1464466?
by N. J. A. Sloane 11 Jan '05

11 Jan '05

The following message gives an alternative value for Pi, 3.1464466. Does any one know what this constant is? Google didn't recognize it. NJAS > From: "Jain ( Mathemagics )" <jain(a)jainmathemagics.com> > Subject: JAIN, of Australia, World Tour 2005. South East Queensland, Australia Tour in Feburary. > Date: Tue, 11 Jan 2005 18:48:17 +1100 > > Dear Friends, > > Due to the popularity of my American Tour last year in 2004, I have been > invited again to teach in many destinations. I am sending you this email > for several reasons: > > ... > Day 1 Feb 5, Sat VEDIC MATHEMATICS FOR THE NEW MILLENNIUM: > > How to complete complex mathematics... in your head! Without a > calculator. > Rapid Mental Calculation. Increases Confidence and Memory Skills. > ... > > Day 5 PI: (Date To Be Announced). (Optional) > > The Western value of Pi 3.1415926 is wrong and disharmonic! > Discover the True and Exact Value of Indian Pi ( A ) which is 3.1464466. > > Highly controversial issue that will rewrite all the books. > > Experience 'Jain Magic' "Sacred Geometry", > with a spectacular 2-hour INTRODUCTORY PRESENTATION > on all the above topics! > ...

4 3

Re: [math-fun] Learning computer programming for a bright 13-year old?
by Phil Carmody 10 Jan '05

10 Jan '05

While I'm replying I'll deviate back to the original question and suggest JavaScript. It's got pretty much all the theoretical purity of languages like LISP or even ML; it's a close syntactic relative of the more mainstream C/C++/Java, so a useful familiariser for those; and to top it off, it typically sits inside a framework (a browser) where all input/output/display issues already neatly handled. To the mathematician in me, JavaScript, when programmed well, is a very satisfying language. (But 99% of all real-world use of it would get this message negatively moderated ;-) ) From: "R. William Gosper" <rwg(a)osots.com> > I said > > For a certain concrete thinker, I'm > > planning the following first program: Combine Macsyma's string > > manipulation functions, especially CARDINAL_STRING (12 -> "twelve") and > > ORDINAL_STRING (12 -> "twelfth") to make a FRACTION_STRING function > > (11/12 -> "eleven twelfths"). There are nice opportunities for bugs > > ("one twelfths", 1/2 -> "one second", 3 -> "three firsts") > > This went great!! After he got those fixed and was sure it all worked, > 3/2 -> "three halfs" and after the obvious fix, "three halvess". > He *really* enjoyed that session. > > Richard Fateman added > >You might be surprised to learn that speaking fractions is > ambiguous. > > 30/400 and 34/100 are quite different numbers, but > each can be pronounced > > thirty four hundredths > > Luckily, we dodged that one. It probably can't happen with reduced > fractions anyway, twenty three hundred and oneths? > but just for kicks: > block([gcd:false,fancy_display:false], > for x in [34/100,30/400] do print(x=number_string(x)))$ > > 34 > --- = thirty-four one hundredths > 100 > > 30 > --- = thirty four hundredths > 400 One thing that used to drive both my (US) girlfriend and (UK) me absolutely mad was hearing sports commentators say things like "X has beaten Y by three one thousandths of a second". "Three thousandths!" we'd both shout at the idiot box simultaneously. I don't know how widespread such ire is though. I believe the additional (to me) "one" is certainly more US, but the commentator in question (Murray Walker) was as British as the day is long. The disambiguation can typically happen in the phrasing, but that's a lower-bandwidth part of the signal, alas, and more susceptible to noise. Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

11 13

[math-fun] patterns in steel, damascus steel, interesting patterns
by Simon Plouffe 10 Jan '05

10 Jan '05

Hello, I just contacted an old friend who lives in France and specialize in the fabrication of knives and 'eggs of Damascus', the interesting thing is that when they make those egss, patterns appears on the surface which are intriguing. http://damascus.free.fr/f_damas/quest.htm and see the eggs here : http://oeufs-damas.com/index.php http://oeufs-damas.com/oeufs/oeuf_08.jpg They are considered decorative and they sell it. (I am not trying to sell those things, just pointing to an interesting phenomena). Simon Plouffe

1 0

[math-fun] Query into pseudoprimes
by David Wilson 08 Jan '05

08 Jan '05

It is no longer surprising that there are even pseudoprimes 2n for which 2^(2n) == 2 (mod 2n) specifically, 2n = 161038 (see A006935). This got me to wondering if there were always multiples of This got me to wondering if for any m, there always exists k >= 2 satisfying [1] m^(km) == m (mod km) and if so, what would the least such k(m) be? Empirically, it looks as if k(m) exists for all m, and programmatically I got the following k(m) for 2 <= m <= 100. 80519,2,3,2,5,2,7,2,3,2,11,2,13,2,3,2,17,2,19,2,3,2,23,2,5,2,3,2,29,2,31, 2,3,2,5,2,37,2,3,2,41,2,43,2,3,2,47,2,7,2,3,2,53,2,5,2,3,2,59,2,61,2,3,2,5, 2,67,2,3,2,71,2,73,2,3,2,7,2,79,2,3,2,83,2,5,2,3,2,89,2,7,2,3,2,5,2,97,2,3 Superficially, this appears to be k(m) = 80519, if m = 2 lpf(m-1), if m > 2. where lpf(x) is the least prime factor of x (A020639). I assume we can prove that k = lpf(m-1) satisfies [1], any takers? But maybe things aren't so simple. According to my program, there are some m for which k(m) < lpf(m-1). In particular: k(152) = 143 < 151 = lpf(152-1) k(158) = 77 < 157 = lpf(158-1) k(338) = 161 < 337 = lpf(338-1) k(368) = 77 < 367 = lpf(368-1) k(380) = 299 < 379 = lpf(380-1) k(524) = 437 < 523 = lpf(524-1) k(542) = 143 < 541 = lpf(542-1) k(548) = 77 < 547 = lpf(548-1) k(608) = 407 < 607 = lpf(608-1) k(614) = 611 < 613 = lpf(614-1) k(662) = 581 < 661 = lpf(662-1) k(674) = 319 < 673 = lpf(674-1) k(692) = 377 < 691 = lpf(692-1) k(998) = 161 < 997 = lpf(998-1) ... These may actually be discrepancies, however, there is also the distinct possibility of computational error, so maybe someone could verify or refute these values?

2 1

[math-fun] Book recommendation
by Daniel Asimov 08 Jan '05

08 Jan '05

Recently I've been browsing with great delight a recent book called Mathematical Puzzles: A Conoisseur's Collection, by Peter Winkler. These puzzles have been chosen because they're typically much more interesting than, say, the puzzles in the Monthly. They're aimed at people with a math background, but not necessarily an advanced one. Some of the solutions are fairly complex, but almost none require math beyond calculus (and very few go even that far). Besides a sections on probability, geometry, games, combinatorics, etc., there's also a non-mathy fun section on geography puzzles, a section of especially tough puzzles, and finally, a section of easy-to-state unsolved problems. Most math-funners have seen some of these problems before, but I'd guess at least 2/3 of them were new to me, and well worth the price ($18 on Amazon (paperback)). --Dan

1 0

Re: [math-fun] Modular square root
by Mike Stay 06 Jan '05

06 Jan '05

Rabin's public key algorithm is based on the difficulty of computing square roots mod n=p*q, p,q prime. ----- Original Message Follows ----- > Except for semicolons, Michael Kleber writes: > > << > [T]here will be at most two [square roots of an integer > mod p]. > > Working mod p, you can still do a^2=b^2; a^2-b^2=0; > (a+b)(a-b)=0; a=b or a=-b, since there are no zero > divisors mod p. >> > > There's something different and interesting going on with > square roots in the integers mod n for n not prime, > and especially if n|24. > > --Dan > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

2 1