Estimating the number of prime factors a number has

henryzz · 2012-05-15, 18:28

Has anyone found a formula that gives the probability of a number with a given size having n prime factors? I haven't ever seen one and a google search didn't turn anything up.

mart_r · 2012-05-15, 19:17

Maybe this post is relevant to your question:
http://www.mersenneforum.org/showthread.php?t=13737

CRGreathouse · 2012-05-15, 22:00

Quote:

Originally Posted by henryzz

Has anyone found a formula that gives the probability of a number with a given size having n prime factors? I haven't ever seen one and a google search didn't turn anything up.

The Erdős-Kac theorem with continuity correction gives a decent estimate, but it's not very useful unless n is large.

henryzz · 2012-05-16, 10:06

My aim with this information is to estimate how likely it is for an aliquot sequence with for example 2^4*3*c100 to lose/keep the 3 on the next iteration. $\pi_k(n)=\frac{n(\log\log n)^{k-1}}{(k-1)!\log n}$ should be good enough especially if I can estimate the error.
Since I am using this for aliquot sequences I know certain factors do not divide the composite. In the case of 2^4*3*c100 this is 2 and 3(Note I could also do with doing things like 2^4*7 not just the first n primes. The exponent 4 isn't crucial as well.)

henryzz · 2012-05-20, 21:38

Is there a way of removeing a factor from this formula? For example if I know that 2 is not a factor of the composite.
How much difference should this make? I imagine with 2 it would make quite a bit of difference. With much larger numbers e. g. 31 it wouldn't make nearly so much difference.

CRGreathouse · 2012-05-22, 04:22

Use a weighted sum of the appropriate pi_k.

For example, if you wanted the number of odd 3-almost-primes up to x, that's pi_3(x) - pi_2(x/2).

henryzz · 2012-05-22, 09:16

Quote:

Originally Posted by CRGreathouse

Use a weighted sum of the appropriate pi_k.

For example, if you wanted the number of odd 3-almost-primes up to x, that's pi_3(x) - pi_2(x/2).

Brilliant thanks. Wierdly I actually thought of something similar while going to sleep last night.
Does this sort of start a chain where pi_2(x/2) needs correcting by subtracting from it pi_1(x/4) etc.?
This would lead to pi_k(x)-pi_(k-1)(x/2)+pi_(k-2)(x/4)-pi_(k-3)(x/8) ... which you would continue until you have the necessary precision.

CRGreathouse · 2012-05-23, 01:13

Quote:

Originally Posted by henryzz

Brilliant thanks. Wierdly I actually thought of something similar while going to sleep last night.
Does this sort of start a chain where pi_2(x/2) needs correcting by subtracting from it pi_1(x/4) etc.?
This would lead to pi_k(x)-pi_(k-1)(x/2)+pi_(k-2)(x/4)-pi_(k-3)(x/8) ... which you would continue until you have the necessary precision.

No, one subtraction is good enough for that problem. But for more complicated problems you might need a lot of terms, yes.

2012-05-15, 18:28	#1
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2×3³×109 Posts	Estimating the number of prime factors a number has Has anyone found a formula that gives the probability of a number with a given size having n prime factors? I haven't ever seen one and a google search didn't turn anything up.

2012-05-15, 19:17	#2
mart_r Dec 2008 you know...around... 2×5×67 Posts	Maybe this post is relevant to your question: http://www.mersenneforum.org/showthread.php?t=13737 Last fiddled with by mart_r on 2012-05-15 at 19:21

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Maximum number of prime factors (3 questions)	siegert81	Factoring	31	2018-01-29 10:41
Finding prime factors for 133bit number	noodles	YAFU	2	2017-05-12 14:00
Estimating the number of primes in a partially-factored number	CRGreathouse	Probability & Probabilistic Number Theory	15	2014-08-13 18:46
Number of distinct prime factors of a Double Mersenne number	aketilander	Operazione Doppi Mersennes	1	2012-11-09 21:16
Number of Factors for a Mersenne Number	kurtulmehtap	Math	12	2010-05-03 14:02

2012-05-16, 10:06	#4
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5886₁₀ Posts	My aim with this information is to estimate how likely it is for an aliquot sequence with for example 2^43c100 to lose/keep the 3 on the next iteration. $\pi_k(n)=\frac{n(\log\log n)^{k-1}}{(k-1)!\log n}$ should be good enough especially if I can estimate the error. Since I am using this for aliquot sequences I know certain factors do not divide the composite. In the case of 2^43c100 this is 2 and 3(Note I could also do with doing things like 2^4*7 not just the first n primes. The exponent 4 isn't crucial as well.)

2012-05-20, 21:38	#5
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2·3³·109 Posts	Is there a way of removeing a factor from this formula? For example if I know that 2 is not a factor of the composite. How much difference should this make? I imagine with 2 it would make quite a bit of difference. With much larger numbers e. g. 31 it wouldn't make nearly so much difference.

2012-05-22, 04:22	#6
CRGreathouse Aug 2006 3·1,993 Posts	Use a weighted sum of the appropriate pi_k. For example, if you wanted the number of odd 3-almost-primes up to x, that's pi_3(x) - pi_2(x/2).