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

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

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

[QUOTE=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[/QUOTE]

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.

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.

[QUOTE=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.[/QUOTE]

OK see the attachment for the source.

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.

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

[QUOTE=grandpascorpion]3470704837171937280 = 2 ^ 16 x 3 ^ 3 x 5 x 23 x 109 x 367 x 593 x 719 [/QUOTE]
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.

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.

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.

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.

Much appreciated
 

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. :smile:

[QUOTE=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.[/QUOTE]

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?

An improvement ...
 

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;
[B][I]g = gcd(k2%g,g)[/I][/B]
)

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

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.

New low solution found for x=6
 

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.

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

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

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

new record smoothtrio for x=6
 

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.

So here it is the exe for Pentium4.

That's great R. Coincedentally, I also found this answer yesterday (with the old program). Thanks ao much for your help with this idea. It was about 1.5 billion iterations into checking 59 6.

new record smoothtrio for x=6
 

At night running my smoothtrio program I've gotten:

17539913103192530=2*5*23*37*53*61*71*89*233*433
17539913103192531=3^6*17*149*223*277*367*419
17539913103192532=2^2*13^2*41*79*167*313*331*463

this is the smallest known smoothtrio for x=6
log(17539913103192532)/log(463)=6.09399 so this time not the strongest
solution.

So now grandpa you can reduce your computation to smoothtrio 54 6,
bound for primes=509 because this solution is <2^54. Now the expected
running time is only about 4 days!

Great stuff!

Hi !
with a limit of 62 bits for d, the x=7 case has very little chance to succeed.
Is it a way to increase the d bound over 62 bits without having to rewrite all the program or loosing all the speed benefits?
Thanks.

New low solution found 3283630023973833,2,1. Running R's script now for 52 6

[QUOTE=grandpascorpion]New low solution found 3283630023973833,2,1. Running R's script now for 52 6[/QUOTE]
Congratulations. ( I've stopped my program yesterday )
Here it is the factorizations:
3283630023973831=7^4*29*67*83*103*281*293
3283630023973832=2^3*13*19*43*59*97*107*223*283
3283630023973833=3^2*23*73*79*127*229*271*349

This is the smallest known solution for x=6.
The strength=log(3283630023973833)/log(349)=6.1020 ( not the strongest )

[QUOTE=Phil Mjx]Hi !
with a limit of 62 bits for d, the x=7 case has very little chance to succeed.
Is it a way to increase the d bound over 62 bits without having to rewrite all the program or loosing all the speed benefits?
Thanks.[/QUOTE]
It wouldn't be much slower, perhaps by a factor of two. I don't think that we have got a very little chance by smoothtrio 62 7. It would take less than 3 month for my computer.

Finito! for x=6
 

The lowest answer is:
1348770149848002 = 2 x 3 x 7 x 23 x 41 x 61 ^ 2 x 149 x 239 x 257
1348770149848001 = 19 ^ 3 x 89 x 103 x 229 x 283 x 331
1348770149848000 = 2 ^ 6 x 5 ^ 3 x 11 x 29 x 109 x 151 x 163 x 197

log(1348770149848002)/log(2) = 50.26
log(1348770149848001)/log(331)=6.004353 (just barely a solution)

That was a great work, garndpa!

If we use the strength of n is log(n)/log(q), where q is the largest prime factor of n. Then the smallest smoothtrio for x=2 is the following:
48=2^4*3
49=7^2
50=2*5^2
And the strength=log(49)/log(7)=2.
Grandpa this isn't an error in your first post, because you've used a slightly modified definition: smoothtrio's strength=log(n-2)/log(q), where q is the largest prime factor among n, n-1, n-2's prime factors.

Couldn't have done it without you, R! :smile:

Keep in mind, that in these x=6 cases, the differences between log(n)/log(p)
and log(n-1)/log(p) and log(n-2)/log(p) (where p is the high factor among the three numbers are almost negligible. For the last case, the values are the same through 15 decimal places. So, I'd rather keep the original definition even though I'm splitting hairs :)

BTW, could you give some insight into your last revision of this code? I'm really curious how you pared down the search. Thanks.


I suppose it's time for quartets now :)

[QUOTE=grandpascorpion]
BTW, could you give some insight into your last revision of this code? I'm really curious how you pared down the search. Thanks.
[/QUOTE]
It isn't very hard, known algorithms. Some parts:
Generate all smooth numbers by lexicographic order
Let m=n*p, where p is the largest prime factor of m, then we want to see if m-1 is smooth or not. Let q be a prime(power) and suppose that m-1 is divisible by q, so
m-1==0 mod q, here m=n*p, so we can write:
n*p==1 mod q from this:
p==modinverse(n,q) mod q, so every q-th number is divisible by q. It means that by sieving we can save the trial factoring of m-1. I included your ideas also.

I've made a GMP version of the program. If you want I'll post. In that version: d<127 and d<=15*x are the limitations only.

Quartets
 

R., that'd be great if you could post it. Thanks

Quartets (using a tweaked version of your code):

x=2

2106 = 2 x 3 ^ 4 x 13
2107 = 7 ^ 2 x 43
2108 = 2 ^ 2 x 17 x 31
2109 = 3 x 19 x 37
===================================
x=3

11503632 = 2 ^ 4 x 3 x 7 ^ 2 x 67 x 73
11503633 = 29 x 37 x 71 x 151
11503634 = 2 x 23 ^ 2 x 83 x 131
11503635 = 3 x 5 x 11 x 13 x 31 x 173
===================================
x=4

89861691840 = 2 ^ 6 x 3 x 5 x 23 x 73 x 197 x 283
89861691841 = 17 x 29 ^ 2 x 43 x 313 x 467
89861691842 = 2 x 13 x 151 x 191 x 293 x 409
89861691843 = 3 ^ 6 x 7 x 11 x 31 x 113 x 457

Strength: LOG(89861691841)/LOG(467) = 4.1035

[QUOTE=grandpascorpion]
Quartets (using a tweaked version of your code):
[/QUOTE]
I also modified my program. These are the smallest smoothquartets solutions.

x=2

1680=2^4*3*5*7
1681=41^2
1682=2*29^2
1683=3^2*11*17

strength=log(1681)/log(41)=2
==========================================
x=3

3678723=3^3*19*71*101
3678724=2^2*7^2*137^2
3678725=5^2*37*41*97
3678726=2*3*83^2*89

strength=log(3678723)/log(101)=3.27577
==========================================
x=4

22377473780=2^2*5*139*179*193*233
22377473781=3*13*43*103*353*367
22377473782=2*19^3*67*97*251
22377473783=7*29*31*107*167*199

strength=log(22377473781)/log(367)=4.03554

Corrections
 

Actually, your x=2 answer doesn't fit the original definition.

I'm wrong about x=3 and x=4. I thought those answers weren't smooth enough. Which leads me to, when you were running for x=3, did you get a false positive with 3027675. I did when I ran it for 25 3.

One really large 74 bits smoothtrio for x=5 found by the smoothtriosgmp program:

16692872914488219204860=2^2*5*13*3853*6133*6299*20639*20899
16692872914488219204861=3^28*7^2*1579*9431
16692872914488219204862=2*97*167*277*563*12841*14951*17209

Now it is saving the found smoothtrios and you can continue the program because it is saving the program's d,x,n value after every 1000000-th iteration. If you want to continue the computation then don't give d and x, because if the number of the input pararmeters isn't 2 then the program will use the smoothtriosstat.txt file.

But note that this gmp version is about 15% slower than smoothtrio.c for d<=62.

You can see the source in the attachment.

And here it is an exe for P4.

[QUOTE=grandpascorpion]Actually, your x=2 answer doesn't fit the original definition.[/QUOTE]
As you can see I used my definition.
[QUOTE]
I'm wrong about x=3 and x=4. I thought those answers weren't smooth enough. Which leads me to, when you were running for x=3, did you get a false positive with 3027675. I did when I ran it for 25 3.[/QUOTE]
There was no problem for me. But I've rewritten only the gmp version.

That's fine but it's not really a valid answer.

Thanks for the gmp version.

Smooth Duo List / Duos, Triplets and Quartest submitted to OEIS / A002072 extended
 

Hi R.,

I tweaked your code to check duos and found min answers through the 9th power/term. I decided to use your variant of the definition and submitted all three lists to OEIS, citing your program.

Solutions and factorizations:
3=3,2=2

9=3^2, 8= 2^3

2401=7^4, 2400=2^5*3*5^2 (3rd and 4th term)

5909761=11^2*13^2*17^2, 5909760=2^8*3^5*5*19

1611308700=2^2*3^6*5^2*23*31^2, 1611308699=7^4*11*13^2*19^2

421138799640=2^3*3^5*5*13^4*37*41, 421138799639=17*19*23^2*31*43^3

2286831727304145=3^15*5*7^3*19*67*73, 2286831727304144=2^4*17*23^2*37*41^2*59*61*71

3948741978036988496=2^4*7^5*13*23*43*59^3*67*83, 3948741978036988495=5*11*17*31*97^2*101*103*109*113^2

I submitted these. I decided to use your variant of the definition.


=================================================

On a related note, I found some addition terms for [url]http://www.research.att.com/~njas/sequences/?q=A002072[/url]
using a modified version of your program. This list (n and n+1) takes extends this list up to prime = 97. There's no counterexamples < 2^62.

31887350832896
31887350832896
119089041053696
2286831727304144
2286831727304144
17451620110781856
166055401586083680
166055401586083680


Incidentally, for duos, the max value log(n)/log(max prime) was 9.287 for the pair below:

4108258965739505499=3^7*13*19*23^4*47*73*89^2
4108258965739505500=2^2*5^3*7^2*11*29^2*31^2*43^2*101^2

10 would be quite a challenge I think.

[QUOTE=grandpascorpion;86704]
I tweaked your code to check duos and found min answers through the 9th power/term. I decided to use your variant of the definition and submitted all three lists to OEIS, citing your program.
[/QUOTE]

Thanks! Great work, grandpa.

[QUOTE=grandpascorpion;86704]

On a related note, I found some addition terms for [url]http://www.research.att.com/~njas/sequences/?q=A002072[/url]
using a modified version of your program. This list (n and n+1) takes extends this list up to prime = 97. There's no counterexamples < 2^62.

31887350832896
31887350832896
119089041053696
2286831727304144
2286831727304144
17451620110781856
166055401586083680
166055401586083680

[/QUOTE]

Grandpa,

Could I have a copy of the modified program. Is it possible to look for smooth consecutive pairs, using the solution of pell equations, than sieving all numbers and then finding smooth numbers.

[url]http://en.wikipedia.org/wiki/Stormer%27s_theorem[/url]

Thanks:smile:

Hi Citrix,

Thanks for this link. To be frank, my script (originally R. Gerbicz's) has a totally different algorithm.

Don Reble has already written a script (which I assume is much more efficientwith Pell approach in Python:
[url]http://www.research.att.com/~njas/sequences/a002072.py.txt[/url]

It would be a good little exercise to convert this to a C program.

Sequences [B]A002072[/B] and [B]A117581[/B] are the same, only the latter uses the higher value of each pair as the sequence value.

This is preferable, I think, since the only published tables, the 1964 results of Dick Lehmer, use that convention, and his proofs are given in the same terms.

Both sequences have the same inconvenient feature, though - those pairs of duplicate values might preserve the monotonicity (if that's a word!) of the sequence, but only by omitting useful information.

Writing [I]gpd[/I](n) for greatest prime divisor of n, what is [B][I]S'([/I]23)[/B], the greatest S for which n = S(S-1) has [I]gpd[/I](n) = 23?

The answer of course is 5142501, but this is less than [B][I]S'([/I]23) = [/B]11859211, so it gets left behind!

Anyway, here is a list that fills in those entries, and which extends the sequence to the 35th prime:

[code]
[SIZE=3][FONT=Courier New][COLOR=navy]N pN S'(pN) log2(S')[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]=============================================[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 1. 2 2 1[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 2. 3 9 3.1699[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 3. 5 81[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 4. 7 4375[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 5. 11 9801[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 6. 13 123201[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 7. 17 336141[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 8. 19 11859211 23.4995[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 9. 23 5142501 22.2940[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]10. 29 177182721 27.4077[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]11. 31 1611308700 30.5856 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]12. 37 3463200000 31.6895[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]13. 41 63927525376 35.8957[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]14. 43 421138799640 38.6155[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]15. 47 1109496723126 40.0103[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]16. 53 1453579866025 40.4027[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]17. 59 20628591204481 44.2297[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]18. 61 31887350832897 44.8580[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]19. 67 12820120234376 43.5435[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]20. 71 119089041053697 46.7090[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]21. 73 2286831727304145 51.0223[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]22. 79 9591468737351909376 63.0565 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]23. 83 17451620110781857 53.9542 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]24. 89 166055401586083681 57.2044[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]25. 97 49956990469100001 55.4715[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]26. 101 4108258965739505500 61.8332[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]27. 103 19316158377073923834001 74.0322 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]28. 107 386539843111191225 58.4234[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]29. 109 90550606380841216611 66.2954 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]30. 113 205142063213188103640 67.4752[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]31. 127 53234795127882729825 65.5290[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]32. 131 4114304445616636016032 71.8011[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]33. 137 124225935845233319439174 76.7173[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]34. 139 3482435534325338530940 71.5606[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]35. 149 6418869735252139369210 72.4428[/COLOR][/FONT][/SIZE]
[/code]

Good point Jim. Did you convert the script to C or just run it in Python?

Sorry for the loss of continuity in my post above - I hadn't actually finished it ... pressed "save" when I meant "keep editing" ...

Then I couldn't find it again ... presumably 1st posts get held in quarantine until moderated?

I'll provide more info when (and if) I remember what it was I that I intended to add ... :cool:


Regarding the code used, it's all hand-rolled. I'm doing research at ANU (under Richard P Brent) generally on "fast" algorithms for computing the elementary functions (high precision). All experimental work is done with
standard C (gcc) and we use GMP as the arithmetic kernel.

(I also test a lot of stuff at home, on a PC, using VB6, for which I've knocked up a GMP dll interface)

This particular topic ("Stoermer's Problem") has only popped up on my radar very recently, I'd never heard of Stoermer a month ago. I have a new and practical use for these smooth pairs (ie. superparticular ratios)

I did look at the Python example you mentioned, as I didn't even know about continued fractions to begin with!

Then I started with a basic implementation of Dick Lehmer's method in C, and looked hard at making the continued fraction and smoothness-testing rouines as fast as possible, etc.

When I got the thing running, I quickly discovered that doing Lehmer's work (13 primes) in less than a second was not as exciting as it seemed at first - this was of course entirely due to the faster hardware we have these days ...

Every additional prime still costs about 10 times as much to solve than the previous one, and it seemed to me that "10" might itself be showing signs of increasing itself ...

... the problems of exponential growth in complexity relating to the number of equations, the increasingly huge Pell eqn discriminants D, and their corespondingly increasing periods, etc, are well-known to you all, I'm sure!

So I found of course that it was very hard to get past N=25 primes (p = 97), and from OEIS I gathered that everybody else was in the same boat

I'll explain how I managed to get to a complete enumeration for the first 35 primes (to p = 149) in around 70 minutes (all times I quote are for a reasonably conventional confign, a 2GHz AMD64) in the next post.

I have reduced that incremental cost factor from 10 down to around 2.5, still exponential but it does increase by a modest amount the number of primes you can do in given time - this result can be applied in practice quite easily, but I don't yet have formal proof-of-correctness of my short-cut (which is what it comes down to)

At that rate pushing up to 40 primes (173) is just a matter of days - it helps that I've also found a way to adapt Lehmer's method so that it can be run [I]incrementally[/I], that is, just dealing with the additional prime(s) being introduced at each run.

Other interesting results I have include a way to do all 3 of Lehmer's enumerations (S, S-1) (S, S-2) and (S, S-4) in a single pass over the set of square-free D

And Dick missed a few numbers in his tables (not the main one, S(S-1), which is accurate, but I found a dozen cases in S(S-2) and S(S-4) that are not in Lehmer's tables)


I'll describe all this and other possibly useful observations I have on speeding up computation, in additional postings


Cheers

Jim White
MSI (Austn National University)



(to be ctd)

[QUOTE=Jim White;113191]Anyway, here is a list that fills in those entries, and which extends the sequence to the 35th prime:

[code]
[SIZE=3][FONT=Courier New][COLOR=navy]N pN S'(pN) log2(S')[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]=============================================[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 1. 2 2 1[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 2. 3 9 3.1699[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 3. 5 81[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 4. 7 4375[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 5. 11 9801[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 6. 13 123201[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 7. 17 336141[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 8. 19 11859211 23.4995[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy] 9. 23 5142501 22.2940[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]10. 29 177182721 27.4077[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]11. 31 1611308700 30.5856 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]12. 37 3463200000 31.6895[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]13. 41 63927525376 35.8957[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]14. 43 421138799640 38.6155[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]15. 47 1109496723126 40.0103[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]16. 53 1453579866025 40.4027[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]17. 59 20628591204481 44.2297[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]18. 61 31887350832897 44.8580[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]19. 67 12820120234376 43.5435[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]20. 71 119089041053697 46.7090[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]21. 73 2286831727304145 51.0223[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]22. 79 9591468737351909376 63.0565 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]23. 83 17451620110781857 53.9542 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]24. 89 166055401586083681 57.2044[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]25. 97 49956990469100001 55.4715[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]26. 101 4108258965739505500 61.8332[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]27. 103 19316158377073923834001 74.0322 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]28. 107 386539843111191225 58.4234[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]29. 109 90550606380841216611 66.2954 [/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]30. 113 205142063213188103640 67.4752[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]31. 127 53234795127882729825 65.5290[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]32. 131 4114304445616636016032 71.8011[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]33. 137 124225935845233319439174 76.7173[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]34. 139 3482435534325338530940 71.5606[/COLOR][/FONT][/SIZE]
[SIZE=3][FONT=Courier New][COLOR=navy]35. 149 6418869735252139369210 72.4428[/COLOR][/FONT][/SIZE]
[/code][/QUOTE]That is A145606: [url]http://oeis.org/A145606[/url]

It would be fine to add these new terms and to correct A002072.

The sequence of maximal n's, for which n, n+1 and n+2 are p-smooth with p running over primes, is A003032:
[url]http://oeis.org/A003032[/url]

The similar sequence is A003033, where the chains of length 4 are considered:
[url]http://oeis.org/A003033[/url]
(BTW, there are also some wrong entries, I'm going to correct them.)

In general, all these sequences seems to grow nearly as

a_k*exp(b_k*sqrt(p))

where k+1 is the length of the chain. Some plots showing this could be found in the following Excel table:
[url]http://www.primefan.ru/stuff/math/maxs.xls[/url]

Well, in this topic we consider trios; it seems that a_2 is about 0.08 and b_2 is about 2.2, so A003032 is about

0.08*exp(2.2*sqrt(p))

Therefore it's not much sense to use log(n)/log(p) as a measure of the "strength". The better would be log(n)/sqrt(p), and the largest currently known is

log(407498958)/sqrt(89) = 2.1015

[QUOTE=XYYXF;268076]The better would be log(n)/sqrt(p), and the largest currently known is

log(407498958)/sqrt(89) = 2.1015[/QUOTE]Oops, log(138982582998)/sqrt(103) = 2.52812 is larger.

Smooth pairs up to p=173 are reported there by Jim White:
[url]http://11011110.livejournal.com/97325.html?thread=351533#t351533[/url]

Let's define L(n, k) as the largest prime factor of product

n*...*(n+k)

of k+1 consecutive integers, starting at positive integer n.

So we have, for example,
L(4374, 1) = 7
L(48, 2) = 7
L(350, 2) = 13
L(138982582998, 2) = 103
L(61011223, 3) = 163
L(23931257472314, 3) = 631
L(1517, 4) = 41
L(3294850, 5) = 239
L(1913253200, 8) = 3499
L(8559986129664, 12) = 58393
L(48503, 14) = 379

[B] Conjecture:[/B]
as n goes to infinity,

lim inf L(n, k) / (log n)^2 = C_k

The very rough estimates of constants C_k are:
C_1 ~ 0.0376
C_2 ~ 0.258
C_3 ~ 0.907
C_4 ~ 2.46
C_5 ~ 5.16
C_6 ~ 11.4
C_7 ~ 19
C_8 ~ 42
C_9 ~ 70
C_10 ~ 140
C_11 ~ 200
C_12 ~ 250
C_13 ~ 380
C_14 ~ 430
C_15 ~ 460

Some successive minima of L(n, k) are shown there:
[url]http://oeis.org/A193943[/url]
[url]http://oeis.org/A193944[/url]
[url]http://oeis.org/A193945[/url]
[url]http://oeis.org/A193946[/url]
[url]http://oeis.org/A193947[/url]
[url]http://oeis.org/A193948[/url]
[url]http://oeis.org/A199407[/url]
[url]http://oeis.org/A200566[/url]
[url]http://oeis.org/A200567[/url]
[url]http://oeis.org/A200568[/url]
[url]http://oeis.org/A200569[/url]
[url]http://oeis.org/A200570[/url]
[url]http://oeis.org/A209837[/url]
[url]http://oeis.org/A209838[/url]
[url]http://oeis.org/A209839[/url]

Any suggestions on the conjecture? Does it depend on other
known ones like Twin prime conjecture or ABC conjecture?

Great thanks for any information on the subject.