Smooth power trios

[Jens K Andersen]

Nice. "smoothtrio 32 0 4 0" takes 33s on my 1.33 Ghz Athlon which used 60s with my version.
I have attached your source compiled for P3 and for P4 with Windows.
I don't know whether the P4 version runs on Pentium M.

[grandpascorpion]

I tried both versions. They both finished in 23 seconds. I'm running a Pentium M 1.6Ghz with 512RAM, btw.

So, my process should speed up by a factor of (137/23*173/33)~30 between the change of machine and the optimizations. Veddy cool.

[grandpascorpion]

Originally Posted by Jens K Andersen

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.

Would you mean something like this pseudocode:

x=6;
c = 2^5*3^3*5^2*7*11*13*17*19*23*29*31*37*43;
mfs = 43*43;

k2=n+1
g = gcd(k2%c,c)
while (g > 1,
k2 /= g;
g = gcd(k2%c,c)
)

if (n < mfs && (n==1 || k2 < (n+1)^(1/x)) // need to find a cheap way to do this
print ("It's smooth")
else
print ("It's not") // continue factoring

c and mfs could be arrays with a few more elements. Do you think performing a gcd like this would be cheaper than just factoring the numbers?

[grandpascorpion]

x=6;
c = 2^5*3^3*5^2*7*11*13*17*19*23*29*31*37*43;
mfs = 43*43;

k2=n+1
g = gcd(k2%c,c)
while (g > 1,
k2 /= g;
g = gcd(k2%g,g)
)

if (n < mfs && (n==1 || k2 < (n+1)^(1/x)) // need to find a cheap way to do this
print ("It's smooth")
else
print ("It's not") // continue factoring

[Jens K Andersen]

I don't know how your suggestion would perform. I had something else in mind.
Some cpu's are much faster at 32-bit than 64-bit divisions.
The compiler can also have an influence.

Assume n is a 64-bit variable and r is 32-bit.
Option 1: Compute n%p for p=101,103,107,109, to see if any divide n.
Option 2: Compute r=n%(101*103*107*109). Then compute r%p for p=101,103,107,109.

Option 2 replaces 4 64-bit divisions with 1 64-bit and 4 32-bit.
It's twice as fast in my test on 1.33 GHz Athlon XP 1500+ compiled with
gcc version 3.2 (mingw special 20020817-1) (Maybe I should update gcc).
The attached speed test outputs:
381298 factors found in 4.21s with 4 64-bit divisions.
381298 factors found in 2.06s with 1 64-bit and 4 32-bit divisions.

Option 3: Compute r=n%(101*103) and look up in a precomputed array whether that r value means that 101 or 103 divides n. Then repeat with n%(107*109).
This only makes 2 divisions but adds memory lookups.
More primes (e.g. 101*103*107) at the same time would also be possible but then the cache ram would probably be missed most of the time.
I haven't timed this.

[grandpascorpion]

Thanks Jens. I'll have to try this.

In the meantime, after about 6.5 billion iterations, I found the following:

292716330021466875 = 3 ^ 12 x 5 ^ 4 x 29 x 167 x 283 x 643
292716330021466876 = 2 ^ 2 x 7 ^ 3 x 31 x 37 x 71 x 137 x 157 x 349 ^ 2
292716330021466877 = 17 x 19 x 179 x 197 x 311 x 331 x 421 x 593

log(292716330021466875)/log(643) =6.2198 so this also the strongest answer found so far.

The nice thing about this is that it's < 2^59. So, I can limit the checking to 59 bits (down from 62 bits). The values are generated are now 911-smooth instead of 1289-smooth. There's about 1/4 fewer possible primes in the generated values.

[Jens K Andersen]

3^12*5^4 means you have tested all numbers divisible by 3^13 and just started on 3^12.
So you have tested a little more than 3^13*k for odd k < 2^62/3^13 ~= 2^41.
2^59 is far larger than 2^41, so you have only done a tiny part of 2^59.
There are probably many far smaller solutions for x=6. If you want an exhaustive search for the smallest then I suggest a much lower limit than 2^59 which could take years. Maybe around 2^45 (just a wild guess).

[grandpascorpion]

I ran a check through 2^44 early on, but with no luck. Thanks.


I estimate that there's about 5 trillion cases to churn through. At the current clip, it should take about 2 years. LOL

[grandpascorpion]

Just to clarify: By cases, I mean odd 911-smooth numbers under 2^59.

[R. Gerbicz]

I've found a much better algorithm to generate smoothtrios.
By my new program after about only 90 minutes of computation
for smoothtrio 59 6, I've gotten:

105555555337666238=2*7*67*103*127*139*389^2*409
105555555337666239=3^11*13*17*41^2*79^2*257
105555555337666240=2^6*5*23*53*73*167*191*251*463

for this log(105555555337666240)/log(463)=6.3864 the
strongest known solution also.
This solution is the smallest known for x=6 case.

( It is a little interesting number: 7 consecutive 5's!,
2 consecutive 3's and 3 consecutive 6's (the beast 666)).

By the new program the classic smoothtrio 32 4 test takes
only 10 sec. on my computer! ( P4 Celereon 1.7 GHz ).

So now grandpa you can reduce your computation by my new program to
smoothtrio 57 6 , bound for primes=719, because this solution is <2^57.
It wouldn't take too much time, approx. only 1 month for an average
computer by my new program.

I've also added to print the number of smoothtrios at the end of the run.

The source is in smoothtrio.txt.
The next post will contain the program.

[R. Gerbicz]

So here it is the exe for Pentium4.