mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-04-13, 09:48   #1
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

3×149 Posts
Default 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 4-cores.

Dave

Last fiddled with by drkirkby on 2021-04-13 at 09:49 Reason: Remove the number of unnecessary spaces this forum inserts between paragraphs
drkirkby is offline   Reply With Quote
Old 2021-04-13, 09:55   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

61·97 Posts
Default

Quote:
Originally Posted by drkirkby View Post
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 4-cores.

Dave
https://en.m.wikipedia.org/wiki/Erd%...three%20primes.
The average number of factors is Loglog(n). This was a quick Google.
henryzz is offline   Reply With Quote
Old 2021-04-13, 09:58   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

174410 Posts
Default

Quote:
Originally Posted by drkirkby View Post
So 64 has 6 factors, and 67 has no factors.
That is inconsistent counting.
Nick is online now   Reply With Quote
Old 2021-04-13, 11:19   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

7628 Posts
Default

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 Erdos-Kac but the proof, including that of Mertens' theorem, is a lot simpler.

Last fiddled with by charybdis on 2021-04-13 at 11:20
charybdis is offline   Reply With Quote
Old 2021-04-13, 12:15   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·47·53 Posts
Default

The "normal order" and "average order" are not necessarily the same. Number of distinct prime factors, sum of prime-power 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."
Dr Sardonicus is offline   Reply With Quote
Old 2021-04-13, 12:50   #6
charybdis
 
charybdis's Avatar
 
Apr 2020

7628 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
The "normal order" and "average order" are not necessarily the same.
Indeed, and it's trivial to construct a counterexample. But they are the same for ω(n), and in fact to prove the result I gave above one would want to deal with \(\sum_{n\leq x}\omega(n)\) first, from which we derive the average order.

Quote:
Curiously, the "normal order" of the divisor function is significantly smaller than the "average order."
Technically speaking, it doesn't have a normal order in the strict sense, although its logarithm does. I suppose if you're Hardy and Ramanujan you're allowed to be a bit flexible with your terminology
charybdis is offline   Reply With Quote
Old 2021-04-13, 13:10   #7
drkirkby
 
"David Kirkby"
Jan 2021
Althorne, Essex, UK

1BF16 Posts
Default

Quote:
Originally Posted by Nick View Post
That is inconsistent counting.

I take your point. The only factor of 64 is 2 - I was considering 2x2x2x2x2x2=64 to be 6 factors.



Dave
drkirkby is offline   Reply With Quote
Old 2021-04-13, 14:06   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

115668 Posts
Default

Quote:
Originally Posted by charybdis View Post
Indeed, and it's trivial to construct a counterexample. But they are the same for ω(n), and in fact to prove the result I gave above one would want to deal with \(\sum_{n\leq x}\omega(n)\) first, from which we derive the average order.
Check. It's in the paper I linked to.
Quote:
Technically speaking, it doesn't have a normal order in the strict sense, although its logarithm does. I suppose if you're Hardy and Ramanujan you're allowed to be a bit flexible with your terminology
Yes, but I was being even more "flexible" than they were.

As a non-trivial example where normal and average orders both exist but are different:

For positive integers n, let r2(n) be the number of representations of n as the sum of the squares of two integers. For example, r2(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

\sum_{k\le n}r_{2}(k)\;\approx\;\pi n

so the "average" order of r2(n) is π.

OTOH, it is well known that r2(n) = 0 unless every prime-power factor pe where p == 3 (mod 4) has an even exponent e. It then follows (though not easily) that the proportion of n with r2(n) > 0 tends to 0 as n increases without bound, so the "normal" order of r2(n) is 0.

IIRC r2(n) = 4(d1(n) - d3(n)), where d1(n) and d3(n) are the number of positive integer divisors of n which are congruent to 1 and 3 (mod 4) respectively.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What size of Mersenne number ? Detheris Math 10 2021-04-15 14:55
Triangular number pattern in integer divisors MPT2019 Factoring 32 2019-11-06 23:42
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Size of prime factors found by p-1 method Robertcop Math 10 2006-04-30 22:23
ECM Server for Record Size Factors at 8195 wblipp ElevenSmooth 1 2003-11-25 15:47

All times are UTC. The time now is 19:49.


Tue Oct 19 19:49:02 UTC 2021 up 88 days, 14:18, 0 users, load averages: 2.22, 1.84, 1.72

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.