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.

[Batalov]

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³⁰⁰⁰).

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

[VBCurtis]

Originally Posted by Trejack

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.

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.

[VBCurtis]

See https://en.wikipedia.org/wiki/Dickman_function, specifically the "Extension" toward the bottom.

[wblipp]

Originally Posted by Trejack

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?

Originally Posted by wblipp

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

[Dubslow]

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:

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)