November 2011 - mathfun@mailman.xmission.com

[math-fun] A puzzle from Emissary
by Victor Miller 29 Nov '11

29 Nov '11

In the lastest issue of Emissary (the newsletter from MSRI) there's the following challenging puzzle: For every positive integer n, write it in binary, and allow the following possible set of transformations: You can insert "+" signs at arbitrary points within the binary expansion, and interpret that as a sum of binary numbers. For example 110101_2 --> 11_2+01_2+01_2 = 3 + 1 + 1 = 5 = 101_2. Show that there is an absolute constant C such that for any positive integer n there is a sequence of at most C such transformations that results in 1. Note: The minimal value of C is a real shocker This made me wonder about the obvious generalization to other bases, where now we ask for a sequence of such transformation that results in a single digit base b number. Victor

2 1

Re: [math-fun] parabola puzzle
by Gary Antonick 28 Nov '11

28 Nov '11

yes - the n lines intersect with the 2 main lines at equal intervals. and I made a mistake. The structure should then be stretched until the angle between the 0th line (not 1st line) and the n/2+1th line is the same as the angle at which the ball was tossed. -------- Original message -------- Subject: Re: [math-fun] parabola puzzle From: Fred lunnon <fred.lunnon(a)gmail.com> To: math-fun <math-fun(a)mailman.xmission.com> CC: It's looking a lot better now, anyway. Presumably the "n lines" are spaced at equal intervals along the "base" lines? WFL On 11/28/11, Gary Antonick <gantonick(a)post.harvard.edu> wrote: > Hi Fred, > > Thank you for checking this out. The problem I'm having is being precise > with rotating and scaling main parabola. I'm looking for an underlying > structure that indicates all bounce patterns at once. > > Here's a concrete example I just ran. The bounce pattern and necessary > reflector angle for 20 bounces. All steps can be done quickly and with a > lot of precision except for > > - creating the 45 degree angle between the 1st and n/2+1 (in this case > the 11th) added tangent line and > - rotating the structure until the n/2+1 tangent line is vertical. > > http://www.flickr.com/photos/70917169@N02/6417153069/in/photostream > > - Gary > > > > On Sun, Nov 27, 2011 at 10:38 PM, Fred lunnon <fred.lunnon(a)gmail.com> wrote: > >> I followed your pictures well enough to understand the problem now, >> but still can't grasp what the (solution? or) property that you have in >> mind >> might be. >> >> WFL >> >> >> >> On 11/28/11, Gary Antonick <gantonick(a)post.harvard.edu> wrote: >> > Phooey. I don't think my description was very enticing. >> > >> > Here's a more specific question. In the linked image below, what is the >> > relationship between lengths a, b, c and d? >> > >> > http://www.flickr.com/photos/70917169@N02/6416169329/in/photostream >> > >> > I've googled around a bit.. haven't found anything on using a parabola >> > on >> > its side to trace out the pattern of multiple bounces. Any suggestions >> > would be very much appreciated. >> > >> > Best, >> > >> > Gary >> > >> > >> > >> > On Sun, Nov 27, 2011 at 3:06 PM, Gary Antonick >> > <gantonick(a)post.harvard.edu>wrote: >> > >> >> Hi all, >> >> >> >> I happened to notice something interesting about parabolas several >> months >> >> ago. Am wondering if it would make a good puzzle. >> >> >> >> It's about a ball bouncing up an incline. >> >> >> >> Say you point a cannon at 45° and fire. A cannonball flies out and hits >> a >> >> perfect reflector at the same height as the mouth of the cannon. If the >> >> cannonball bounces once on the reflector and then returns along its >> >> original path to the mouth of the cannon you'd know the reflector was >> >> at >> >> 45 >> >> °. >> >> >> >> But what if the ball bounces 5 times? What's the angle of the >> >> reflector? >> >> And >> >> - a related question - what trajectory does the bouncing ball take? >> >> >> >> All frictionless, of course, and w/o air resistance. And no calculus >> >> (or >> >> formulas of any kind) required. >> >> >> >> - Gary >> >> >> > _______________________________________________ >> > math-fun mailing list >> > math-fun(a)mailman.xmission.com >> > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] http://en.wikipedia.org/wiki/Golden_ratio
by Bill Gosper 28 Nov '11

