mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-08-20, 03:02   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

311 Posts
Post 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.
carpetpool is offline   Reply With Quote
Old 2019-08-21, 01:33   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
wblipp is offline   Reply With Quote
Old 2019-08-21, 10:16   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18D616 Posts
Default 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
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
fivemack is offline   Reply With Quote
Old 2019-08-21, 10:29   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

11×127 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
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).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Probability of factor (TF) nuggetprime Math 2 2011-03-19 22:14
Probability of n-digit factor? roger Factoring 3 2007-05-09 22:51
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
Probability of finding a factor in TF eepiccolo Math 4 2003-06-07 05:56
Probability of finding a factor in DC p-1 Deamiter Math 4 2002-12-25 06:06

All times are UTC. The time now is 11:25.

Sat Sep 26 11:25:39 UTC 2020 up 16 days, 8:36, 0 users, load averages: 1.14, 1.39, 1.39

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