July 2006 - mathfun@mailman.xmission.com

Re: Re: [math-fun] Twisted puzzle
by Phil Carmody 15 Jul '06

15 Jul '06

I wrote about 5 minutes ago: > I got to the 21st page in about 5 minutes, but have no idea ... D'oh! That was one I should have solved instantly. 5 more minutes gets one to: "you win (for now)" Phil () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

Re: Re: [math-fun] Twisted puzzle
by Phil Carmody 15 Jul '06

15 Jul '06

From: "Michael Kleber" <michael.kleber(a)gmail.com> > > David Wilson wrote: > > > It's pretty simple. Click the "1" and you end up on a page with a "2". > > ...and, by induction, you're done! > > (I looked just before bed last night and made it to around 14; looks like > fun so far.) 13 was a bit poor as it didn't follow the pattern. I was trying things to do with 'valentines' for several minutes. It's otherwise fun up until about 18, then it gets tawdry. Even more tawdry for those with unsanitary browsing habits. > > > I just wasted several hours getting all the way to the end of this > puzzle: > > > > > > http://n.nfshost.com/1.html I got to the 21st page in about 5 minutes, but have no idea what to do with a word that ouside the quiz only exists on a single page in Hungary, according to google. Apologies if this is latein the thread, I read the digest and can sometimes appear to be quite a way behind the thrust of a discussion. Phil () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

[math-fun] Twisted puzzle
by Jason Holt 15 Jul '06

15 Jul '06

I just wasted several hours getting all the way to the end of this puzzle: http://n.nfshost.com/1.html -J

3 2

[math-fun] difference engine (was Re: pi)
by Steve Witham 13 Jul '06

13 Jul '06

>From: "Alec Mihailovs" <alec(a)mihailovs.com> >Another approach is using a polynomial approximation of sin. Linear >approximation sin(x) = x is not very good. For x=pi/6 it gives 1/2=pi/6 and >pi=3. However, cubic approximation sin(x) = x + Ax^3 is already pretty good >(quadratic term is not present because sin is odd). That reminds me of a question I've wanted to ask here. I have fun conceptual design for a difference engine that uses paper tape and computes one digit (of one order of difference) at a time. But I would like to have a good example to run. Didn't they actually used to use the method of differences to calculate trig & log tables by hand? If so, how did they calculate the initial numbers for each page (say) without having to do more work than it takes to calculate the entries separately? Do you just calculate the first n entries manually, then take the differences, differences of differences, etc., or is there a more numerical-methods way? --Steve

1 0

RE: [math-fun] Calculating pi
by Schroeppel, Richard 13 Jul '06

13 Jul '06

