20160513, 17:52  #1 
8,353 Posts 
Possibility of a FullyFactored Number
Hi, does anyone know the approximate chance that I will run into a number, either P, PRP, or FF? I know the chance of a PRP is 1/(log n), but what about an FF status?
It is obvious that the FF status is more common than the PRP or P status, but there are still undefined gaps with FF status and I do not know what to expect for an ndigit number. Thanks. 
20160513, 19:00  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3×5×17×19 Posts 
Forget about approximate! It is very easy to give you a precise answer! It's 0.000...% for P, for PRP, for FF,  with a thousand zeroes after dot for any reasonable size (e.g. > 10^{3000}).
If you enter a large enough number, the probability for all of these will be ~0%, and the ~100% share will be used by 'U' (Unknown). If you expected that FactorDB knows everything about every number  think again! If FactorDB could talk, it would have repeated after Socrates: "I know one thing: that I know nothing" (relatively speaking). 
20160513, 21:20  #3  
"Curtis"
Feb 2005
Riverside, CA
3^{3}×191 Posts 
Quote:
When you say "expect", what is it you are doing to get a result? Do you mean "when I run a primality test on a number not in FactorDB", or "when I type a number into FactorDB to see what someone else has already done", or something else? You cited 1/log(n) for a PRP. Again, what specific process to determine PRPness are you referring to? Note Batalov answered your question for "if I ask FactorDB about a random number", but I'm not sure that's what you meant. Also, note that when you pose a mathematical question about "an ndigit number", mathy folks will assume you mean "what is the behavior of this thing I care about as n gets large?", or that you're looking for a formula as a function of n (as you cited for PRP). It seems pretty obvious you're not asking for a formula for "how often are numbers in the database already fully factored by other humans?", since that would make no sense to even ask. So, Batalov gave you the answer to the other interpretation, asymptotic behavior as n gets large. 

20160513, 22:24  #4 
2^{2}·5·211 Posts 
Yes, VBCurtis, let me try to say this instead:
What is the chance that I will run into a number n that has only one prime factor larger than x? If the factoring limit = 100, then in this case: 5084330323469388575978983438081543922 = (2*13*71*2754241778694143323932277052048507) would be Fully factored (FF), however 5084330323469388575978983438081543923 = (3^2*5081*14735093*796754809*9470316193971551) would be a (CF) status. (Notice I bold the factors greater that the limit x, and what I intended was to only bold one of these factors, then by definition is Fully Factored in that sense.) I am only looking for numbers the FactorDB fully factors when tested, not factors reported by other humans. 
20160514, 03:29  #5 
"Curtis"
Feb 2005
Riverside, CA
3^{3}·191 Posts 
See https://en.wikipedia.org/wiki/Dickman_function, specifically the "Extension" toward the bottom.

20160514, 03:33  #6 
"William"
May 2003
New Haven
23×103 Posts 
I don't understand the question. What are you doing to "run into a number?" Are you using some method to select from the factordb Ulist? Are you using some method to select a string of decimal digits? Are you walking down the street with your eyes closed?

20160514, 04:03  #7  
2·5^{2}·71 Posts 
Quote:
So in that case, it would be a (10MSmooth number)*(A prime larger than 10M) that count toward FF numbers (or factordb's trial division limit). 

20160514, 05:38  #8  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
I think OP is asking this:
Define the (approximate) bound to which FDB can find small factors as b. For this purposes of this discussion, PRPs are treated as if they were proven prime. For a random number n >> b, what are the odds that ndividedbyitslargest[prp?]primefactor is bsmooth (which is the necessary and sufficient condition for n to be declared FF by the FDB)? And the answer is indeed found in post #5 of this thread by VBCurtis: Quote:
Last fiddled with by Dubslow on 20160514 at 05:38 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne number factored (disbelievers are biting elbows)  alpertron  Data  576  20211107 02:22 
Largest Mersenne Number Fully Factored?  c10ck3r  Data  49  20171210 19:39 
Fully factored  mattmill30  PrimeNet  23  20170213 12:42 
Exponent fully factored whilst only 74% known  mattmill30  Factoring  3  20160814 18:09 
Estimating the number of primes in a partiallyfactored number  CRGreathouse  Probability & Probabilistic Number Theory  15  20140813 18:46 