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

RE: [math-fun] three integers relatively prime
by Daniel Asimov 13 Dec '04

13 Dec '04

<< Am I making some mistake here: Prob(p divides all three of K, L, M)=1/p^3 Prob(p does not divide all three) = 1 - 1/p^3 giving the final probability as the product of these terms over all p, which is 1/zeta(3) = 0.8319... >> I don't understand the reason you choose to multiply those particular factors (for each prime p). The criterion is that either 0 or 1 of K,L,M can be divisible by p, but no more than 1 of them. --Dan Asimov

1 0

[math-fun] Probability of two (or three) integers being relatively prime
by Daniel Asimov 11 Dec '04

11 Dec '04

Similar to the way I "computed" the probability that a "random pos. int." is quadratfrei, the probability that two "random pos. ints." can also be computed. Call the two pos. ints. K and L. Now (K,L) = 1 <=> For each prime p, it is false that p divides both K and L. But Prob(p divides a random integer N) = 1/p. Assuming "independence" between the prime factors of K and those of L, Prob(p divides each of K and L) = 1/p^2, and so Prob(It is false that p divides each of K and L) = 1 - 1/p^2. Thus, Prob(For each prime p, it is false that p divides each of K and L) = = Product over all primes p of (1 - 1/p^2). Once again this product is the reciprocal of the Euler product for Zeta(2), and so the desired probability is 6/pi^2. ******************************************************************** NOW, how about three random integers K, L, M? By same reasoning, for each p there must be at most one of the three random integers that p divides. The probability of this is Prob(p divides none of K,L,M) + Prob(p divides just one of K,L,M) = (1-1/p)^3 + 3(1/p)*(1-1/p)^2 = 1 - 3/(p^2) + 2/(p^3). Thus Prob(K,L,M) are relatively prime = Product over all prime p of (1 - 3/(p^2) + 2/(p^3)). I don't know how to sum this in closed form, but numerically it turns out that Prob( (K,L,M) = 1 ) ~ 0.1284 (taking the product over the first 1000 primes). It would be nice to know that this jibes with the fraction of random triples of pos. ints. that are rel. prime. --Dan Asimov

2 1

RE: [math-fun] Probability of two (or three) integers being relativelyprime
by N. J. A. Sloane 11 Dec '04

11 Dec '04

I will add Steve Finch's references to this entry in the OEIS: %I A018805 %S A018805 1,3,7,11,19,23,35,43,55,63,83,91,115,127,143,159,191,203,239,255,279, %T A018805 299,343,359,399,423,459,483,539,555,615,647,687,719,767,791,863,899,947, %U A018805 979,1059,1083,1167,1207,1255,1299,1391,1423,1507,1547,1611,1659,1763 %N A018805 Number of elements in the set {(x,y): 1<=x,y<=n, 1=gcd(x,y)}. ... where there is already the comment %F A018805 a(n) ~ (1/Zeta(2)) * n^2 = (6/pi^2) * n^2 as n goes to infinity (zeta is the Riemann zeta function and the constant 6/pi^2 is 0.607927...). - Ahmed Fares (ahmedfares(AT)my-deja.com) Jul 18 2001 As for triples, there is this: %I A071778 %S A071778 1,7,25,55,115,181,307,439,637,841,1171,1447,1915,2329,2881,3433,4249, %T A071778 4879,5905,6745,7861,8911,10429,11557,13297,14773,16663,18355,20791, %U A071778 22495,25285,27541,30361,32905,36289,38845,42841,46027,49987,53395 %N A071778 Number of ordered triples (a, b, c) with gcd(a, b, c) = 1 and 1 <= {a, b, c} <= n. ... for ordered triples. But I'm not sure if the numbers of unordered triples is there. Neil Sloane

1 0

RE: [math-fun] Probability of two (or three) integers being relativelyprime
by Steven Finch 11 Dec '04

11 Dec '04

