Re: The squarefree part of a number


Hugo Pfoertner wrote:
> oswald.kluge@xxxxxx wrote:
> >
> > Dear reader,
> >
> > given a natural number s the "squarefree part" c of s is
> > the product of the distinct prime divisors q of s:
> >
> > c = PROD q st. prime q | s
> >
> > I got several questions regarding c:
> >
> > 1. Is there a faster algorithm for constructing c other
> > than complete prime decomposition?
> >
> > 2. Given a random number s, what is the maximal
> > number of distinct primes dividing s?
> >
> > 3. What is the most probable number of primes dividing s?
> >
> > 4. What is the most probable proportion of c and s?
> >
> > Answers and/or references would be greatly appreciated!
> >
> > Kind regards,
> > Oswald
>
> See Hardy, Wright, An Introduction to the Theory of Numbers, 5th
> Edition,
> Oxford Science Publications, 1979. Chapter 22, pp.340-374.
>
> The expected number of different prime factors of n for n->infinity is
> ~ log(n)/(log log(n))

I think you meant just log log n. Theorem 430 in H&W(pg. 355) is "The
average order of omega(n) and Omega(n) is log log n." H&W then gives a
more precise fomulation.
(In H&W's notation omega(n) is the number of distinct prime factors of
n and Omega(n) is the number of total prime factors counting
multiplicity. I have replace the greek letters for ease of reading)
Then later there is Theorem 431 "The normal order of omega(n) and
Omega(n) is log log n)." Again, a more precise result is then given.
Now, if you look at max omega(n) for n < x, this will be ~ log(n)/log
log n. Was this what you were thinking about?

> Donald Knuth's The Art of Computer Programming Vol.2 Seminumerical
> Algorithms, Ch. 4.5.4 Factoring into Primes pp.379-417, especially pages
> 383, 384. gives statistical information on the size and total number of
> prime factors.
>
> Hugo Pfoertner

.