20060322, 15:47  #1 
Jan 2005
Transdniestr
503_{10} Posts 
Smooth power trios
The special smooth numbers thread got me curious about smooth trios:
Find a trio of numbers: n, n1 and n2 such that they are all f(x,n)smooth where f(x,n) is defined as the maximum prime p <= floor((n2)^(1/x)). In other words, the lowest of the three,n2 would have to be >= p^x and all three numbers would have to be psmooth. For x=2, the minimum answer is n=352. Sqrt(350)=18.71 so the numbers would have to be 17smooth (In fact, they are 13smooth). For x=3, the minimum n=134850. To satisfy the relation, all three numbers must be 47smooth (In fact, they are 43smooth). For x=4, the minimum n=116026275. To satisfy the relation, all three numbers must be 103smooth (In fact, they are 101smooth). 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,n1, and n2 are all psmooth. I found one higher x=4 solution: n=196512877 (The trio are 113smooth 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 20060322 at 15:53 
20060322, 18:34  #2 
"Robert Gerbicz"
Oct 2005
Hungary
1442_{10} Posts 
For x=5 the smallest solution is n=138982583000, the factorizations:
n=2^3*5^3*23^2*59*61*73 n1=13*31*37*43^2*71^2 n2=2*3^6*7*29*47*97*103 
20060322, 18:48  #3 
Jan 2005
Transdniestr
503_{10} Posts 
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 20060322 at 18:48 
20060322, 19:50  #4  
"Robert Gerbicz"
Oct 2005
Hungary
10110100010_{2} Posts 
Quote:


20060323, 02:41  #5 
Jan 2005
Transdniestr
111110111_{2} Posts 
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. 
20060323, 06:12  #6  
"Robert Gerbicz"
Oct 2005
Hungary
2×7×103 Posts 
Quote:


20060706, 14:29  #7 
Jan 2005
Transdniestr
503 Posts 
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. 
20060801, 14:41  #8 
Jan 2005
Transdniestr
767_{8} Posts 
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 20060801 at 14:43 
20060802, 00:39  #9  
Feb 2006
Denmark
2·5·23 Posts 
Quote:
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 m1 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 m1. I made the modifications in smoothtriojka.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 non0 remainder indicates a factor, but this would take a little more to implement. 

20060802, 16:01  #10 
Jan 2005
Transdniestr
767_{8} Posts 
Thanks, great idea.
You raised an interesting question. 1 out of 3 perhaps. Is there a heuristic for finding the ratio of odd psmooth to even psmooth numbers < some n. 
20060802, 21:06  #11 
Jan 2005
Transdniestr
767_{8} Posts 
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. Last fiddled with by grandpascorpion on 20060802 at 21:12 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Remove the Smooth 2012  c10ck3r  Math  12  20120918 12:38 
Smooth Numbers  Yamato  Math  1  20051211 11:09 
NFS and smooth norm MOD N ?  bonju  Factoring  9  20050826 13:29 
Smooth?  Xyzzy  Factoring  5  20041104 18:20 