A simpler iteration for sin(theta/3) comes from "solving" the triplication equation: sin(3x) = 4 sin(x)^3 - 3 sin(x) sin(x) = (sin(3x) + 4 sin(x)^3) / 3 The iteration is to plug the current guess for sin(x) into the RHS, giving an improved guess for sin(x) on the LHS. Unfortunately, the convergence is inferior to RWGs scheme -- merely linear. If we assume out current guess is sin(x)+eps, the new guess is sin(x) + eps * (4 sin(x)^2) + ... . This gives OKish convergence for small sines. If sin(3x) = 1/2, and we take the first guess for sin(x) = sin(3x)/3 (i.e., a 0th guess of sin(x)=0), the next iteration is sin(x) = 14/81 = .1728... . The error has dropped from .0070 to .0008. Successive steps will get another factor of 8 each time. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com] On Behalf Of R. William Gosper Sent: Thursday, July 13, 2006 4:46 AM To: math-fun(a)mailman.xmission.com Subject: Re: [math-fun] Calculating pi Archimedes' pi method with sin(pi/6), sin(pi/12), sin(pi/24), ... requires a sqrt for each new sine. If instead, we sought sin(pi/6), sin(pi/18), sin(pi/54), ..., we'd need a cbrt, but each iteration provides an excellent starting value for a Newton iteration for the next cbrt. The triple angle formula is (c102) (sin(3*x),%% = decosify(trigexpand(%%))) 2 3 (d102) sin(3 x) = 3 sin(x) (1 - sin (x)) - sin (x) We can't solve this for sin(x) without a nasty complex cubic, which explains why there's no nice expression for sin(pi/9), etc. But letting S := sin(3x), s := sin(x), the Newton step toward s given S is (c197) newt : (8*s^3-\s)/(3*(4*s^2-1)) 3 8 s - S (d197) ------------ 2 3 (4 s - 1) Starting sith S = sin(pi/6), (c198) subst(1/2,\s,newt) 3 1 8 s - - 2 (d198) ------------ 2 3 (4 s - 1) we seek s = sin(pi/18), using sin(pi/6)/3 as our first guess: (c199) subst(1/6.0d0,s,%) (d199) 0.17361111111111d0 plugging back in (c200) subst(%,s,d198) (d200) 0.17364817658193d0 once more (c201) subst(%,s,d198) (d201) 0.17364817766693d0 This has converged, since the agreement doubles each time. So now we go for sin(pi/54) (c202) subst(%,\s,newt) 3 8 s - 0.17364817766693d0 (d202) ------------------------- 2 3 (4 s - 1) starting with sin(pi/18)/3: (c203) subst(d201/3,S,%) (d203) 0.05814481276438d0 (c204) subst(%,s,d202) (d204) 0.05814482891048d0 Already finished! Go for sin(pi/162). (c205) subst(%,\s,newt) 3 8 s - 0.05814482891048d0 (d205) ------------------------- 2 3 (4 s - 1) (c206) subst(d204/3,s,%); (d206) 0.01939133176448d0 [...] (c211) subst(%,\s,newt) 3 8 s - 0.00646413739654d0 (d211) ------------------------- 2 3 (4 s - 1) (c212) subst(d210/3,s,%) (d212) 0.00215472580425d0 Now we don't even need to iterate! (c213) subst(%,s,d211) (d213) 0.00215472580425d0 This was our fifth thirding of pi/6: (c214) (sin(%pi/6/3^5),%% = dfloat(%%)) %pi (d214) sin(----) = 0.00215472580425d0 1458 (c215) 1458*%; %pi (d215) 1458 sin(----) = 3.14159022259953d0 1458 Here's a different recursion, based on tangents: On 18 Apr 05 I sent > [...] another one of those annoying little pi iterations: (c124) tn2(x):=if equal(12,12-(x:x/2)^2) then x else ((tn2(x)-x)/2,2*x-4/(%%-1/%%)) x 2 (d124) tn2(x) := if equal(12, 12 - (x : -) ) then x 2 tn2(x) - x 4 else (----------, 2 x - -------) 2 1 %% - -- %% The symbol %% is a pronoun meaning the most recent result in the computation, in this case, (tn2(x)-x)/2. tn2(x) computes x-2*tan(x/4) recursively via the tangent double angle formula. Iterating this function converges quadratically to pi: (c125) tn2(3.0) (d125) 1.1368 (c126) tn2(2+%) (d126) 1.14158 (c127) tn2(2+dfloat(%)) (d127) 1.14159265355336d0 (c128) (bfprecision:23,tn2(2+bfloat(%))) (d128) 1.1415926535897932384623b0 Finally, in late '02 I sent a method based on an amazingly simple way to compute the vector [sin(x), sin(x/3), ..., epsilon], where sin(epsilon) ~ epsilon, again using the triple angle formula: (c6) sn3(x) := if equal(6,x+6) then [x] else (sn3(x/3),cons(%%[1]*(3-4*%%[1]^2),%%))$ Then with the help of magic rational vectors we can get pi with any desired rate of convergence. E.g., for 9th order (enneadic?): (c134) pi27(x):=x+[-1/12579840,1/5120,-243/5120,531441/465920] . part(sn3(27*x),1..4)$ (c137) pi27(22/7.b0); (d137) 3.14159265358979323846264339539b0 (In case anybody missed it, pi27(d137) would give *nine times* as many correct digits.) The magic vector is 1 (d139) ------------------------------ 1 1 n - k (-; -) 3 (9; 9) 9 9 k - 1 n - k n = 4, k=1..4, and (a;q)_n is the q-Pochhammer symbol (1-a)(1-aq)...(1-aq^(n-1)). Of course, if you have a sin function simply iterating x <- x + sin x will triple the number of digits of pi each time, as Gene Salamin pointed out many years ago in HAKMEM. --rwg _______________________________________________ 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] Calculating pi
by Schroeppel, Richard 12 Jul '06

12 Jul '06

A straightforward approach is to calculate the area of the quarter circle in the first quadrant. Split the circle into 10 vertical segments, and use the trapezoid rule to get inside and outside estimates for the area. This requires nothing worse than square roots and slopes of tangent lines -- a minimum of analytic geometry. It's easy to see that bumping up the number of slices to 100 will reduce the error by a factor of around 10. This part can be programmed numerically. The next step is deeper: Writing out the binomial for sqrt(1-x^2), believing it converges (at least out to x=1/2), rearranging the terms to make an integral, and accepting integral(x^K) = x^(K+1)/(K+1), may take some selling. But after that, you actually have a reasonably convergent series for pi, related to arcsin(1/2) and the area of the portion of the unit circle between x=0 and x=1/2 and y>=0. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com] On Behalf Of Jason Holt Sent: Wednesday, July 12, 2006 2:05 PM To: math-fun Subject: [math-fun] Calculating pi A friend of mine recently asked me what pi is all about. This was rather remarkable, as he's failing out of high school, and people treat him like a failure. Turns out he's fascinated by physics and math. Anyway. So I described pi in terms of the experimental method of drawing circles and noticing that their circumference always seems a little more than 3 times their diameter. That led to a great discussion about experimental vs. theoretical science, and eventually he asked me how we went from experimental methods of calculating pi to computational approaches. I checked the wikipedia, but its approaches all seem to assume advanced math to prove that the approximations describe pi, and he hasn't gotten past algebra and geometry. At this point, the simplest approach I can think of is to write a program to choose random points in a circumscribed circle, then calculate the proportion of the points which fall within it. But that still has a heuristic element to it. Are there any plain arguments for the deterministic approximations? (For that matter, how about doing the same thing for the trig functions? I took the same approach for sin/cos/tan, talking about building a table of angle/ratio measurements, but I had no idea how to describe computational approaches.) -J _______________________________________________ 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] Calculating pi
by Cordwell, William R 12 Jul '06

