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.

Maybe this post is relevant to your question:
[URL]http://www.mersenneforum.org/showthread.php?t=13737[/URL] 
[QUOTE=henryzz;299546]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.[/QUOTE]
The [url=http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem]ErdÅ‘sKac theorem[/url] with [url=http://en.wikipedia.org/wiki/Continuity_correction]continuity correction[/url] gives a decent estimate, but it's not very useful unless n is large. 
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. [TEX]\pi_k(n)=\frac{n(\log\log n)^{k1}}{(k1)!\log n}[/TEX] 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.) 
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. 
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). 
[QUOTE=CRGreathouse;300016]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).[/QUOTE] 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_(k1)(x/2)+pi_(k2)(x/4)pi_(k3)(x/8) ... which you would continue until you have the necessary precision. 
[QUOTE=henryzz;300025]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_(k1)(x/2)+pi_(k2)(x/4)pi_(k3)(x/8) ... which you would continue until you have the necessary precision.[/QUOTE] No, one subtraction is good enough for that problem. But for more complicated problems you might need a lot of terms, yes. 
All times are UTC. The time now is 05:38. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.