Hello! See my book "Mathematical Constants", pages 110-112, for more on this topic. You can browse my book freely online. Visit http://pauillac.inria.fr/algo/bsolve/ and click on the word "Google" in the second pararaph. In the search utility, type "carefree". Then select page 110. You'll be able to move ahead two pages as well. Please let me know if you run into any trouble. (I'm unsure why we disagree numerically.) Also see Pieter Moree's unpublished note "Counting carefree couples" at http://web.inter.nl.net/hcc/J.Moree/ The pairwise coprimality result conjected by Moree has been proved to be true: Cai, Jin-Yi; Bach, Eric. On testing for zero polynomials by a set of points with bounded precision, Theoret. Comput. Sci. 296 (2003), no. 1, 15--25. MR1965515 (2004m:68279). Best wishes! Steve Finch >From: "Daniel Asimov" <dasimov(a)earthlink.net> >Reply-To: dasimov(a)earthlink.net, math-fun <math-fun(a)mailman.xmission.com> >To: math-fun(a)mailman.xmission.com >Subject: [math-fun] Probability of two (or three) integers being >relativelyprime >Date: Fri, 10 Dec 2004 23:14:04 -0500 > >Similar to the way I "computed" the probability that a "random pos. int." >is quadratfrei, the probability that two "random pos. ints." can also be >computed. > >Call the two pos. ints. K and L. > >Now (K,L) = 1 <=> For each prime p, it is false that p divides both K and >L. > >But Prob(p divides a random integer N) = 1/p. > >Assuming "independence" between the prime factors of K and those of L, > >Prob(p divides each of K and L) = 1/p^2, and so > >Prob(It is false that p divides each of K and L) = 1 - 1/p^2. > >Thus, Prob(For each prime p, it is false that p divides each of K and L) = > >= Product over all primes p of (1 - 1/p^2). > >Once again this product is the reciprocal of the Euler product for Zeta(2), >and so the desired probability is 6/pi^2. >******************************************************************** > >NOW, how about three random integers K, L, M? > >By same reasoning, for each p there must be at most one of the three random >integers that p divides. The probability of this is > >Prob(p divides none of K,L,M) + Prob(p divides just one of K,L,M) = > >(1-1/p)^3 + 3(1/p)*(1-1/p)^2 = > >1 - 3/(p^2) + 2/(p^3). > >Thus Prob(K,L,M) are relatively prime = > >Product over all prime p of (1 - 3/(p^2) + 2/(p^3)). > >I don't know how to sum this in closed form, but >numerically it turns out that > >Prob( (K,L,M) = 1 ) ~ 0.1284 > >(taking the product over the first 1000 primes). > >It would be nice to know that this jibes with the fraction of random >triples >of pos. ints. that are rel. prime. > >--Dan Asimov

1 0

Re: [math-fun] Random integer question
by Daniel Asimov 09 Dec '04

09 Dec '04

One kind of quasi-probability distribution we can impose on the integers (or let's say the positive integers Z+) is as follows: Define Prob(n * Z+) = 1/n for all n in Z+. Then in particular the probability that a "random" integer is squarefree is the Prob(for all p prime, n is not divis. by p^2) = [assuming independence of divisibility by powers of different primes] = Product over p prime of Prob( n not divis. by p^2) = = Product over p prime of (1 - 1/p^2) = = 1 / Product over p prime of ((1 - 1/p^2)^-1) = [by the euler product for Zeta] = 1 / Zeta(2) = 6/pi^2. --Dan Asimov Regarding statements about random integers, I am reminded of certain abuses of formal notation. For instance, in the statement lim 1/x = 0 x->inf we have a statement of equality in which both sides are defined and equal, whereas lim x^2 = inf x->inf is not actually a statement of equality, and neither side is well-defined. Rather, the statement is taken as a whole to assert that x^2 grows without bound as x grows without bound. This is arguably an acceptable abuse of the equality notation. (Possibly we can make this into an actual equality by augmenting R or by some other means, but let's not go there, that is not my point). Similarly, a statement such as "the probability that an integer picked at random is squarefree is 6/pi^2" cannot be taken as equating two well-defined values, but rather the statement must be interpreted as a whole to mean something else, that is, the "the density of squarefree numbers over the integers is 6/pi^2". I understand that this is the common interpretation, though I am rather more disturbed by this abuse of the notion of probability than I am with the abuse of the notion of limit cited above, since the implied uniform distribution over the integers does not exist, and any existing distribution over the integers is likely to invalidate the statement. For example, if an integer is chosen from a normal distribution with mean 0 and variance 1, is its probability of squarefreeness 6/pi^2? Or if we asked human subjects to choose random integers with no other prompting than "pick a number" (another possible interpretation of "integer chosen at random"), would the number chosen be squarefree with probability 6/pi^2? Anyway, I had a thought about a possible definition for random integer. For integer n >= 0, let D[n] be a uniform distribution over the integers on the range [-n, n]. For a set of integers S, let p_S[n] be the probability that a random integer drawn from D[n] is in S. Then the density of S over Z is just the limit n->inf p_S[n]. To interpret the probability that an integer is in S to be the density of S over Z is more or less like saying that D[n] approaches a hypothetical uniform distribution on Z as n increases. Suppose rather, that we let D[n] (n >= 1) be a discrete normal distribution on Z with mean 0 and variance n. We might then also assert that D[n] approaches a hyprothetical uniform distribution on Z as n increases. Does this definition of D[n] lead us to the same probability of an integer being in S as does the prior definition? If so, can we formalize the notion that a sequence of distributions approaches a hypothetical uniform distribution on Z? Can this be used to rigorize the notion of a pseudouniform distribution on Z? _______________________________________________ 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] Random integer question
by Daniel Asimov 09 Dec '04

