- In primenumbers@yahoogroups.com,

Bernardo Boncompagni <RedGolpe@...> wrote:

> Let's say we have a random number N:

Provided that p << N, I guess that the average value

> we know that we can expect

> log(log(N)) distinct prime factors.

> Great, we found the least of them, say p.

>

> In the end, my question is:

> how many factors should one expect in N/p?

of omega(n/p) for the numbers n up to N with least

prime divisor p is

log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)

with B_1 =

0.261497212847642783755426838608695859051566648261199206192...

but this is only a guess. (It is true for p = 2

and looks sensible for N >> p >> 2.)

David - --- In primenumbers@yahoogroups.com,

"djbroadhurst" <d.broadhurst@...> wrote:

> Provided that p << N, I guess that the average value

I have proven this for primes p up to 19,

> of omega(n/p) for the numbers n up to N with least

> prime divisor p is

>

> log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)

>

> with B_1 =

> 0.261497212847642783755426838608695859051566648261199206192...

but the general proof eludes me.

My proof for p = 19 was already laborious and is

equivalent to showing that test(19) is true, here:

{T(n)=local(F=factor(n)[,1]);

sum(k=1,n,sum(j=1,#F,gcd(k,F[j])==1))/n^2;}

{test(p)=local(P=1,D=1,A=1-1/p);

forprime(q=2,p-1,P*=q;D*=1-1/q;A-=1/q);

sumdiv(P,n,moebius(n)*T(n*p))*p/D == A;}

{gettime;forprime(p=2,19,if(test(p),

print("p = "p" proven in "gettime" ms")));}

p = 2 proven in 0 ms

p = 3 proven in 0 ms

p = 5 proven in 0 ms

p = 7 proven in 0 ms

p = 11 proven in 8 ms

p = 13 proven in 141 ms

p = 17 proven in 2926 ms

p = 19 proven in 66089 ms

Challenge: prove that test(p) is true for all prime p.

David (unable to this, at present) >

Interestingly enough, if p>>1, sum=B_1+log(log(p)) and we get

> Provided that p << N, I guess that the average value

> of omega(n/p) for the numbers n up to N with least

> prime divisor p is

>

> log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)

>

> with B_1 =

> 0.261497212847642783755426838608695859051566648261199206192...

>

log(log(N))-log(log(p)).

The chance of N being prime is 1/log(N). Invoking Mertens' 3rd theorem, the

chance of a number sieved up to p being prime should be

log(p)/(log(N)*exp(-gamma)), where gamma is the Euler-Mascheroni constant.

If the log(N) in the number of divisors is distantly related to the chance

of N being prime, one may squeeze this result into our formula obtaining

log(log(N)*exp(-gamma)/log(p))=log(log(N))-log(log(p))-gamma. Not sure if

this last passage makes sense but at this point I guess

log(log(N))-log(log(p)) is a very reasonable answer to the problem. By the

way, N>p^2 means log(log(N))-log(log(p))>log(2) which looks reasonable

enough.

It's even very elegant if one writes it as log(lg(N)), where lg is the

logarithm to base p...

[Non-text portions of this message have been removed]- --- In primenumbers@yahoogroups.com,

Bernardo Boncompagni <RedGolpe@...> wrote:

> > log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)

For log(p) << log(N), the average of omega(n/p),

>

> Interestingly enough, if p>>1, sum=B_1+log(log(p))

> and we get log(log(N))-log(log(p)).

with n running from p to N and p the least

prime divisor of n, is (I claim) asymptotic to the

sum of 1/q, with prime q running from q = p up to

the greatest prime q <= N/p.

All I did was to use Mertens at the upper limit.

For log(2) << log(p) << log(N), one may also use

Mertens at the lower limit to get log(log(N)/log(p)),

as Bernardo has observed. However one should not push

this up to p = O(sqrt(N)), since there we may run into

a problem that worried Chebyshev:

http://tech.groups.yahoo.com/group/primenumbers/message/21565

David (per proxy Pafnuty Lvovich)