April 2006 - mathfun@mailman.xmission.com

[math-fun] Indoor sports: arctan relations
by Joerg Arndt 15 Apr '06

15 Apr '06

During the last week I improved on my 1993 computations finding arctan relations for Pi. here is the data: http://www.jjj.de/arctan/arctanpage.html I am pretty confident the relations up to 11-terms are the best possible. Improving on the 12...17-term relations may be possible but will require a good amount of computation. The 18..22-term samples are likely not optimal, but I could not resists to add the 21-term sample +360698976*arctan(1/1290312057) -218005568*arctan(1/1721451206) ... -234213467*arctan(1/14033378718) == -1 * Pi/4 This is the smallest relation so far that has a least convergent term < 1/10^9. A future computation would require a better algorithm to compute all numbers X so that (X^2+1) is smooth. I used the table of all such numbers smaller than M:=10^10 and the first 64 primes 4*k+1 (761 is the 64th). If someone knows a better algorithm than simply testing the partial factorizations of all X^2+1 kindly let me know. The search took 37 hours, a better table should cover the data up to, say, M:=10^12.

5 6

Re: [math-fun] Little number theory puzzle
by Mike Stay 14 Apr '06

14 Apr '06

How do you select two integers independently at random? On 4/14/06, dasimov(a)earthlink.net <dasimov(a)earthlink.net> wrote: > Given two integers selected independently and at random, > what is the probability they are relatively prime *and* that > each one is squarefree? > > --Dan > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > -- Mike Stay metaweta(a)gmail.com http://math.ucr.edu/~mike

2 1

Re: [math-fun] Little number theory puzzle
by franktaw＠netscape.net 14 Apr '06

14 Apr '06

The probability that both numbers are square-free is (6/pi^2)^2, or 36/pi^4. The probability that a square-free number is divisible by a prime p is (1/p - 1/p^2)/(1 - 1/p^2) = 1/(p+1). Thus the probability that two square-free numbers are relatively prime is product_{p prime} 1 - 1/(p+1)^2. According to A065472, this is approximately .77588351000389549962040428442790, giving an overall probability of .28674742843447873410789271278984 (A065473). This is sometimes called the "strongly carefree" constant. See http://www.gn-50uma.de/alula/essays/Moree/Moree.en.shtml#r20-scfree "Moreover, 0.28675 is also the natural density of pairwise coprime triples of positive integers (relative to all such triples)." Franklin T. Adams-Watters -----Original Message----- From: dasimov(a)earthlink.net To: math-fun <math-fun(a)mailman.xmission.com> Sent: Fri, 14 Apr 2006 19:48:12 -0400 (GMT-04:00) Subject: [math-fun] Little number theory puzzle Given two integers selected independently and at random, what is the probability they are relatively prime *and* that each one is squarefree? --Dan _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com

1 0

[math-fun] "Reverse factoring" complexity of addition
by dasimov＠earthlink.net 13 Apr '06

13 Apr '06

I used to wonder why no one ever stated explicitly just *how* a number is respresented when a factoring algorithm is applied to it, in terms of saying how fast the algorithm is. But it's pretty clear that the input could be in base 10, or 2, or what have you, and at least for a long range of bases -- a factoring algorithm's complexity would vary very little. ---------------------------------------------------------------------------------------------------- Now I'm wondering about a sort of reverse problem: Suppose you're given two numbers solely in terms of their prime factorizations, i.e., the prime powers, in order, up to the last nonzero power: K = (d_1, d_2, . . . , d_r) (= 2^d_1 * 3^d_2 * . . . * p_r^d_r) and L = (e_1, e_2, . . . , e_s) (likewise). Now: What's the fastest way to compute the prime factorization of K + L ? Obviously, one way is to represent K and L to some number base, add, then factor the result. Is there a faster short cut? (Or could a judicious choice of number base make a big difference?) An obvious first step would be to exploit distributivity by factoring out G=gcd(K,L) and working with K' = K/G and L' = L/G. So WLOG assume (K,L) = 1. (And maybe assume further that K and L are squarefree.) --Dan

4 4

[math-fun] Mysterious but well-known identity
by dasimov＠earthlink.net 13 Apr '06

13 Apr '06

