-   Math (
-   -   Finding smooth numbers (

Citrix 2005-12-29 21:32

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?


alpertron 2005-12-29 21:35

You need to perform [URL=""]sieving[/URL].

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 [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.

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?


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.


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

Finding smooth 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:

akruppa 2005-12-31 11:07

Looks like Mally is completely losing it...


All times are UTC. The time now is 05:43.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.