mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-03-22, 15:47   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

50310 Posts
Default Smooth power trios

The special smooth numbers thread got me curious about smooth trios:

Find a trio of numbers: n, n-1 and n-2 such that they are all
f(x,n)-smooth where f(x,n) is defined as the maximum prime p <= floor((n-2)^(1/x)). In other words, the lowest of the three,n-2 would have to be >= p^x and all three numbers would have to be p-smooth.

For x=2, the minimum answer is n=352. Sqrt(350)=18.71 so the numbers would have to be 17-smooth (In fact, they are 13-smooth).

For x=3, the minimum n=134850. To satisfy the relation, all three numbers must be 47-smooth (In fact, they are 43-smooth).

For x=4, the minimum n=116026275. To satisfy the relation, all three numbers must be 103-smooth (In fact, they are 101-smooth).

Can anyone extend this sequence? I have done a search through 300 million.
Could anyone have insight into an upper bound for x?

A corollary would be to maximize log(n)/log(p) where n,n-1, and n-2 are all p-smooth. I found one higher x=4 solution: n=196512877 (The trio are 113-smooth and this happens to have a higher log(n)/log(p)=4.0395 than the minimum solution above. Of course finding a solution for a higher x would bump up the max log(n)/log(p) found > x.

Thanks for reading,
Grandpa

Last fiddled with by grandpascorpion on 2006-03-22 at 15:53
grandpascorpion is offline   Reply With Quote
Old 2006-03-22, 18:34   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

144210 Posts
Default

For x=5 the smallest solution is n=138982583000, the factorizations:
n=2^3*5^3*23^2*59*61*73
n-1=13*31*37*43^2*71^2
n-2=2*3^6*7*29*47*97*103
R. Gerbicz is offline   Reply With Quote
Old 2006-03-22, 18:48   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

50310 Posts
Default

Cool, did you use a variation of your code from the other thread? If you have a Windows exe, I'd gladly run the program to try to extend the sequence.

BTW, for that result, log(n)/log(p)=5.5536

Last fiddled with by grandpascorpion on 2006-03-22 at 18:48
grandpascorpion is offline   Reply With Quote
Old 2006-03-22, 19:50   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101000102 Posts
Default

Quote:
Originally Posted by grandpascorpion
Cool, did you use a variation of your code from the other thread? If you have a Windows exe, I'd gladly run the program to try to extend the sequence.

BTW, for that result, log(n)/log(p)=5.5536
Yes here it is an exe for windows. Note that to use it type smoothtrio d x If you want to determine all smoothtrio up to 2^d for x value.
Attached Files
File Type: exe smoothtrio.exe (32.2 KB, 120 views)
R. Gerbicz is offline   Reply With Quote
Old 2006-03-23, 02:41   #5
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

Thanks R. This is great. If possible, could you post the source? I'd like to make a couple of changes: a start bit parameter and a parameter/logic to search for more than 3 consecutive numbers.

I'm searching through n=2^53 for x=6 now.
grandpascorpion is offline   Reply With Quote
Old 2006-03-23, 06:12   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×7×103 Posts
Default

Quote:
Originally Posted by grandpascorpion
Thanks R. This is great. If possible, could you post the source? I'd like to make a couple of changes: a start bit parameter and a parameter/logic to search for more than 3 consecutive numbers.

I'm searching through n=2^53 for x=6 now.
OK see the attachment for the source.
Attached Files
File Type: txt smoothtrio.txt (10.6 KB, 201 views)
R. Gerbicz is offline   Reply With Quote
Old 2006-07-06, 14:29   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default First solution for x=6 found

3864470338872410112 = 2 ^ 17 x 3 ^ 2 x 17 x 19 x 23 x 97 x 109 x 179 x 233
3864470338872410113 = 7 x 11 ^ 2 x 83 x 157 x 587 x 613 x 887 x 1097
3864470338872410114 = 2 x 37 x 89 x 421 x 947 x 1109 x 1151 x 1153

log(3864470338872410114)/log(1153)=6.0706

The cutoff prime for a number of this size is 1249 defined as
the largest prime < floor(3864470338872410112^(1/6)) .

This was found between the 666 and 667 x 10^8th iterations on a slightly modified version of R.'s program set to search through 2^62. On the Sparc Ultra 5 machine I'm running this on, it checks about 100 million every two hours (a little less than 14000 cases per second). So, this took almost 2 months computing time to find.
grandpascorpion is offline   Reply With Quote
Old 2006-08-01, 14:41   #8
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

7678 Posts
Default 2nd Smaller solution found for x=6

3470704837171937280 = 2 ^ 16 x 3 ^ 3 x 5 x 23 x 109 x 367 x 593 x 719
3470704837171937281 = 7 x 61 x 71 x 167 x 701 x 839 x 977 x 1193
3470704837171937282 = 2 x 19 ^ 2 x 37 x 59 x 73 x 211 x 409 x 431 x 811

log(3470704837171937281)/log(1193)=6.0262 . So, it's smaller than the one above but not as "strong" (6.0706 > 6.0262).

Last fiddled with by grandpascorpion on 2006-08-01 at 14:43
grandpascorpion is offline   Reply With Quote
Old 2006-08-02, 00:39   #9
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2·5·23 Posts
Default

Quote:
Originally Posted by grandpascorpion
3470704837171937280 = 2 ^ 16 x 3 ^ 3 x 5 x 23 x 109 x 367 x 593 x 719
Only trios (m, m+1, m+2) with m divisible by 2^16 have been tested so far.
Exhaustive searching below 2^62 would take ages.
I looked at Gerbicz' smoothtrio.txt. It uses this order to search trios:

Generate all smooth m by multiplying small primes.
For each m, trial factor m+1 to see whether it's smooth.
If m+1 is smooth then trial factor m+2 to see whether it's smooth.

I suggest this:

Generate all odd smooth m by multiplying small odd primes.
For each m, trial factor m+1 to see whether it's smooth.
If m+1 is smooth then trial factor m+2 and m-1 to see if one of them is smooth.

Less than half of all smooth numbers are odd, so this is more than twice as fast.
m+1 is rarely smooth so it doesn't slow down to test m-1.
I made the modifications in smoothtrio-jka.txt.
"smoothtrio 32 4" is reduced from 173s to 60s on my Athlon. It found the same 65 trios in different order.
There are also ways to optimize trial factoring, e.g. by dividing with a product of two or more small primes and see whether a non-0 remainder indicates a factor, but this would take a little more to implement.
Attached Files
File Type: txt smoothtrio-jka.txt (11.2 KB, 144 views)
Jens K Andersen is offline   Reply With Quote
Old 2006-08-02, 16:01   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

7678 Posts
Default

Thanks, great idea.

You raised an interesting question. 1 out of 3 perhaps. Is there a heuristic for finding the ratio of odd p-smooth to even p-smooth numbers < some n.
grandpascorpion is offline   Reply With Quote
Old 2006-08-02, 21:06   #11
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

7678 Posts
Default Sparc woes / Updated version / Favor to ask

I tried running this code with these options (32 4) on the same Sparc as above and it took a whopping 258 seconds! Lordy.

I had made some enhancements earlier to the code which limit the factoring range as well as adding a couple of parameters.

smoothtrio <high bit> <low bit> <exponent> <starting point>

Starting point of n means to start factoring at the n*10^9th iteration (in case you have to restart the script and want to save time). It still has to cycle through the iterations but it's about 50 times faster than factoring.

I found a good optimization and knocked the time down to 137 seconds, coupled with these new options. At each point, you can check if n > f ^x where f is the high factor prime[pos]. If not, skip to the next smooth number.

Could anyone do me a big favor and compile my code for Windows? I'll be running this on a Pentium M if that matters.
Attached Files
File Type: txt smoothtrio.txt (13.2 KB, 130 views)

Last fiddled with by grandpascorpion on 2006-08-02 at 21:12
grandpascorpion 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
Remove the Smooth 2012 c10ck3r Math 12 2012-09-18 12:38
Smooth Numbers Yamato Math 1 2005-12-11 11:09
NFS and smooth norm MOD N ? bonju Factoring 9 2005-08-26 13:29
Smooth? Xyzzy Factoring 5 2004-11-04 18:20

All times are UTC. The time now is 13:48.

Tue Mar 2 13:48:54 UTC 2021 up 89 days, 10 hrs, 0 users, load averages: 2.55, 2.33, 2.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.