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.