View Single Post
Old 2021-11-06, 15:54   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7·223 Posts
Default

Quote:
Originally Posted by axn View Post
Does this look right?
I'm not sure what your code is doing, anyway, for a fixed B bound and e>1, solve the
x*log(x)/e=B*log(B)
equation, say binary search is fine since x*log(x) is monotone increasing (on [exp(-1),inf) interval ).
And put all q^e (for q prime) to the smooth set, where q is in the [B,U] interval, and U is the solution of the above equation.

You could argue that smooth number's factors is not that random, and that is true, say more than half of them is even.
So ran some tests, that is in some way deeper and at once lighter.

General method let the antique pm1 way, and the improved is the improved.
Since we want a comparison we have to adjust the B limit, lowering that in such a way that the exponent will be smaller, but we find more smooth numbers.

Let B=1000, but for simplicity we use the same U bound for all e>1, the algorithm will include 1024,1331,1369,1681 [these are 2^10, 11^3, 37^2, 41^2] and exclude 991 and 997.
Here 2*11*37*41<991*997 gives that the exponent is smaller what used in the general method.
In the [1e13,2e13] interval with a simple backtracking it is possible to find all smooth numbers (for these 2 methods)
The general method found 12988813875 smooth numbers.
The improved found 13058081975 smooth numbers, so slightly more.

You could say that the included 2^10 was the booster, so repeat the search for B=1024 (here B is included in the set), the method will include 1331,1369,1681,1849 [these are 11^3, 37^2, 41^2, 43^2] and exclude 1019 and 1021. [Notice that in this case, basically 1024 would be also dropped out due to the smaller B limit, but ofcourse the improved method would pick up it, in other words: you would drop out some non-primes also, but all of those will reappear in the set.]
Again 11*37*41*43<1019*1021, so the exponent is smaller.
The general method found 13691324851 smooth numbers.
The improved found 13809957083 smooth numbers, slightly more.

In both cases we got a roughly ~0.5% gain over the general method using primepowers out of order. [the gain is smaller for larger B !]

ps. you could still say that this is not a fair test, because p-1 is even for p>2, so it won't be a random smooth number. But it is proven that for any M the p mod M is equally distributed in the mod M reduced residue classes.

Last fiddled with by R. Gerbicz on 2021-11-06 at 16:15
R. Gerbicz is offline   Reply With Quote