09 Dec '04

------------------------------------------------------------------------------------ David Wilson writes: I'm looking at the Mathworld article "Relatively Prime". I see this: The probability that two integers m and n picked at random are relatively prime is [6/pi^2, equation elided]. When we say "random element of set S" without further qualification, the assumption is a uniform distribution. For example, if you pick a random number form 1 to 10, the assumption is each number has probability 1/10. However, no such uniform distribution exists for Z, so an "integer picked at random" is ill-defined, I guess this is well-known. I think what is meant here is: The density of pairs of coprime integers over ZxZ is 6/pi^2. Is that a common interpretation of the original statement? ------------------------------------------------------------------------------------- Actually I've found a way to pick an integer from Z such that all integers have the same chance of being picked (using the Axiom of Choice). But never mind that. And yes, what people mean when they say "the chance that two random integers are coprime = 6/pi^2" is that 6/pi^2 is the limit of A(n) / n^2 as n -> oo, where A(n) is the number of coprime pairs K,L with 1<= K,L <= n. --Dan Asimov _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

[math-fun] Re solving for a sequence
by N. J. A. Sloane 09 Dec '04

09 Dec '04

ms said: I know the solution a[n] to 1-px = product(n = 1 to infinity) (1-x^n)^a[n] through a rather indirect route, but are there techniques for directly solving this equation? me: what's often called the Euler transform on sequences will do the trick this is from the "transforms" file that you can find on the OEIS web site: # EULER takes [a_1,a_2,a_3,...] and produces [b_1,b_2,b_3,...] with # 1 + Sum_{n=1..inf} b_n x^n = 1 / Product_{n=1..inf} (1-x^n)^a_n. here's the Maple code: EULER:=proc(a) local b,c,i,d: if whattype(a) <> list then RETURN([]); fi: c:=[]: for i to nops(a) do c:=[op(c), add( d*did(i,d)*a[d] , d=1..i)]: od: b:=[]: for i to nops(a) do b:=[op(b),(1/i)*(c[i]+ add( c[d]*b[i-d], d=1..i-1))]: od: RETURN(b); end: Here "did" is "did it divide": did:=proc(m,n) if irem(m,n) = 0 then 1 else 0: fi: end: Neil Sloane

1 0

Re: [math-fun] Random integer question
by Daniel Asimov 09 Dec '04

09 Dec '04

Since I plan to publish this when I get around to writing it up, I'm a bit hesitant to go into detail at this point. --Dan --- Daniel Asimov <dasimov(a)earthlink.net> wrote: > Actually I've found a way to pick an integer from Z such that > all integers have the same chance of being picked (using the Axiom > of Choice). How? Gene __________________________________ Do you Yahoo!? Yahoo! Mail - Easier than ever with enhanced search. Learn more. http://info.mail.yahoo.com/mail_250 _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

4 3

[math-fun] Random integer question
by David Wilson 08 Dec '04

08 Dec '04

I'm looking at the Mathworld article "Relatively Prime". I see this: The probability that two integers m and n picked at random are relatively prime is [6/pi^2, equation elided]. When we say "random element of set S" without further qualification, the assumption is a uniform distribution. For example, if you pick a random number form 1 to 10, the assumption is each number has probability 1/10. However, no such uniform distribution exists for Z, so an "integer picked at random" is ill-defined, I guess this is well-known. I think what is meant here is: The density of pairs of coprime integers over ZxZ is 6/pi^2. Is that a common interpretation of the original statement?

1 0

[math-fun] Re: Mismatch between A097398 and UPiNT 3rd ed.
by Richard Guy 08 Dec '04

08 Dec '04

