20051229, 21:32  #1 
Jun 2003
1,579 Posts 
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 
20051229, 21:59  #3 
Jan 2005
Transdniestr
503 Posts 
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. Last fiddled with by grandpascorpion on 20051229 at 22:03 
20051229, 22:21  #4 
Jun 2005
Near Beetlegeuse
604_{8} Posts 
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 its factors < 1000, or all of the factors < 1000. If he meant the latter then P might be > M, in which case X might = P. Nice idea though. 
20051229, 22:32  #5 
Jun 2003
1,579 Posts 
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 
20051229, 22:39  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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 
20051230, 14:38  #7 
Jan 2005
Transdniestr
503 Posts 
Oops, I misinterpreted your question earlier, Citrix.

20051231, 09:37  #8 
Jun 2005
Near Beetlegeuse
604_{8} Posts 
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. 
20051231, 11:02  #9 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}×3^{3}×19 Posts 
Finding smooth numbers.
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. Please, as a New year resolution remember your own dictum in the other posts as well!! Mally 
20051231, 11:07  #10 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Looks like Mally is completely losing it...
Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Finding a smooth integer in a given residue class  Alexander  Math  32  20120509 13:09 
Quad Sieve  Finding BSmooth Bound  blackbriar  Factoring  3  20111228 14:31 
Distribution of Smooth Numbers  flouran  Math  12  20091225 16:41 
Smooth Numbers  Yamato  Math  1  20051211 11:09 