mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-12-29, 21:32   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

157610 Posts
Default 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
Citrix is offline   Reply With Quote
Old 2005-12-29, 21:35   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24728 Posts
Default

You need to perform sieving.
alpertron is offline   Reply With Quote
Old 2005-12-29, 21:59   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1F716 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2005-12-29, 22:21   #4
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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.
Numbers is offline   Reply With Quote
Old 2005-12-29, 22:32   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

23×197 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-12-29, 22:39   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-12-30, 14:38   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Oops, I misinterpreted your question earlier, Citrix.
grandpascorpion is offline   Reply With Quote
Old 2005-12-31, 09:37   #8
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

1100001002 Posts
Default

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.
Numbers is offline   Reply With Quote
Old 2005-12-31, 11:02   #9
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Thumbs down 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
mfgoode is offline   Reply With Quote
Old 2005-12-31, 11:07   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Looks like Mally is completely losing it...

Alex
akruppa is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 17:57.

Sat Dec 5 17:57:21 UTC 2020 up 2 days, 14:08, 0 users, load averages: 2.68, 2.59, 2.33

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.