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

Number of factors

Expand Messages
  • Bernardo Boncompagni
    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?
    • djbroadhurst
      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
        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?

        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
      • djbroadhurst
        ... 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
          --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:

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

          David, sadly off topic :-(
        • djbroadhurst
          In primenumbers@yahoogroups.com, ... Provided that p
          Message 4 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 5 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 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]
              • djbroadhurst
                ... For log(p)
                Message 7 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.