Finding smooth numbers
Given a number n, how does one find the closest number that has all factors under a 1000? I can go and test each number, but is there a faster method?
What would be the running time of this faster algorithm? Is it in polynomial time? Thanks, Citrix 
You need to perform [URL="http://www.mersennewiki.org/index.php/Sieving"]sieving[/URL].

I don't think you need to sieve even.
Define P as the lowest number that contains all the factors under some number N Define X as the first number greater than your input number M that also contains all the factors under N. then X= (1+int(M/P))*P ("int" rounds down) Finding the closest to M (either below or above) would just require a couple more simple steps. It doesn't really matter what the factors of P are either. (i.e. prime factors from 2 to N, all integers from 2 to N). The same idea would hold. 
So now you have a single equation in two unknowns. You can define X in terms of M and P, you can define M in terms of X and P or you can define P in terms of X and M. What now?
This also assumes that X and P exist as separate numbers. From Citrix question it is not clear (to me at least) whether he meant all of [B]its[/B] factors < 1000, or all of [B]the[/B] factors < 1000. If he meant the latter then P might be > M, in which case X might = P. Nice idea though. 
What I meant was this consider n=100001 then the closest numbers with all factors below 1000 is 100000. Is there a method faster than sieving to find such numbers for any n?
Citrix 
If you really want the bsmooth number closest to n, I think you'll need to sieve. If you want a bsmooth number "somewhere nearby" n, you can cut a few corners, i.e. by only looking for smooth multiples of a smooth fixed value, similar to what grandpascorpion suggested.
Alex 
Oops, I misinterpreted your question earlier, Citrix.

No grandpascorpion, it is me that should apologise.
As Alex confirmed, you had the right idea. Whereas I was looking at your answer from my typically narrowminded algebraic perspective where a single equation in two unknowns has no solutions. I really should remember to shut my mouth when I don't know what I'm talking about. Sorry. 
Finding smooth numbers.
:smile:
Numbers: I really should remember to shut my mouth when I don't know what I'm talking about. Sorry./Unquote. Ha! ha! ha! ROTFL. You have finally admitted it old boy and that includes English also.:showoff: Please, as a New year resolution remember your own dictum in the other posts as well!! :yucky: Mally :coffee: 
Looks like Mally is completely losing it...
Alex 
All times are UTC. The time now is 05:43. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.