mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Estimating the number of prime factors a number has (https://www.mersenneforum.org/showthread.php?t=16820)

henryzz 2012-05-15 18:28

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.

mart_r 2012-05-15 19:17

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

CRGreathouse 2012-05-15 22:00

[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ős-Kac 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.

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. [TEX]\pi_k(n)=\frac{n(\log\log n)^{k-1}}{(k-1)!\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.)

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=CRGreathouse;300016]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).[/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_(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=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_(k-1)(x/2)+pi_(k-2)(x/4)-pi_(k-3)(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.