Smooth power trios

[grandpascorpion]

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

[R. Gerbicz]

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

[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

[R. Gerbicz]

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.

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

[R. Gerbicz]

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.

[grandpascorpion]

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]

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

[Jens K Andersen]

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.

[grandpascorpion]

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]

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.