28 Nov '11

Can anyone motivate their rather grotesque choice of an infinite series (13/8 + a 1F0[1/4])? Hey, why not some zip?: Binomial[2 n, n] 1970299 Sum[----------------, {n, 0, Infinity}] n 1 62113250390420 - + ----------------------------------------------- 2 1762289 (The +1/2 can be replaced by a factor of a n + b in the summand, for some integers a and b.) Actually, you're unlikely to beat (from Finch's opus) the superfast (doubly exponential) 4 - Sum[1/Fibonacci[2^n], {n, 0,∞}]. In typical fashion, Mma knows this one, just to be impressive, but not that it telescopes, just to be useful. --rwg

2 1

[math-fun] parabola puzzle
by Gary Antonick 28 Nov '11

28 Nov '11

Hi all, I happened to notice something interesting about parabolas several months ago. Am wondering if it would make a good puzzle. It's about a ball bouncing up an incline. Say you point a cannon at 45° and fire. A cannonball flies out and hits a perfect reflector at the same height as the mouth of the cannon. If the cannonball bounces once on the reflector and then returns along its original path to the mouth of the cannon you'd know the reflector was at 45 °. But what if the ball bounces 5 times? What's the angle of the reflector? And - a related question - what trajectory does the bouncing ball take? All frictionless, of course, and w/o air resistance. And no calculus (or formulas of any kind) required. - Gary

2 4

[math-fun] new matrix factorization, resembling Cholesky, but more useful for integer matrices
by Warren Smith 25 Nov '11

25 Nov '11

New matrix factorization resembling Cholesky but more useful for integer matrices ==================Warren D. Smith=====Nov 2011=================== If S is a positive definite real symmetric matrix it can be "Cholesky factored" into S = L * L^T where L is lower triangular and the T denotes transpose. If S is positive definite complex Hermitian, there is an analogous factorization S = L * L^H where L is lower triangular and the H denotes Hermitian conjugate, i.e. complex-conjugate transpose. I want now to bring your attention to the idea of allowing the entries of S to be QUATERNIONS. Then S = L * L^H where L is lower triangular and the H denotes Hermitian conjugate, i.e. quaternionic-conjugate transpose. In all three cases, the entries of L can be computed row-by-row via left-to-right raster scan by Lab = (Sab - sum(0<k<b)of Lak Lbk') / Lbb when a>b and |Lbb| = sqrt( Sbb - sum(0<k<b)of Lbk Lbk' ) where the ' denotes conjugate, empty sums are 0, and in the square root, we always take the square root of a positive pure-real number. HOWEVER if we allow L's entries to be complex or quaternion, we can use for Lbb ANY complex or quaternion whose length |Lbb| is given by that square root. We do not need to make the diagonal entries of L always be pure-real and positive, although we could. Why are quaternions interesting? Because of Lagrange's "four-squares theorem." This tells us there is always an INTEGER quaternion Q with |Q|^2 = Q Q' = Q' Q equal to any desired nonnegative integer. Hence, there is always a matrix factorization of any INTEGER QUATERNIONIC-HERMITIAN matrix S, into L L^H where L is lower triangular with RATIONAL quaternion entries. This is superior to the complex and real versions of Cholesky, which by taking square roots generally goes outside the field of the rationals making exact arithmetic practically impossible. ==========An application=========== There are probably many applications of this observation. Let me focus on one: point-sets with distances that are square roots of integers. If Dab is the integer distance between points a and b in n-dimensional space then we might want to actually find coordinate vectors for points realizing those distances. One way to do that is this. Place one point at (0,0,0,...,0). Make the other n points be the n rows of lower triangular matrix L (which if it has quaternion entries, means the points will lie in 4n-dimensional space, but since there are only n+1 points they will really lie in an n-dimensional subspace of it). Then S = L L^H is an nXn hermitian matrix, and Saa = D0a^2 are the diagonal entries and the off-diagonal entries are Sab = (D0a^2 + D0b^2 - Dab^2)/2. Thus S is an nXn matrix whose entries are known half-integers. By quaternion-Cholesky factoring it, we get L giving coordinates in 4n-dimensional space which will instantiate any distances that are sqrt(integer)s that can be achieved in a Euclidean space... AND will do so with every coordinate rational. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] line segment passing through a hyperbola-shaped slit
by James Propp 25 Nov '11

