Smooth and rough numbers

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

[flouran]

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 -smooth numbers is .

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

[wblipp]

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

[CRGreathouse]

Amusingly, not only did I write the article William linked to, I wrote a program (Pari/gp) to calculate these numbers:

\\ 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.");