mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-05-15, 18:28   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

166416 Posts
Default 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.
henryzz is offline   Reply With Quote
Old 2012-05-15, 19:17   #2
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

599 Posts
Default

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
mart_r is offline   Reply With Quote
Old 2012-05-15, 22:00   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134548 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2012-05-16, 10:06   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

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 is offline   Reply With Quote
Old 2012-05-20, 21:38   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2012-05-22, 04:22   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,483 Posts
Default

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).
CRGreathouse is offline   Reply With Quote
Old 2012-05-22, 09:16   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
henryzz is offline   Reply With Quote
Old 2012-05-23, 01:13   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172C16 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 00:57.

Wed Oct 28 00:57:18 UTC 2020 up 47 days, 22:08, 2 users, load averages: 1.76, 1.76, 1.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.