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

Re: [math-fun] Little number theory puzzle
by dasimov＠earthlink.net 15 Apr '06

15 Apr '06

Mike Stay inquires: << How do you select two integers independently at random? To pick one integer at random, just consider a dense subgroup of the circle C = R/Z -- say G = {n*sqrt(2) mod 1 : n is in Z} -- and consider the cosets C/G. Let W be a subset of C containing exactly one representative of each coset. Then C is the disjoint union of the countably many translates of W of the form T_k = k + W, for k in Z. Finally, pick a point at random from C. It belongs to exactly one T_k, and then k is your random integer. Pick another point independently from C in the same way to get two independent random integers. --Dan

2 1

[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