## Number of factors

Expand Messages
• In the past few days I ve been thinking a lot about the results of the recent prime gaps exercise . Though perfectly obvious after it was explained, the
Message 1 of 7 , Sep 30, 2011
• 0 Attachment
In the past few days I've been thinking a lot about the results of the
recent "prime gaps exercise". Though perfectly obvious after it was
explained, the result still undermines a few well-established beliefs
in my mind, so I'm starting to get horrible results from recent
thought experiments. In particular, I found myself trying to compute
the expected number of factors of a random numbers, after a few of
them were found.

Let's say we have a random number N: we know that we can expect
log(log(N)) distinct prime factors. Great, we found the least of them,
say p. The most obvious, and probably wrong, line of reasoning would
say that one should expect log(log(N))-1 more distinct factors. But
one might as well object that the new number N/p has no memory of
previous factors, and therefore we should expect log(log(N/p)).
However, one should also point out that N/p is no more a random
number, as it has no smaller factors than p. In this case, invoking
Mertens' 3rd theorem considering N/p as a large random number "sieved
up to p", one would obtain yet another result.

In the end, my question is: how many factors should one expect in N/p?
• In primenumbers@yahoogroups.com, ... We need to define an averaging procedure. I follow Hardy and Wright by averaging over the numbers up to N. Then their
Message 2 of 7 , Sep 30, 2011
• 0 Attachment
Bernardo Boncompagni <RedGolpe@...> wrote:

> Let's say we have a random number N:
> 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?

We need to define an averaging procedure. I follow
Hardy and Wright by averaging over the numbers up to N.
Then their Theorem 430 gives

sum(n=1,N, omega(n)) / N = log(log(N)) + B_1 + o(1) ... [1]

as the average number of distinct prime divisors
for /all/ the numbers up to N, where B_1 is the constant
0.261497212847642783755426838608695859051566648261199206192...
of http://mathworld.wolfram.com/MertensSecondTheorem.html

So what is the average of omega(n/p) over the subset S
of numbers n up N that are divisible by p << N ?

There is /no/ change:

sum(n in S, omega(n/p)) / #S = log(log(N)) + B_1 + o(1) ... [2]

since the cardinality of S is #S = floor(N/p)
and the elements of S are found by taking all
positive integers up to #S and multiplying each by p.
Moreover (and crucially)

log(log(#S)) = log(log(N)) + o(1) ... [3]

where I really do mean little-oh in equations [1,2,3].

Finally note that I did not insist that p is a prime. There
is no change produced by selecting any divisor p << N, be it
prime or composite.

David
• ... That is all well and good, but Bernando was asking a different question. What if we average over a different set, T, of numbers up to N for which p
Message 3 of 7 , Sep 30, 2011
• 0 Attachment

> We need to define an averaging procedure. I follow
> Hardy and Wright by averaging over the numbers up to N.
> Then their Theorem 430 gives
>
> sum(n=1,N, omega(n)) / N = log(log(N)) + B_1 + o(1) ... [1]
>
> as the average number of distinct prime divisors
> for /all/ the numbers up to N, where B_1 is the constant
> 0.261497212847642783755426838608695859051566648261199206192...
> of http://mathworld.wolfram.com/MertensSecondTheorem.html
>
> So what is the average of omega(n/p) over the subset S
> of numbers n up N that are divisible by p << N ?
>
> There is /no/ change:
>
> sum(n in S, omega(n/p)) / #S = log(log(N)) + B_1 + o(1) ... [2]
>
> since the cardinality of S is #S = floor(N/p)
> and the elements of S are found by taking all
> positive integers up to #S and multiplying each by p.
> Moreover (and crucially)
>
> log(log(#S)) = log(log(N)) + o(1) ... [3]
>
> where I really do mean little-oh in equations [1,2,3].

That is all well and good, but Bernando was asking
a different question. What if we average over a different
set, T, of numbers up to N for which p << N is the
/least/ prime divisor. That is a subtler question and
I apolgize for not answering it.

• In primenumbers@yahoogroups.com, ... Provided that p
Message 4 of 7 , Oct 1, 2011
• 0 Attachment
Bernardo Boncompagni <RedGolpe@...> wrote:

> Let's say we have a random number N:
> 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?

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...
but this is only a guess. (It is true for p = 2
and looks sensible for N >> p >> 2.)

David
• ... I have proven this for primes p up to 19, but the general proof eludes me. My proof for p = 19 was already laborious and is equivalent to showing that
Message 5 of 7 , Oct 2, 2011
• 0 Attachment

> 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...

I have proven this for primes p up to 19,
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 log(log(N))-log(log(p)). The chance of N being prime is 1/log(N). Invoking Mertens 3rd
Message 6 of 7 , Oct 3, 2011
• 0 Attachment
>
> 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...
>
Interestingly enough, if p>>1, sum=B_1+log(log(p)) and we get
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]
• ... For log(p)
Message 7 of 7 , Oct 3, 2011
• 0 Attachment
Bernardo Boncompagni <RedGolpe@...> wrote:

> > log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)
>
> Interestingly enough, if p>>1, sum=B_1+log(log(p))
> and we get log(log(N))-log(log(p)).

For log(p) << log(N), the average of omega(n/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: