mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-05-25, 02:03   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×29×103 Posts
Default 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
CRGreathouse is offline   Reply With Quote
Old 2009-05-25, 02:36   #2
flouran
 
flouran's Avatar
 
Dec 2008

11010000012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
flouran is offline   Reply With Quote
Old 2009-05-25, 04:48   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
wblipp is offline   Reply With Quote
Old 2009-05-25, 05:26   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·29·103 Posts
Default

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.");
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 06:40.

Thu Mar 4 06:40:51 UTC 2021 up 91 days, 2:52, 1 user, load averages: 3.36, 3.00, 2.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.