 mersenneforum.org Probability N has a prime factor > sqrt(N)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2019-08-20, 03:02 #1 carpetpool   "Sam" Nov 2016 32610 Posts 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.   2019-08-21, 01:33   #2
wblipp

"William"
May 2003
New Haven

3×787 Posts Quote:
 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.   2019-08-21, 10:16 #3 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 143578 Posts 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];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 Code: 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. Last fiddled with by fivemack on 2019-08-21 at 10:21   2019-08-21, 10:29   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101101011102 Posts Quote:
 Originally Posted by fivemack Code: c=0;for(t=10^12,10^12+10^6,F=factor(t);lp=F[matsize(F),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).  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post nuggetprime Math 2 2011-03-19 22:14 roger Factoring 3 2007-05-09 22:51 JuanTutors Software 20 2004-09-26 09:47 eepiccolo Math 4 2003-06-07 05:56 Deamiter Math 4 2002-12-25 06:06

All times are UTC. The time now is 23:07.

Sat Apr 10 23:07:52 UTC 2021 up 2 days, 17:48, 1 user, load averages: 4.27, 2.71, 2.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.