I've had a message from Henry, and any errors are probably due either to my inaccurate transcription, or possibly to typos by Fibonacci Quarterly. As the years go by computers, both electronic and human,get better and better. Perhaps some keen type will check the table below, and even extend it? Many thanks in anticipation. R. On Thu, 2 Dec 2004, Richard Guy wrote: > I'm copying this message to Sloane's Dream Team > in the hope that some computer can settle the > doubtful values (marked ***) in the following > table: > > > \begin{center} > \begin{tabular}{lcccccccccc} > \quad $k$ & 2 & 3 & 4 & 5 & 6 & 7 & 8 & > 9 & 10 & 11 \\ > $x_1=2$ & 43 & 89 & 97 & 214 & 19 & 239 & 37 & > 79 & 83 & 239 \\ > $x_1=3$ & 7 & 89 & 17 & 43 & 83 & 191 & 7 & > 127 & 31 & 389 \\ *** 338? > $x_1=4$ & 17 & 89 & 23 & 139 & 13 & 359 & 23 & > 158 & 41 & 239 \\ *** 139? > $x_1=5$ & 34 & 89 & 97 & 107 & 19 & 419 & 37 & > 79 & 83 & 137 \\ > $x_1=6$ & 17 & 31 & 149 & 269 & 13 & 127 & 23 & > 103 & 71 & 239 \\ > $x_1=7$ & 17 & 151 & 13 & 107 & 37 & 127 & 37 & > 103 & 83 & 239 \\ > $x_1=8$ & 51 & 79 & 13 & 214 & 13 & 239 & 17 & > 163 & 71 & 239 \\ > $x_1=9$ & 17 & 89 & 83 & 139 & 37 & 191 & 23 & > 103 & 23 & 169 \\ *** 239? > $x_1=10$ & 7 & 79 & 23 & 251 & 347 & 239 & 7 & > 163 & 41 & 239 \\ > $x_1=11$ & 34 & 601 & 13 & 107 & 19 & 478 & 37 & > 79 & 31 & 389 > \end{tabular} *** > \end{center} 461? > > Many thanks in anticipation of help. R. > > On Fri, 17 Sep 2004, Hugo Pfoertner wrote: > >> Dear Neil, (CC Richard Guy, Henry Ibstedt), >> >> one month ago I had submitted A097398 >> http://www.research.att.com/projects/OEIS?Anum=A097398 >> >> I just copied it from the URL you had posted >> earlier, asking if someone >> could find interesting stuff in Henry Ibstedt's >> book "Mainly Natural >> Numbers" [1]. At the time when I prepared A097398, >> the on-line version >> of [1] had disappeared, so I didn't include a link >> to it in the >> sequence. >> Currently it is available again, but I don't know >> if that will last >> longer ... >> http://www.gallup.unm.edu/~smarandache/Ibstedt-Book3.pdf >> >> I now compared the table given on page 35 of [1] >> that is reproduced in >> the comment section of A097398 against the >> transposed version given in >> Richard's "Unsolved Problems..., 3rd edition" [2], >> page 329, E15 A >> recursion of Goebel. Whereas the parts k<11 and >> x_1<11 are identical >> (using Richard's notation, the last row (x_11=11) >> and the last column >> k=11 show differences: >> >> x_1=11 [1]: 34 601 13 107 19 461 37 79 31 389 >> Ibstedt >> [2]: 34 601 13 107 19 478 37 79 31 389 >> rkg >> ^^^ >> k=11 [1]: 239 338 139 137 239 239 239 239 239 >> 389 Ibstedt >> [2]: 239 389 239 137 239 239 239 169 239 389 >> rkg >> ^^^ ^^^ ^^^ >> >> I don't know how reliable Henry Ibstedt's results >> are. I did no own >> computations, except for the >> 2,3,5,10,28,154,3520,.. Goebel's sequence. >> The fact that Ibstedt gives a wrong version of >> this sequence in [1], >> >> 2,3,5,10,28,154,3520,_15518880_,267593772160,_160642690122633501504 >> instead of >> 2,3,5,10,28,154,3520, 1551880, 267593772160, >> 7160642690122633501504 >> (A003504) >> >> casts some doubts on the reliability of the >> reproduction of numerical >> results in [1]. Looks like being copied manually. >> I have no idea how to >> resolve the mismatch mentioned above. Fortunately >> the part of the >> rectangular array given in the %S%T%U part of the >> sequence is not >> affected. I do not want to dive deeper into this >> subject, but maybe >> Henry Ibstedt himselve (I CCed this message to >> him) can resolve the >> question. Of course it would be best to >> recalculate his results >> independently. >> >> (BTW: the initialization of A003504 and the >> related sequences is at >> least problematic, as it is described currently - >> division by zero >> results. I'll make an recommendation in a comment >> on A003054 ). >> >> Best wishes to all >> >> Hugo Pfoertner

2 1