20110919, 19:03  #1 
Aug 2010
Kansas
547 Posts 
Theory Question
Hey, I was hoping RDS et al could hint me in on whether or not there are any formulas for this...
What are the chances that a randomly chosen integer n, with x digits, is factorable by a number less than p? More questions later! Thanks all! John Shuck 
20110919, 19:53  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}×3^{2}×281 Posts 
Quote:
Paul 

20110919, 23:09  #3 
Aug 2006
2·5·593 Posts 

20110919, 23:15  #4  
Nov 2003
2^{6}×113 Posts 
Quote:
and p = n^alpha ~ 10^((x1)alpha) then the answer is simply given by Dickman's function rho(alpha). A more accurate estimate can be done by integrating rho(alpha) as n varies over the entire set of x digit numbers. A less accurate estimate can be found via the CanfieldErdosPomerance thm. ~ u^u with u = log(n)/log(p) A good exposition of Dickman's function can be found in Knuth Vol 2. 

20110919, 23:18  #5  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 
Quote:
Will someone explain more about how Mertens' theorems are related to what is posted earlier? 

20110920, 06:58  #6  
Aug 2006
2·5·593 Posts 
Quote:
where is Euler's constant. * Chosen uniformly at random from 1..10^x for some large x. It turns out x doesn't matter unless it's small. Last fiddled with by CRGreathouse on 20110920 at 07:00 

20110920, 13:32  #7  
Nov 2003
16100_{8} Posts 
Quote:
[by the PNT or via estimates of the psi function; they are the same] The probability that some p divides the random integer is not independent of the probability that p1 (p != p1) divides the integer once there are sufficiently many primes, because unless your integer is greater than exp(y+o(1)), they ALL can't divide. They "get in the way" of each other. Which, BTW, is why we have no sieve method proof of PNT. Your expression is correct provided that y is small enough relative to the random integer such that all primes less than y can divide it. This difficulty is closely tied to the Fundamental Lemma of the Sieve [see e.g. Halberstam & Richert's "Sieve Methods"] and is also somewhat tied to the parity problem in sieve methods. Put another way, once there are sufficiently many primes in the product (i.e. y is big), the error terms in the sieve start to overtake the main terms. This discussion can get very technical in a hurry. I have only given a highlevel explanation. For more details the readers might like to read Tao's essay on the parity problem. [sorry, I don't have the URL handy] 

20110921, 01:08  #8 
Aug 2006
2×5×593 Posts 

20110921, 02:49  #9  
Nov 2003
2^{6}×113 Posts 
Quote:
this only allows e.g. y ~ 1150. I think most people would agree that a 500digit integer is large. Yet Mertens' Thm only applies if one asks about factors less than 1150. I can easily imagine asking: e.g. what is the probability that a 500digit number has a factor less than 10 digits. Mertens' Thm is much too weak to answer this. 

20110921, 03:21  #10  
Nov 2003
1110001000000_{2} Posts 
Quote:
factors to be less than p. This is clearly an incorrect assumption. If one wants just at least ONE factor, use the following: The probability that an integer n has a factor between x and x^(1+e), for x^(1+e) < sqrt(n) [i.e. we are asking about factors less than the sqrt(n)] is e/(e+1) 

20110921, 03:31  #11  
Nov 2003
16100_{8} Posts 
Quote:
to ask: what is the probability that there is no factor less than sqrt(n)? The answer is exp(gamma)/log(sqrt(n) = 2 exp(gamma)/log(n). 2 exp(gamma) is ~ 1.123. Yet the PNT says the answer should be 1/log(n). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime Gap Theory  robert44444uk  Prime Gap Searches  94  20201023 18:24 
Ask a number theory question  wreck  Math  4  20100415 07:11 
Theory  RichardB  Information & Answers  6  20100410 18:39 
The offended God theory  jasong  Soap Box  73  20070327 22:03 
Do I need group theory for this?  Orgasmic Troll  Math  1  20050121 12:50 