Finding smooth numbers

Citrix · 2005-12-29, 21:32

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

alpertron · 2005-12-29, 21:35

You need to perform sieving.

grandpascorpion · 2005-12-29, 21:59

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.

Numbers · 2005-12-29, 22:21

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.

Citrix · 2005-12-29, 22:32

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

akruppa · 2005-12-29, 22:39

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

grandpascorpion · 2005-12-30, 14:38

Oops, I misinterpreted your question earlier, Citrix.

Numbers · 2005-12-31, 09:37

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.

mfgoode · 2005-12-31, 11:02

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

akruppa · 2005-12-31, 11:07

Looks like Mally is completely losing it...

Alex

2005-12-29, 21:32	#1
Citrix 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

2005-12-29, 21:59	#3
grandpascorpion Jan 2005 Transdniestr 767₈ 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-31, 11:02	#9
mfgoode Bronze Medalist Jan 2004 Mumbai,India 804₁₆ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Not smooth enough numbers	Sam Kennedy	Factoring	5	2012-11-10 07:54
Finding a smooth integer in a given residue class	Alexander	Math	32	2012-05-09 13:09
Quad Sieve - Finding B-Smooth Bound	blackbriar	Factoring	3	2011-12-28 14:31
Distribution of Smooth Numbers	flouran	Math	12	2009-12-25 16:41
Smooth Numbers	Yamato	Math	1	2005-12-11 11:09

2005-12-29, 21:35	#2
alpertron Aug 2002 Buenos Aires, Argentina 17·79 Posts	You need to perform sieving.

2005-12-29, 22:21	#4
Numbers Jun 2005 Near Beetlegeuse 2²×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 62B₁₆ 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 2,467 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 767₈ Posts	Oops, I misinterpreted your question earlier, Citrix.

2005-12-31, 09:37	#8
Numbers Jun 2005 Near Beetlegeuse 604₈ 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:07	#10
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Looks like Mally is completely losing it... Alex