20120515, 18:28  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
31·191 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.

20120515, 19:17  #2 
Dec 2008
you know...around...
2^{3}·5·17 Posts 
Maybe this post is relevant to your question:
http://www.mersenneforum.org/showthread.php?t=13737 Last fiddled with by mart_r on 20120515 at 19:21 
20120515, 22:00  #3  
Aug 2006
3×1,993 Posts 
Quote:


20120516, 10:06  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
31·191 Posts 
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. 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.) 
20120520, 21:38  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
31×191 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. 
20120522, 04:22  #6 
Aug 2006
3·1,993 Posts 
Use a weighted sum of the appropriate pi_k.
For example, if you wanted the number of odd 3almostprimes up to x, that's pi_3(x)  pi_2(x/2). 
20120522, 09:16  #7  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
31·191 Posts 
Quote:
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_(k1)(x/2)+pi_(k2)(x/4)pi_(k3)(x/8) ... which you would continue until you have the necessary precision. 

20120523, 01:13  #8  
Aug 2006
3·1,993 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Maximum number of prime factors (3 questions)  siegert81  Factoring  31  20180129 10:41 
Finding prime factors for 133bit number  noodles  YAFU  2  20170512 14:00 
Estimating the number of primes in a partiallyfactored number  CRGreathouse  Probability & Probabilistic Number Theory  15  20140813 18:46 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
Number of Factors for a Mersenne Number  kurtulmehtap  Math  12  20100503 14:02 