mersenneforum.org Possibility of a Fully-Factored Number
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-13, 17:52 #1 Trejack   2·3·5·257 Posts 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.
 2016-05-13, 19:00 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×3×1,657 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. > 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).
2016-05-13, 21:20   #3
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

172·19 Posts

Quote:
 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.

 2016-05-13, 22:24 #4 Trejack   163218 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.
 2016-05-14, 03:29 #5 VBCurtis     "Curtis" Feb 2005 Riverside, CA 125638 Posts See https://en.wikipedia.org/wiki/Dickman_function, specifically the "Extension" toward the bottom.
2016-05-14, 03:33   #6
wblipp

"William"
May 2003
New Haven

45058 Posts

Quote:
 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?

2016-05-14, 04:03   #7
Trejack

23×3×103 Posts

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

2016-05-14, 05:38   #8
Dubslow

"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 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

 Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Data 589 2022-07-03 19:04 c10ck3r Data 49 2017-12-10 19:39 mattmill30 PrimeNet 23 2017-02-13 12:42 mattmill30 Factoring 3 2016-08-14 18:09 CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46

All times are UTC. The time now is 19:03.

Wed Oct 5 19:03:13 UTC 2022 up 48 days, 16:31, 0 users, load averages: 0.97, 1.17, 1.20

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