20140801, 19:09  #1 
Aug 2006
13533_{8} Posts 
Estimating the number of primes in a partiallyfactored number
I'm interested in using information about a number to estimate the likelihood of it having a certain number of prime factors.
If we had no information about the number except its size, there are two obvious approaches: the ErdősKac theorem plus continuity correction, or Landau's extension to the Prime Number Theorem: Hildebrand, Tenenbaum, and various collaborators have versions of this formula which works over a larger range, though all results are stated asymptotically so it's hard to tell over what ranges each would be best suited. It's not obvious to me when I should use each of the various estimates. (I also wonder if there is an integral formulation of Landau's theorem, just like Li(x) is a better approximation to pi(x) than x/log x.) Things get even more interesting if you add in partial factorization. First, it essentially takes care of the difference between distinct and indistinct factorizations, since beyond a fairly small point you don't see repeated prime factors of that size 'in the wild'. Second, it should be able to use the factorization information to refine the above estimates. Essentially you'd expect about log log x primes out of the first x, and you should be able to subtract this delta from the ErdősKac estimate directly. (It's not so clear how to modify Landau's formula.) I ask these questions because in the range of numbers of interest (from those we can factor fairly easily to those we can check for probable primality fairly easily) the numbers are small enough that constant factors and o(1)'s matter. And (pipe dream?) if the calculations are fairly routine we might ask Syd (or, for that matter, Alpertron) to include them in factordb (resp., his ECM page). 
20140802, 20:53  #2 
"William"
May 2003
New Haven
2^{2}·593 Posts 
How about building on the Dickmande Bruijn function by defining a series
is the asymptotic probability that x has exactly k prime divisors greater than x^(1/n). is the standard Dickmande Bruijn function. The higher k's can (I think) be defined easily in terms of an integral of (k1) functions. I'd hope that this heuristic gives a probability density for the number of large primes, with "large" defined by the choice of n. You could use the knowledge of prior factoring effort to choose interesting definitions of "large," and apply Bayes' theorem to modify the density to account for the prior effort. 
20140802, 21:48  #3  
"Bob Silverman"
Nov 2003
North of Boston
1110100101000_{2} Posts 
Quote:
probability that a large integer N has k prime factors given that it has no factors less than (say) N^1/a, for given a. 

20140803, 04:06  #4  
"William"
May 2003
New Haven
2^{2}×593 Posts 
Quote:
For these scenarios, I think you would be better off to start with the entire original number and the distibutions I described, then use Bayes to account for the known factoring efforts. But it doesn't really matter what I think or you think  this is a question of comparing heuristics that can studied empirically. Perhaps we can get the OP to propose some "interesting" cases. 

20140803, 05:42  #5  
Aug 2006
175B_{16} Posts 
Quote:
But at the ranges that I've tested it the Dickman function already does a fairly poor job; not sure how these would fare, better or worse. Sounds reasonable. 

20140803, 06:12  #6  
Aug 2006
1011101011011_{2} Posts 
Quote:
I think the amount of work on MM127 is wellknown. It doesn't look like XYYX has worked on the other one, so suppose not much work has been done on it. Last fiddled with by CRGreathouse on 20140803 at 16:43 

20140804, 14:54  #7 
Aug 2006
3·1,993 Posts 
Using (to avoid the extra variability from the small primes that brings) and searching an interval around 10^{20} I find
1 distinct prime factor: 4290 2 distinct prime factors: 21379 3 distinct prime factors: 44810 4 distinct prime factors: 54544 5 distinct prime factors: 42306 6 distinct prime factors: 22179 7 distinct prime factors: 8090 8 distinct prime factors: 2022 9 distinct prime factors: 331 10 distinct prime factors: 49 11 distinct prime factors: 1 which compares to the (naive) Landau predictions of 1 distinct prime factor: 4342 2 distinct prime factors: 16632 3 distinct prime factors: 31849 4 distinct prime factors: 40658 5 distinct prime factors: 38928 6 distinct prime factors: 29817 7 distinct prime factors: 19032 8 distinct prime factors: 10412 9 distinct prime factors: 4984 10 distinct prime factors: 2121 11 distinct prime factors: 812 and the ErdősKac predictions 1 distinct prime factor: 29250 2 distinct prime factors: 51228 3 distinct prime factors: 70509 4 distinct prime factors: 76319 5 distinct prime factors: 64973 6 distinct prime factors: 43492 7 distinct prime factors: 22872 8 distinct prime factors: 9438 9 distinct prime factors: 3051 10 distinct prime factors: 772 11 distinct prime factors: 152 This supports the intuition that Landau is better for small numbers of prime factors and ErdősKac better for large. In this case the crossover is surprisingly large (8 prime factors) but neither estimate is particularly accurate. 
20140804, 18:26  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 
Quote:


20140804, 18:33  #9  
Aug 2006
3×1,993 Posts 
Quote:
But it would still be useful to have good estimates for these ranges. Any ideas of what techniques could be used? 

20140804, 21:47  #10  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 
Quote:
ErdosKac thm. 

20140805, 00:05  #11 
Aug 2006
1011101011011_{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne number factored (disbelievers are biting elbows)  alpertron  Data  589  20220703 19:04 
Largest Mersenne Number Fully Factored?  c10ck3r  Data  49  20171210 19:39 
Possibility of a FullyFactored Number  Trejack  FactorDB  7  20160514 05:38 
Estimating the number of prime factors a number has  henryzz  Math  7  20120523 01:13 
230 bits! M1237 (partially) factored  petrw1  Factoring  5  20101103 11:31 