mersenneforum.org > Math Finding smooth numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2005-12-29, 21:32 #1 Citrix     Jun 2003 110001010112 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
 2005-12-29, 21:35 #2 alpertron     Aug 2002 Buenos Aires, Argentina 25048 Posts You need to perform sieving.
 2005-12-29, 21:59 #3 grandpascorpion     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 2005-12-29 at 22:03
 2005-12-29, 22:21 #4 Numbers     Jun 2005 Near Beetlegeuse 22·97 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.
 2005-12-29, 22:32 #5 Citrix     Jun 2003 157910 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
 2005-12-29, 22:39 #6 akruppa     "Nancy" Aug 2002 Alexandria 9A316 Posts If you really want the b-smooth number closest to n, I think you'll need to sieve. If you want a b-smooth 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
 2005-12-30, 14:38 #7 grandpascorpion     Jan 2005 Transdniestr 503 Posts Oops, I misinterpreted your question earlier, Citrix.
 2005-12-31, 09:37 #8 Numbers     Jun 2005 Near Beetlegeuse 38810 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 narrow-minded 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.
 2005-12-31, 11:02 #9 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 22·33·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
 2005-12-31, 11:07 #10 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Looks like Mally is completely losing it... Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 5 2012-11-10 07:54 Alexander Math 32 2012-05-09 13:09 blackbriar Factoring 3 2011-12-28 14:31 flouran Math 12 2009-12-25 16:41 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 02:37.

Thu Apr 22 02:37:38 UTC 2021 up 13 days, 21:18, 0 users, load averages: 2.18, 2.27, 2.35