mersenneforum.org > Math Estimating the number of prime factors a number has
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-15, 18:28 #1 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2·5·599 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... 76110 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
2012-05-15, 22:00   #3
CRGreathouse

Aug 2006

135338 Posts

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.

 2012-05-16, 10:06 #4 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 10111011001102 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. $\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.)
 2012-05-20, 21:38 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 2×5×599 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).
2012-05-22, 09:16   #7
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

2·5·599 Posts

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.

2012-05-23, 01:13   #8
CRGreathouse

Aug 2006

597910 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 Factoring 31 2018-01-29 10:41 noodles YAFU 2 2017-05-12 14:00 CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 kurtulmehtap Math 12 2010-05-03 14:02

All times are UTC. The time now is 08:36.

Fri Jul 1 08:36:17 UTC 2022 up 78 days, 6:37, 0 users, load averages: 1.38, 1.56, 1.58