mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2016-05-13, 17:52   #1
Trejack
 
Apr 2016

2·13 Posts
Post Possibility of a Fully-Factored 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 n-digit number. Thanks.
Trejack is offline   Reply With Quote
Old 2016-05-13, 19:00   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Cool

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. > 103000).

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).
Batalov is offline   Reply With Quote
Old 2016-05-13, 21:20   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

112B16 Posts
Default

Quote:
Originally Posted by Trejack View Post
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 n-digit number. Thanks.
How is it obvious that FF is more common?

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 PRP-ness 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 n-digit 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.
VBCurtis is offline   Reply With Quote
Old 2016-05-13, 22:24   #4
Trejack
 
Apr 2016

2·13 Posts
Default

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.
Trejack is offline   Reply With Quote
Old 2016-05-14, 03:29   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·5·293 Posts
Default

See https://en.wikipedia.org/wiki/Dickman_function, specifically the "Extension" toward the bottom.
VBCurtis is offline   Reply With Quote
Old 2016-05-14, 03:33   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by Trejack View Post
What is the chance that I will run into a number n that has ...
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 U-list? Are you using some method to select a string of decimal digits? Are you walking down the street with your eyes closed?
wblipp is online now   Reply With Quote
Old 2016-05-14, 04:03   #7
Trejack
 
Apr 2016

2×13 Posts
Default

Quote:
Originally Posted by wblipp View Post
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 U-list? Are you using some method to select a string of decimal digits? Are you walking down the street with your eyes closed?
In this range, I have 4 FF numbers and 1 PRP, and want to determine the chance of these FF status numbers, trial factored at the same limit (about 10M).


So in that case, it would be a (10M-Smooth number)*(A prime larger than 10M) that count toward FF numbers (or factordb's trial division limit).
Trejack is offline   Reply With Quote
Old 2016-05-14, 05:38   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

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 n-divided-by-its-largest-[prp?]prime-factor is b-smooth (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:
Originally Posted by Wikipedia
Friedlander defines a two-dimensional analog \(\sigma(u,v)\) of \(\rho(u)\).[9] This function is used to estimate a function \(\Psi(x,y,z)\) similar to de Bruijn's, but counting the number of y-smooth integers with at most one prime factor greater than z. Then\( \Psi(x,x^{1/a},x^{1/b})\sim x\sigma(b,a).\)
(Holy shit copying equations in Wikipedia puts the source LaTeX into your clipboard, that's so cool)

Last fiddled with by Dubslow on 2016-05-14 at 05:38
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne number factored (disbelievers are biting elbows) alpertron Data 529 2020-10-07 01:00
Largest Mersenne Number Fully Factored? c10ck3r Data 49 2017-12-10 19:39
Fully factored mattmill30 PrimeNet 23 2017-02-13 12:42
Exponent fully factored whilst only 74% known mattmill30 Factoring 3 2016-08-14 18:09
Estimating the number of primes in a partially-factored number CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46

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

Tue Oct 27 21:23:23 UTC 2020 up 47 days, 18:34, 2 users, load averages: 2.04, 1.80, 1.87

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.