John, which precise entry in HAKMEM are you referring to?
On Wed, May 7, 2008 at 3:22 PM, Miodrag <[EMAIL PROTECTED]> wrote:
> Very nice problem, went against my initial guess anyway. I, however,
> get the probability that the denominator is not divisible by prime p
> to be p/(1+p), i.e. probability that it is divisible by prime p is
> 1/(1+p).
>
> Argument goes something like this: the probability that p^k is the
> highest power of p that divides an integer is P_k = (1/p^k)(1-1/p).
> Probability that the denominator is not divisible by p is
> Sum_{k>=0}Sum_{0<= j <=k}P_j P_k
> which comes out to p/(1+p)
>
> On Wed, May 7, 2008 at 2:37 PM, John Randall
>
> <[EMAIL PROTECTED]> wrote:
>
>
> > Raul Miller wrote:
> > > I think that randomness might be something of a distraction
> > > from the main point
> >
> > OK: here's my argument.
> >
> > Let p and q be random nonzero integers.
> >
> > Define events
> >
> > E : denominator of reduced fraction p/q is even.
> >
> > E(n): q is divisible by 2^n ; q is divisible by 2^n-1 but not 2^n.
> >
> > Then the E(n) constitute a partition of E.
> >
> > Since p(E(n))=1/2^(2*n),
> >
> > p(E)=1/4+1/16+1/64+....=1/3.
> >
> > The same argument gives the even more surprising result that the
> > probability of the denominator being divisible by a prime p is
> > 1/((p^2)-1.
> >
> > The problem of this argument is that it depends on p and q: the E(n)'s
> > become empty after a while. Whether this is is important depends on
> > how randomness is defined.
> >
> >
> >
> > Best wishes,
> >
> > John
> >
> >
> >
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> >
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
