Loading ...
Sorry, an error occurred while loading the content.

Re: Number of factors

Expand Messages
  • djbroadhurst
    In primenumbers@yahoogroups.com, ... Provided that p
    Message 1 of 7 , Oct 1, 2011
    • 0 Attachment
      In primenumbers@yahoogroups.com,
      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
    • djbroadhurst
      ... 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 2 of 7 , Oct 2, 2011
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "djbroadhurst" <d.broadhurst@...> wrote:

        > 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)
      • Bernardo Boncompagni
        ... 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 3 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]
        • djbroadhurst
          ... For log(p)
          Message 4 of 7 , Oct 3, 2011
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            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:
            http://tech.groups.yahoo.com/group/primenumbers/message/21565

            David (per proxy Pafnuty Lvovich)
          Your message has been successfully submitted and would be delivered to recipients shortly.