November 2002 - mathfun@mailman.xmission.com

[math-fun] odd prime query
by Kimberling, Clark 11 Nov '02

11 Nov '02

A friend would like to know if someone can prove or disprove the following assertion: Let d(n) be the characteristic function of the odd primes, p(1)=3, p(2)=5, etc. For j>=3, define S(k,j)=Product{1-d(2j-p(i)): i=1,2,...,k}} if 2j>p(k) and S(k,j)= 0 otherwise. Let A(k,n)=Sum{S(k,j): j=3,4,...,n}, for n>=3. Assertion: A(k,n) < n(1-2/log(2n))^k. Have fun! Clark Kimberling

1 0

[math-fun] Fibonacci prime test
by R. William Gosper 11 Nov '02

11 Nov '02

I sent (but didn't see on Math-fun) >Rich once showed me the "Lucas pseudoprime test", of which this may be >merely a special case. Let n>2 be not a multiple of 5, phi be the golden >ratio, and e:=(-1)^(n^2 mod 5). Then if phi^(n+e) mod n = -e, n is probably >prime. Inequality certifies n composite. This presumably follows from ancient >lore on the periodicity of the Fibonacci sequence mod n. >The Macsyma function is merely >modulus_warn:false$ >fibprm(n):=block([modulus:n,e:(-1)^nummod(n^2,5),algebraic:true], > is(-ratsimp(%phi^(n+e))=e)) >This is fast because RATSIMP exponentiates modulo both n and %phi^2-%phi-1. Slightly faster is the Maple fibprm:=proc(n) local e; e:=(-1)^(n^2 mod 5); evalb(-e = mods(Powmod(phi,n+e,phi^2-phi-1,phi),n)); end: >The first few pseudoprimes spoofing this test are >4181 = fib(19) = 37 * 113, >5777 = 53 * 109, >6721 = 11 * 13 * 47, >10877 = 73 * 149, > . . ., >197209 = 199 * 991, > . . ., >1203401 = 401 * 3001, > . . ., >1803601 = 601 * 3001, > . . ., >1970299 = 199 * 9901 > . . ., >4475521 = 211 * 21211, >with typical differences gradually increasing, but ratios decreasing. [...]> Erdos (I think) conjectured that in the *very* long run, >the density of pseudoprimes will actually increase. There appear to be no >even pseudoprimes. This test even rejects 2! Next after 2^35-6284047 = 34353454321 = 5300641*6481 is the relatively close pair 2^35+28429389 = 34388167757 = 19333 * 1778729 and 2^35+30503233 = 34390241601 = 3 * 89 * 401 * 321203 . Does anyone see what scrutiny of intermediate results might make this test "strong"? --rwg

1 0

[math-fun] Putnam Exam
by Roland Silver 09 Nov '02

09 Nov '02

I took the Putnam at Harvard ca 1948, and didn't do particularly well. I have an interesting recollection of it, though. Andy Gleason was the coach, and after each session of five questions (morning and afternoon) he offered us the choice of going for lunch or staying to to discuss the questions. Needless to say we all stayed. Gleason gave solutions to ALL the problems, giving more than one solution to several of them. All his solutions were quite elegant. I remember one of the problems, and his astounding approach to the solution. It asked how many roots of a given quintic polynomial have positive real part. I could probably reconstruct the polynomial (or one that would do just as well). -- --rollo <rollos(a)starband.net>

1 0

Re: [math-fun] Prodigals
by asimovd＠aol.com 09 Nov '02

09 Nov '02

Turns out Google gives 693 hits for "product integral", and it appears that the concept was first invented by Volterra in 1887. --Dan

6 6

Re: [math-fun] Putnam Exams
by asimovd＠aol.com 09 Nov '02

09 Nov '02

When I took the Putnam 1964-67, they would tell you your rank among all contestants, but I don't think they told you your test score. I wonder when they began doing that. --Dan

2 1

[math-fun] Putnam Exam
by Thane Plambeck 09 Nov '02

09 Nov '02

I've often thought that the focus on teams and not revealing the highest scoring individual in the Putnam examination is a public relations mistake for Mathematics (I think they only reveal the highest 5, and next 5, etc?). No newspaper is likely to pick up a story that reads "Harvard (or whoever) wins Putnam." By contrast the old Westinghouse Science winners got lots of press. Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

[math-fun] Putnam Exams
by David Wilson 09 Nov '02

09 Nov '02

I took the Putnams only once in my sophomore year, 1979. I was #2 scorer at Cornell, but to put that in perspective, the top scorer, Irwin Jungreis, got an 89 and I got a 23, I think out of 120. I don't think anybody else got better than 15. Of course, Irwin was a true genius and would eat, drink, and sleep Putnam for 3 months prior, whereas I was a comparative amateur and I never studied for it. Irwin was the one who convinced me to take the test that year. I never took it again after.

1 0

Re: [math-fun] Prodigals (of matrices)
by asimovd＠aol.com 09 Nov '02

09 Nov '02

Hi, Shel. I'm not clear on how A(t) and B(t) depend on t in what you wrote below. I have posted a response to math-fun that should appear any minute. --Dan ------------------------------------------------------------------------------ -------------------------------- << If A and B are thought of as matrix-valued functions of a parameter t where, e.g., A(1/n) ^ n = A(1), B(1/n) ^ n = B(1), which makes easy to see geometric sense for constant rate rotations, then the product integral P (A(t)B(t))^dt seems to be the continuously combined rotation (at least according to one way of defining it), and seems to be equal to P (B(t)A(t))^dt. >>

2 2

Re: [math-fun] Prodigals (of matrices)
by asimovd＠aol.com 08 Nov '02

08 Nov '02

Shel (sjk(a)kaphan.org) writes << ...Apropos your response to math-fun, what relationship does Log(A) have to the eigenvector of A, if any?... >> Sorry about the blank message again!!! (I'm having a touchpad hardware problem and single clicks often get interpreted as double -- which sent the blank msg. The hardware's supposed to be replaced on Monday) Anyhow, any rotation Q in SO(n,R) has assoc. with it a decomp. of R^n into orthogonal eigenspaces that are 2-planes P_i that are each carried into themselves by rotation by, say, theta_i for 0 <= theta_i <= pi, (and if n odd, an extra R^1 that is fixed). This decomp is unique if the |theta_i|'s are all unequal. Q has a pair of eigenvalues cos(theta_i) + - sin(theta_i) for each P_i, plus an extra 1 if n is odd. Choosing an orthonormal basis e_1,...,e_n which all lie in the eigenspaces (and the ith pair having the right orientation on its P_i), the Log can be expressed by the 2x2 block about the diagonal equal to 0 theta_i -theta_i 0 It's easy to check that exp of such a matrix gets you blocks like cose(theta_i) sin(theta_i) -sin(theta_i) cos(theta_i) along the diagonal, and so it performs as advertised. This much I understand, but what happens to the axes and angles when you add Log(A) and Log(B) (and then take exp) is a mystery to me. * * * BTW, I wasn't quite right in what I claimed: The expression Shel asked about, lim n -> oo (A^(1/n) B^(1/n))^n is equal to exp(Log(A) + Log(B)). The expression lim n-> oo (A^(1/2n) B^(1/2n))^n is what's equal to exp( (Log(A) + Log(B)) / 2 ). --Dan

1 0

Re: [math-fun] Prodigals (of matrices)
by asimovd＠aol.com 08 Nov '02

08 Nov '02

1 0