20210413, 09:48  #1 
"David Kirkby"
Jan 2021
Althorne, Essex, UK
166_{10} Posts 
What's the average number of factors of an integer of size n?
Are there any estimates/theories/conjectures of the number of factors a random integer of size n has? Clearly any integer could be prime, but could also have factors of multiple factor of 2. So 64 has 6 factors, and 67 has no factors. I rather suspect that someone has worked out the average number of factors an integer of size n would have. I tried a quick test of this in Mathematica, but its factoring algorithm is very dumb  it uses only one core of my computer, and common sense says it could test multiple factors at the same time, not just one. I have 52 cores, but the license is for 4cores.
Dave Last fiddled with by drkirkby on 20210413 at 09:49 Reason: Remove the number of unnecessary spaces this forum inserts between paragraphs 
20210413, 09:55  #2  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{2}·3^{2}·163 Posts 
Quote:
The average number of factors is Loglog(n). This was a quick Google. 

20210413, 09:58  #3 
Dec 2012
The Netherlands
1671_{10} Posts 

20210413, 11:19  #4 
Apr 2020
263 Posts 
A fun exercise is to deduce from Mertens' theorem
\[\sum_{p\leq x}\frac{1}{p} = \log\log x + M + o(1)\] (where M is a constant) that \[\sum_{n\leq x}\omega(n)\log\log n^2 = O(x\log\log x)\] where ω(n) is the number of distinct prime factors of n. This implies that ω(n) cannot stray too far from loglog(n) very often. Of course this is much weaker than ErdosKac but the proof, including that of Mertens' theorem, is a lot simpler. Last fiddled with by charybdis on 20210413 at 11:20 
20210413, 12:15  #5 
Feb 2017
Nowhere
11A5_{16} Posts 
The "normal order" and "average order" are not necessarily the same. Number of distinct prime factors, sum of primepower exponents, and the divisor function (number of positive integer divisors) are discussed in the following paper:
The normal number of prime factors of a number n Curiously, the "normal order" of the divisor function is significantly smaller than the "average order." 
20210413, 12:50  #6  
Apr 2020
263 Posts 
Quote:
Quote:


20210413, 13:10  #7 
"David Kirkby"
Jan 2021
Althorne, Essex, UK
2·83 Posts 

20210413, 14:06  #8  
Feb 2017
Nowhere
4,517 Posts 
Quote:
Quote:
As a nontrivial example where normal and average orders both exist but are different: For positive integers n, let r_{2}(n) be the number of representations of n as the sum of the squares of two integers. For example, r_{2}(1) = 4, using the pairs (1,0), (1,0), (0,1), and (0,1). Considering the points with integer coordinates inside the circle x^2 + y^2 = n, we see that so the "average" order of r_{2}(n) is π. OTOH, it is well known that r_{2}(n) = 0 unless every primepower factor p^{e} where p == 3 (mod 4) has an even exponent e. It then follows (though not easily) that the proportion of n with r_{2}(n) > 0 tends to 0 as n increases without bound, so the "normal" order of r_{2}(n) is 0. IIRC r_{2}(n) = 4(d_{1}(n)  d_{3}(n)), where d_{1}(n) and d_{3}(n) are the number of positive integer divisors of n which are congruent to 1 and 3 (mod 4) respectively. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What size of Mersenne number ?  Detheris  Math  10  20210415 14:55 
Triangular number pattern in integer divisors  MPT2019  Factoring  32  20191106 23:42 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
Size of prime factors found by p1 method  Robertcop  Math  10  20060430 22:23 
ECM Server for Record Size Factors at 8195  wblipp  ElevenSmooth  1  20031125 15:47 