12 Jul '06

Buffon's needle experiment combines, in a sense, experiment and trig. Although the derivation might be too advanced, it could be presented heuristically, I think. There are lots of simulations available on the web. --Bill C. -----Original Message----- From: math-fun-bounces+cordwell=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com] On Behalf Of Jason Holt Sent: Wednesday, July 12, 2006 3:06 PM To: math-fun Subject: Re: [math-fun] Calculating pi On Wed, 12 Jul 2006, Richard Guy wrote: > Surely best to follow Archimedes and > calculate the perimeters of inscribed > and circumscribed regular 6-, 12-, > 24-, ...-gons? R. Working that out computationally seems to require sines, so that the problem of calculating pi reduces to the problem of calculating sines, yes? -J _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] System of 3 equations
by Christian Boyer 12 Jul '06

12 Jul '06

Do you know if it is possible to solve this system of equations, with n=3 or 4: a^n + b^n = c^n + d^n e^n + f^n = g^n + h^n (ae)^n + (bf)^n = (cg)^n + (dh)^n a,b,c,d,e,f,g,h being distinct integers. Solutions with n=1 or 2 are easy to find. For example: 1 + 4 = 2 + 3 6 + 7 = 5 + 8 (1*6) + (4*7) = (2*5) + (3*8) 2² + 11² = 5² + 10² 79² + 46² = 86² + 31² (2*79)² + (11*46)² = (5*86)² + (10*31)² But what about n=3? I am unable to find at least one solution. And n=4 seems hopeless. Christian.

1 0

RE: [math-fun] Prime "number system" ? (Goldbach, etc.)
by Schroeppel, Richard 11 Jul '06

11 Jul '06

The Prime Number Theorem, pi(X) ~ X/logX, implies that the ratio of consecutive primes approaches 1 as a limit. In fact, a bit more is proven - roughly, for large enough numbers, there's always a prime between any two cubes. So by taking the representation of N to be (largest prime <= N) + (recurse to represent the balance), each prime will reduce the size of the leftover from N down to O(N^(2/3)), and the total number of terms is around O(loglogN). Of course, if you allow Goldbach, then 3 primes is likely always enough. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com] On Behalf Of Henry Baker Sent: Monday, July 10, 2006 2:19 PM To: Michael Reid Cc: math-fun(a)mailman.xmission.com Subject: Re: [math-fun] Prime "number system" ? (Goldbach, etc.) Interesting. Is it then true that there is a prime of every length when expressed in the binary system? Then I suppose we could always choose the smallest such for each length, and we would never need more than ~log_2(n) such numbers in the representation. So this representation is as compact as the usual binary system? At 01:08 PM 7/10/2006, Michael Reid wrote: >> In an analogy with Zeckendorf (Fibonacci) number systems, can every >> positive integer be expressed as a _sum_ of _distinct_ (positive) primes ? >> >> If not, what is the smallest integer not so expressible? >> >> For this purpose, I'll allow "1" as a "prime", although I suspect >> it's only needed a constant number of times. > >yes, with your convention of considering 1 to be prime. >you've already shown how to do the first few cases. >for a larger value of N , let p be the largest prime <= N . >then p > N/2 , by the theorem usually called "Bertrand's postulate". >express N - p as a sum of distinct "primes", and add p to the >result. since p > N - p , the primes in this sum are distinct. > >it is probably easy to modify this argument to show that 1 is only >needed a few times (twice?) > >mike _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] sqrt( |Rubik| )
by Steve Witham 10 Jul '06

10 Jul '06

>From: "Schroeppel, Richard" <rschroe(a)sandia.gov> > >We now have enough computing power to find & prove the distance- >to-start for any particular position, using the obvious square-root >meet-in-the-middle algorithm and a big disk. http://en.wikipedia.org/wiki/Rubik%27s_Cube_group says that the number of positions is ( 8! 3^8 12! 2^12 ) / 12 = 43,252,003,274,489,856,200 so the square root is about 6,576,625,523 Each position needs about 5 bytes, and I guess having two copies of the set would make it go a lot faster, so that's 66 terabytes...by my amateur guess. This NYT article about Google's new server farm complex in The Dalles, Oregon http://tinyurl.com/pfvz8 says, "The best guess is that Google now [pre-The Dalles] has more than 450,000 servers spread in at least 25 locations around the world. " If those servers each have 2x10^8 ips, that's about 10^14 ips, which matches Hans Moravec's estimate of the effective power of a human brain (though not in a tight enough cluster). --Steve

2 1