mersenneforum.org > Math Smooth and rough numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-25, 02:03 #1 CRGreathouse     Aug 2006 3×1,987 Posts Smooth and rough numbers It's well-known that the density of sqrt(n)-rough numbers is log 2. What are the densities of nα-smooth numbers? Definition: n is m-rough 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 2009-05-25 at 02:03
2009-05-25, 02:36   #2
flouran

Dec 2008

72×17 Posts

Quote:
 Originally Posted by CRGreathouse It's well-known that the density of sqrt(n)-rough numbers is log 2. What are the densities of nα-smooth numbers? Definition: n is m-rough 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.
I am willing to wager a guess here. Perhaps the density of $n^{\alpha}$-smooth numbers is $-\log({\alpha})$.

But, I am not sure as I have never looked into smooth numbers too deeply (nor cared to).

Last fiddled with by flouran on 2009-05-25 at 02:56

2009-05-25, 04:48   #3
wblipp

"William"
May 2003
New Haven

93816 Posts

Quote:
 Originally Posted by CRGreathouse What are the densities of nα-smooth numbers? ... If it helps, I'm interested in the range 1/3 ≤ α < 1/2.
http://en.wikipedia.org/wiki/Dickman-de_Bruijn_function

The section headed "Computation" has the closed form solution for your range of interest.

William

 2009-05-25, 05:26 #4 CRGreathouse     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.068528194e-1, 4.860838829e-2, 4.910925648e-3, 3.547247005e-4, 1.964969635e-5, 8.745669953e-7, 3.232069304e-8, 1.016248283e-9, 2.770171838e-11, 6.644809070e-13, 1.419713165e-14, 2.729189030e-16, 4.760639989e-18, 7.589908004e-20]; 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.");

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 5 2012-11-10 07:54 Citrix Other Mathematical Topics 46 2012-03-06 14:55 flouran Math 12 2009-12-25 16:41 Citrix Math 9 2005-12-31 11:07 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 16:38.

Fri Jan 22 16:38:13 UTC 2021 up 50 days, 12:49, 0 users, load averages: 1.68, 1.94, 1.98