This following identity has been floating around for years: integral_0^1 1/x^x dx = sum{k=1,oo} 1/k^k It's reasonably straightforward to prove, but the usual proof (which I'll leave as an exercise for anyone who hasn't seen it), though short, is not especially enlightening. Is there some "explanation" for the form of this identity (*) integral_0^1 f(x) dx = sum{k=1,oo} f(k) (where f is analytic), or is this merely a mathematical "coincidence" (which if it had no proof, might not have a proof) ? --Dan

2 1

Re: [math-fun] What use are primes?
by dasimov＠earthlink.net 13 Apr '06

13 Apr '06

Stan wrote: << I had a student in my computer class ask me a mathematics question: she asked what was the use of prime numbers? She knew there were lots of work done on primes, but what she wanted to know was, what *good* are they, besides being a fascination to math people. >> This is probably not what she meant, but I would say primes are to integers as the elements are to matter: They are the fundamental building blocks. --Dan

1 0

Re: [math-fun] What use are primes?
by Kerry Mitchell 13 Apr '06

13 Apr '06

In jet engines, there are series of blades in the fan. Each stage is composed of a rotating blade and a stationary blade. Often the numbers of blades on the rotor and stator are different primes, or at least coprime, in order to reduce resonance from one blade to the next. Kerry Mitchell -- lkmitch(a)gmail.com www.fractalus.com/kerry

2 1

Re: [math-fun] What use are primes?
by dasimov＠earthlink.net 12 Apr '06

12 Apr '06

Stan Isaacs wrote: << I had a student in my computer class ask me a mathematics question: she asked what was the use of prime numbers . . . . . . >> A lot of cryptography is based on finite fields, and there is a one-to-one correspondence between finite fields (up to isomorphism) and prime powers p^n, where n is any prime 2,3,5,... and n >= 1. (Note: For n = 1 the addition and multiplication are just the usual ones mod p; but for n > 1 they are more subtle. See, e.g., <http://en.wikipedia.org/wiki/Finite_field>.) --Dan

1 0

[math-fun] TEST-Please ignore
by Mike Stay 12 Apr '06

12 Apr '06

Does sending UTF-8 work? -- Mike Stay metaweta(a)gmail.com http://math.ucr.edu/~mike

1 0

RE: [math-fun] Indoor sports: arctan relations
by Phil Carmody 12 Apr '06

12 Apr '06

From: "Schroeppel, Richard" <rschroe(a)sandia.gov> > > Speculations on finding "smooth" X^2+1: > > [What was wrong with "round"? That's what Hardy & Wright use.] That's sooooo last century! > You can generate ordinary integers in order, along with their prime > factorizations, using a priority-queue-like scheme. "Lenstra's Algorithm". By default doesn't give you the factorisations, but that part is trivial post facto. > A similar method should work for X+i, using complex primes. > Unclear if it's any faster than just sieving large blocks of X+i. The set { x^2+1 } is so sparse that sieving just along that polynomial will be fairly fast. O(R^(1/2)). > Both methods are faster than factoring N (or X^2+1) one-at-a-time. But using Euler's factoring shortcut (the original block-GCD method), factoring is exceptionally fast. One needs to add extra prime powers, and could still miss extreme cases, but we're not after exhaustive searching are we, merely computationally efficient searching. My 1-line GP/Pari script finds all P-smooth X^2+1 numbers up to (10^7)^2 in only seconds using this not-completely-naive factoring technique. I only wen't to p=100, and found the following 10^6<X<10^7 1984933 2343692 3449051 6225244 > Both methods adapt to ignoring large prime divisors, just keeping those > up to some limit. Lenstra's method is defined in those terms. Alas it's something like O(f(R)*#p) for f(R)=o(R) by default - the larger your set, the more collisions you have, and the more time you spend hopping down lists trying to find the right place to insert values. So it tends to slow down for large sets of divisors, and may take a while before the smoothness-contraint causes the unspecified o(R) to become preferable to the square+1 constraint's O(R^(1/2)). I have a 'Lenstra Engine' somewhere - if someone wants me to perform some actual hunts for smooth numbers with it, just let me know the details, and I'll get a spare machine onto it immmediately. 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

2 2