- **Miscellaneous Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=56*)

- - **Probability N has a prime factor > sqrt(N)**
(*https://www.mersenneforum.org/showthread.php?t=24706*)

Probability N has a prime factor > sqrt(N)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. |

[QUOTE=carpetpool;523989]For some integer N chosen at random, what is the probability that N has a prime factor > sqrt(N)?[/QUOTE]
See Dickmanâ€“de Bruijn function in [URL="https://en.wikipedia.org/wiki/Dickman_function"]Wikipedia[/URL], [URL="http://mathworld.wolfram.com/DickmanFunction.html"]Wolfram[/URL] and elsewhere. |

It takes a long time to reach an asymptote ...[code]
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 [/code] 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 [code] 1e6 270639 1e8 276912 1e10 282202 1e12 286014 1e14 288791 1e16 291417 1e18 293196 1e20 294238 [/code] 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. |

[QUOTE=fivemack;524128][code]
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 [/code] 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 [/QUOTE] For k=2 the exact result is known, it is 1-log(2). |

All times are UTC. The time now is 11:40. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.