25 Nov '11

Is there a video on the web of a line segment passing through a hyperbola-shaped slit, as in the Eames Mathematica exhibit (and probably other math museum exhibits as well)? I want to show this to my calculus students tomorrow, and was astonished that I couldn't find it on the web even after several minutes of searching ("... Eames ruled surface hyperbola ...". Thanks, Jim Propp

4 7

[math-fun] Which Gamma(a/b) are superfast?
by Warren Smith 25 Nov '11

25 Nov '11

Call any real that can be evaluated to 2^N decimal places using only N^O(1) arithmetic operations starting from 0 and 1 only, "superfast." Algebraic numbers, pi, e, and formulas you can write with them using exp, log, trig, elliptic and modular functions and their inverse functions, all are superfast. The Gamma function at certain rational arguments, Gamma(a/b), is superfast. For example Gamma(1/2) = sqrt(pi). According to Eric Weisstein, J.Borwein & D.Bailey on p.137 of Mathematics by Experiment: Plausible Reasoning in the 21st Century, A K Peters, 2003. show that Gamma(a/24) is superfast for every integer a. I want a better understanding of which rationals and what is going on. Could it be that Gamma(a/b) is superfast for every rational a/b??? I shall end up doubting that. I suspect there are only a FINITE set of such favorable a/b with 0<a<=b. And what is that finite set? ======== integer arguments: Gamma(x) = (x-1)! add-1 formula: Gamma(x+1) = Gamma(x) * x so we need only be interested in Gamma(x) for 0<x<1. reflection formula: Gamma(x) * Gamma(1-x) = pi / sin(pi*x) so we need only be interested in x with 0<x<1/2. k-tuplication & duplication formulae: allow expressing Gamma(k*a/b) in terms of the Gamma(j/b) for integers j with 0<j<=a. Gauss full-period product formula: product(a=1..b)of Gamma(a/b) = b^(-1/2) * (2*pi)^((b-1)/2) proper-fraction subproduct due to Sandor & Toth: product(a=1..b with gcd(a,b)=1)of Gamma(a/b) = (2*pi)^(EulerTotient(b)/2) The product of Gamma(a/b) with a belonging to certain multiplicative subgroups of the integers mod b, can sometimes be expressed in terms of powers of sqrt(pi) and 2, algebraic numbers, and "elliptic singular values" and/or "Dedekind eta function" values. If AGM(1, sqrt(1-k*k)) = sqrt(n) * AGM(1, k) where AGM is the arithogeometric mean and where n is an integer, then k is the "nth singular value" and is superfast. In particular product(a=1..b)of Gamma(a/b)^LegendreSymbol(a|b) can be thus-expressed hence is superfast. See Kabib Muzaffar & KS Williams 2006: http://mathstat.carleton.ca/~williams/papers/pdf/299.pdf James G. Huard, Pierre Kaplan and Kenneth S. Williams: The Chowla–Selberg formula for genera, Acta Arith., 73 (1995) 271-301. JM Borwein & IJ Zucker: Elliptic Integral Evaluation of the Gamma Function at Rational Values of Small Denominator, IMA J. Numerical Analysis 12 (1992) 519-526 A.Selberg & S.Chowla: On Epstein's Zeta-Function, J. reine angew. Math. 227 (1967) 86-110 especially eq2 p.110 which is repeated as eq7 by D.Broadhurst: http://arxiv.org/pdf/0807.2976v3 If b divides 24 or 60 then all Gamma(a/b) values are expressible in terms of only 10 of them at these arguments: 1/3*, 1/4*, 1/5, 2/5, 1/8*, 1/15*, 1/20*, 1/24*, 1/60, 7/60 and for the *-starred ones those Gammas are expressible in terms of elliptic functions: http://arxiv.org/pdf/math/0403510 Let us assume highly optimistically that product(1<=a<=b and a in S)of Gamma(a/b) is superfast whenever S is a multiplicative or additive subgroup of the integers mod b. What would that, plus the k-tuplication and reflection and add-1 formulae, give us? The number of additive subgroups is the same as the number of divisors of b. The number of multiplicative subgroups is upperbounded by the number of divisors of EulerTotient(b/k) summed over all divisors k of b. Now use the known fact that the number of divisors of N is upperbounded by a function that grows more slowly than any positive power of N, and the known fact N/O(logN)<EulerTotient(N)<N. HENCE the total number of such additive or multiplicative subgroups ("number of equations") grows more slowly than any positive power of b. The reflection formula cuts the number of unknowns by a factor of 2 from b to b/2. The k-tuplication formula cuts them by a factor of no more than about log(b), since e.g. Gamma(a/b) if a is relatively prime to b, are immune. The number of unknowns is thus at least about EulerTotient(b)/2. We conclude that even under our optimistic assumption, for every sufficiently large b we are not going to get anywhere near enough equations to determine the unknowns. So in conclusion, I doubt that more than a finite set of a/b allow superfast evaluation of Gamma(a/b). But it might conceivably be possible to do it for all a when b=48, 60, 120, or 240, say [especially favorable numbers with lots of subgroups but small EulerTotient values]. A possible approach to doing so would be to compute product Gamma(a/b) over subgroups to high precision, then attempt to "recognize" the resulting numbers using PSLQ in terms of Dedekind eta function values, algebraic numbers, powers of 2 and pi, and the like. -- Warren D. Smith http://RangeVoting.org

