Probability N has a prime factor > sqrt(N)

[carpetpool]

For some integer N chosen at random, what is the probability that N has a prime factor > sqrt(N)? This also includes when N is prime, therefore the probability is greater than 1/ln(N).

Furthermore, what's the probability that N has a prime factor > N^(1/k) ?

Thanks for any new leads.

[wblipp]

Originally Posted by carpetpool

For some integer N chosen at random, what is the probability that N has a prime factor > sqrt(N)?

See Dickman–de Bruijn function in Wikipedia, Wolfram and elsewhere.

[fivemack]

c=0;for(t=10^12,10^12+10^6,F=factor(t);lp=F[matsize(F)[1],1];if(lp*lp<=t,c=1+c)); c

The normal suggestion is that it's about k^-k, so 1/4. But sampling ranges of 10^6 at different places suggests that the count (and so the implied probability) goes up perceptibly for larger N

1e6  270639
1e8  276912
1e10 282202
1e12 286014
1e14 288791
1e16 291417
1e18 293196
1e20 294238

Assuming that we're dealing with a Poisson process with a fixed probability at each sampling point, which I don't think is unfair, those observations are not consistent with the probability being the same at 1e6 as at 1e18.

[R. Gerbicz]

Originally Posted by fivemack

c=0;for(t=10^12,10^12+10^6,F=factor(t);lp=F[matsize(F)[1],1];if(lp*lp<=t,c=1+c)); c

The normal suggestion is that it's about k^-k, so 1/4. But sampling ranges of 10^6 at different places suggests that the count (and so the implied probability) goes up perceptibly for larger N

For k=2 the exact result is known, it is 1-log(2).