mersenneforum.org - View Single Post - Estimating the number of primes in a partially-factored number

wblipp · 2014-08-02, 20:53

How about building on the Dickman-de Bruijn function by defining a series

$\rho_k(n)$ is the asymptotic probability that x has exactly k prime divisors greater than x^(1/n).

$\rho_0(n)$ is the standard Dickman-de Bruijn function.

The higher k's can (I think) be defined easily in terms of an integral of (k-1) 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.

2014-08-02, 20:53	#2
wblipp "William" May 2003 New Haven 4503₈ Posts	How about building on the Dickman-de Bruijn function by defining a series $\rho_k(n)$ is the asymptotic probability that x has exactly k prime divisors greater than x^(1/n). $\rho_0(n)$ is the standard Dickman-de Bruijn function. The higher k's can (I think) be defined easily in terms of an integral of (k-1) 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.