1 0

Re: [math-fun] line segment passing through a hyperbola-shaped slit
by Dan Asimov 24 Nov '11

24 Nov '11

Actually, Adam's parametrization makes it clear that the surface is doubly-ruled, since by symmetry the expressions for x and y can be interchanged to get the same surface. --Dan Adam wrote: << > It occurs to me to ask: Is there a parametrization of the one-sheeted > hyperboloid that makes it manifest that it's a ruled surface? I believe the following is a valid parametrisation, for much the same reason as the hyperbolic slot demonstration works: x = p cos(theta) + sin(theta), y = p sin(theta) - cos(theta), z = p, where p is a real number; theta is in the interval (-pi,pi]. When theta is constant, varying p corresponds to motion along a straight line. Substituting these expressions into x^2 + y^2 = z^2 + 1 confirms that this parametrisation does indeed describe the hyperboloid. > And: Is there a parametrization that makes it manifest that it's a > doubly-ruled surface? Yes, if there are twelve constants, {a,b,c,d,e,f,g,h,i,j,k,l}, . . . . . . >> ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Why Heronian triangles are integer-posable
by Warren Smith 23 Nov '11

23 Nov '11

A Heronian triangle is a triangle with integer sides and rational area. I can prove by a modular analysis mod 2 and mod 3 that the area automatically always 6*integer. The fact any such triangle is "integer posable" meaning one can place it so its vertices have integer XY coordinates, was proved by Paul Yiu and then by Michael Reid, the latter as a mathfun post. Now let me explain WHY this is true. It is basically because of these facts: 1. multiplying by a complex number performs a rotation and scaling. 2. Gaussian integers a+bi, a,b ordinary integers, have a Euclidean algorithm for finding GCD of two of them. GCD means a divisor of both having maximum length. Here is my C code for that purpose: // GIgcd(ar,ai, br,bi, &gr,&gi) finds g=GCD of two Gaussian Integers a,b void GIgcd(int ar, int ai, int br, int bi, int *gr, int *gi){ int bn,bn2,tr,ti,wr,wi; while(br!=0 || bi!=0){ bn = br*br+bi*bi; //bn = |b|^2 bn2 = bn/2; tr = ar*br+ai*bi; ti = ai*br-ar*bi; //trti = a*conj(b) tr = ( tr + ((tr<0)?(-bn2):(bn2)) )/bn; ti = ( ti + ((ti<0)?(-bn2):(bn2)) )/bn; //trti = a/b rounded to integers wr = ar-tr*br+ti*bi; wi = ai-tr*bi-ti*br; //w = a - b*trti = "a mod b" ar = br; ai = bi; br = wr; bi = wi; } //normalize to be in pospos quadrant: if(ar<0){ ar = -ar; ai = -ai; } if(ai<0){ ti = -ai; ai = ar; ar = ti; //multiplies a by i } *gr = ar; *gi = ai; } 3. Gaussian integers are "prime" if they have no smaller-length divisor. The primes are exactly the Gaussians with length that is a prime 3 mod 4, or the squareroot of a prime 1 mod 4 [and also the Gaussians with length sqrt(2) and 1]. There are exactly 4 Gaussian primes with length P = prime = 3 mod 4 (arising from multiply by 1,-1,i,-i). There are exactly 8 Gaussian primes with length=sqrt(P = prime = 1 mod 4) (arising from multiply by 1,-1,i,-i and conjugation). 4. There is unique factorization of every Gaussian X into primes, except that each prime can be multiplied by (1,-1,i,-i) so long as the total multiple is 1. The primes in the factorization all have squared lengths or lengths that are the same as the ordinary primes in the factorization of |X|^2. 5. Given any rational pose of triangle, we can by multiplying by LCM(denominators) find an integer pose with one vertex at 0+0i. 6. Given any two Gaussian integers A and B, we can find G=GCD(A,B) and then A/G and B/G is an integer pose scaled to have smaller lengths. 7. We also can compute g=GCD(|A|, |B|) if |A| and |B| are ordinary integers. So now: THEOREM: |G|=g. Proof by induction, reduce A, B by dividing out one common Gaussian prime at a time while simultaneously dividing out corresponding ordinary primes from |A|,|B| so that at all stages the norms correspond. If an ordinary prime p=1 mod 4 is divided out, then we can divide out two conjugate Gaussian primes whose product is p. Each inductive step always is possible due to fact 3, and same fact shows that both parallel operations run out of primes at the same time. QED --------------------- OK? So that hopefully not only provides a new posability proof, but also explains nicely "why it works." It's all about the structure of Gaussian prime factorizations. (The same proof also works in the "Eisenstein integers" and probably various other Euclidean rings too.) Now when I came up with this proof, I thought to myself: I'll just generalize this to the Hurwitz quaternionic 4-dimensional 'integers' and maybe even the Cayley octonionic 8D 'integers'! However, that apparently does not work. The reason it does not work is that the analogous "unique factorization into primes" theorems, are not quite as nice: In the Hurwitzes and Cayleys, the number of primes with norm=p is known to be an unboundedly growing function of p (unlike in the Gaussians where there is an upper bound of 8), but there are only at most 576=24*24 ways to alter a Hurwitz number by multiplying by the 24 Hurwitz units on the right and left. Hence, when you want to divide out a Hurwitz prime of norm=p from Hurwitzes A and B with |A| and |B| both divisible by p, in general it will happen that they DO NOT HAVE a common Hurwitz prime divisor with that norm. They instead usually have TWO DIFFERENT Hurwitz prime divisors with that norm. So the theorem that |G|=g is simply false if you try to redo it in the Hurwitzes. However, it might be that Heronian tetrahedra are special -- their vertices are not general Hurwitzes, they are specially nicely related Hurwitzes. For this reason, the theorem might still be able to work for Heronian tetrahedra, but if so, some further ingredient will be needed to prove it. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Galois theory before abstract algebra
by Fred Kochman 23 Nov '11

23 Nov '11

It's in Dickson, Modern Algebraic Theories, reprinted by Dover as Algebraic Theories.

1 0