20090525, 02:03  #1 
Aug 2006
3×1,987 Posts 
Smooth and rough numbers
It's wellknown that the density of sqrt(n)rough numbers is log 2. What are the densities of n^{α}smooth numbers?
Definition: n is mrough if there is a prime greater than m that divides n. If it helps, I'm interested in the range 1/3 ≤ α < 1/2. Answers, hints, and references to websites, papers, or books would be appreciated. Related to Sloane's A064052 and A063538. Last fiddled with by CRGreathouse on 20090525 at 02:03 
20090525, 02:36  #2  
Dec 2008
7^{2}×17 Posts 
Quote:
But, I am not sure as I have never looked into smooth numbers too deeply (nor cared to). Last fiddled with by flouran on 20090525 at 02:56 

20090525, 04:48  #3  
"William"
May 2003
New Haven
938_{16} Posts 
Quote:
The section headed "Computation" has the closed form solution for your range of interest. William 

20090525, 05:26  #4 
Aug 2006
3·1,987 Posts 
Amusingly, not only did I write the article William linked to, I wrote a program (Pari/gp) to calculate these numbers:
Code:
\\ Helper function for rhoest. Finds a xi such that e^xi  1 = x * xi. deBruijnXi(x)={ local(left, right, m); if (x < 1, error ("deBruijnXi: Can't find a xi given x < 1.")); if (x > 1, left = log(x), left = eps()); right = 1.35 * log(x) + 1; \\ Heuristic \\Bisection while (right  left > left * eps(), m = (left + right) / 2; if (exp(m)  1 > x * m, right = m, left = m) ); (left + right) / 2 }; rhoest(x)={ my(xi = deBruijnXi(x)); \\exp(Euler) / sqrt(2 * Pi * x) * exp(1  exp(xi) + intnum(s = eps(), xi, (exp(s)  1) / s)) exp(eint1(xi)  x * xi) / sqrt(2 * Pi * x) / xi }; addhelp(rhoest, "de Bruijn's asymptotic approximation for rho(x), rewritten as in van de Lune and Wattel 1969. Curiously, their paper shows values for this estimate that differ from those calculated by this function, often as soon as the second decimal place  but as the difference is in the direction of the true value, I have not looked further into this."); rhoTable = [1, 3.068528194e1, 4.860838829e2, 4.910925648e3, 3.547247005e4, 1.964969635e5, 8.745669953e7, 3.232069304e8, 1.016248283e9, 2.770171838e11, 6.644809070e13, 1.419713165e14, 2.729189030e16, 4.760639989e18, 7.589908004e20]; DickmanRho(x)={ local(left, right, scale); if (x <= 2, return (1  log(max(x, 1)))); if (x <= 3, return( 1  (1  log(x  1))*log(x) + real(dilog(1  x)) + Pi^2 / 12 )); \\ Asymptotic estimate (scaled for continuity) if (x > #rhoTable, scale = rhoTable[#rhoTable] / rhoest(#rhoTable); \\ Let the scale factor dwindle away, since the estimate is (presumably) \\ better in the long run than any scaled version of it. The exponent \\ of 0.25 has been chosen to give the best results for 10 < x < 100 \\ with a table size of 10. scale = (scale  1) * (#rhoTable / x)^.25 + 1; return (precision(rhoest(x) * scale, 9)) ); \\ Scaling factors: the factor by which the true value of rho differs from \\ the estimates at the endpoints. left = rhoTable[floor(x)] / rhoest(floor(x)); right = rhoTable[ceil(x)] / rhoest(ceil(x)); \\ Linear interpolation on the scale factors. scale = left + (right  left) * (x  floor(x)); \\ Return a result based on the scale factor and the asymptotic formula. precision(rhoest(x) * scale, 9) }; addhelp(DickmanRho, "Estimates the value of the Dickman rho function. For x <= 3 the exact values are used, up to rounding; up to "#rhoTable" the value is interpolated using known values and rhoest; after "#rhoTable" rhoest is used, along with a correction factor based on the last value in rhoTable."); 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Special Smooth numbers  Citrix  Other Mathematical Topics  46  20120306 14:55 
Distribution of Smooth Numbers  flouran  Math  12  20091225 16:41 
Finding smooth numbers  Citrix  Math  9  20051231 11:07 
Smooth Numbers  Yamato  Math  1  20051211 11:09 