|
The Størmer Problem (Lehmer's method etc)
It makes sense to start a specific thread for this topic, I think ..
The discussion developed originally in this thread [URL]http://www.mersenneforum.org/showthread.php?t=5647[/URL] I'll start this thread by reproducing my first posting there, which has some useful data, and also give a simple definition of the problem for newcomers: [B][U]Størmer's Problem (1897)[/U][/B] [SIZE=3][COLOR=black]Write [I][B]gpd[/B][/I]([I][B]n[/B][/I]) for the greatest prime divisor of [I][B]n[/B][/I][/COLOR][/SIZE] [COLOR=black][SIZE=3]Given some prime [B]p[/B], [/SIZE][SIZE=3]for which [I][B]n[/B][/I] do we have [I][B]gpd[/B][/I]([B]n[/B]([B]n[/B]-[B]1[/B])) <= [B]p[/B]? [/SIZE][/COLOR] We can refer to the set of all such values of [B][I]n [/I][/B]for given [B]p [/B]as [FONT=Courier New][SIZE=3][COLOR=#000080][FONT=Verdana][SIZE=2][COLOR=black][B]S(p)[/B], and [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][SIZE=3][COLOR=#000080][SIZE=2][COLOR=black][B]S'[/B]([B]p[/B])[/COLOR][/SIZE] [/COLOR][/SIZE]for the [I]maximum[/I] value [B][I]n [/I][/B]for which [B][I]gpd[/I][/B]([B]n[/B]([B]n[/B]-[B]1[/B])) [B]=[/B] [B]p [/B](note that these sets are demonstrably [I]finite, [/I]and so [B]S'[/B]([B]p[/B]) always exists). The pairs ([B]n[/B],[B] n-1[/B]) are obviously representable as (twice the value of) triangular numbers, via their product, and are also known in musical interval theory as [I]Superparticular Ratios, [/I]when represented as rational quotients [B]n / n-1 [/B](these ratios are highly composite, and are as close to possible to 1) ======================================================= OEIS sequences [B]A002072[/B] and [B]A117581[/B] both list the sequence [B]S'(p)[/B], only the first one lists the lower value of each pair, ie [B]S'(p) - 1[/B] Using the higher value is preferable, I think, since the only published tables, the 1964 results of Dick Lehmer ("On a Problem of Størmer", [I]Illinois J. Math[/I], [B]8[/B], 1964, pp 57-79), for [B]p [/B]up to 41,use that convention. Also his proofs are given in the same terms, and it corresponds to the convention used by the muso's. Both sequences as recorded in OEIS have an inconvenient feature, though - there are duplicate values in the sequence, in order (presumably) to keep the sequence increasing. But this omits useful information. If we ask what is [B][I]S'[/I](23)[/B], the [I]greatest[/I] value of S for which [I]gpd [/I](S(S-1)) = 23? The answer is 5142501, but this is [I]less[/I] than [B][I]S'[/I](19) = [/B]11859211, so it does not appear in the sequence, the latter value is just repeated. Here is a list which applies the definition of [B][I]S'[/I](p) [/B]strictly, and which extends the sequence to the 35th prime (149): [code] [SIZE=3][FONT=Courier New][COLOR=navy]N p S'(p) 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] Jim White Math. Sciences Institute Australian National University |
Here is an entry from the table above, showing the factors of the corresponding pair:
[B][FONT=Courier New][COLOR=navy][COLOR=black]124225935845233319439173[/COLOR] [/COLOR][/FONT][/B] [B][FONT=Courier New][COLOR=navy] 13^6, 17, 37, 53, 67, 79, 83, 101, 127, 137[/COLOR][/FONT][/B] [B][FONT=Courier New][/FONT][/B] [B][FONT=Courier New][COLOR=navy][COLOR=black]124225935845233319439174[/COLOR][/COLOR][/FONT][/B] [B][FONT=Courier New][COLOR=navy]2, 3^4, 7, 19^2, 23^2, 29, 31, 47, 97^2, 113^3[/COLOR][/FONT][/B] There are no greater values possible for 137-smooth pairs of consecutive integers. |
Lehmer's Method
Much of what follows will discuss "Lehmer's Method", which finds all members of [B]S(p) [/B]by solving 2^n Pell equations (where n is the number of primes involved), and testing the solutions thereof for [B]p[/B]-smoothness.
So we assume from here on that readers have read that paper and/or know exactly what we're talking about! There is a brute-force method that can also be used that requires no knowledge of Pell equations or continued fractions, but requires that you have a reasonable upper bound on [B]S'(p)[/B] Both methods have exponential complexity however, and in reality we have great difficulty extending the known results, as identifying each additional value of the sequence [B]S'(p) [/B]can take anywhere from 2 to around 10 times as long as the previous one. Currently we seem to be limited in what can be done in a reasonable time to around 25-30 primes. I'll quickly summarise the two methods in a post below, and what's known about [I]proof-of-correctness [/I]issues |
Lehmer method in a Nutshell (updated)
[LIST][*]let [B][I][SIZE=3]Q[/SIZE][/I][/B] be the set of primes {2, ... [I][SIZE=3]p[/SIZE][/I]}, and let [I][FONT=Times New Roman][SIZE=4]n[/SIZE][/FONT][/I][B] [I]= [/I][/B][tex]\pi[/tex][SIZE=3]([I]p[/I])[/SIZE] =[SIZE=3][I]|[B]Q[/B]| [/I][/SIZE][SIZE=2]be the number of primes in [/SIZE][SIZE=3][B][I]Q[/I][/B][/SIZE][/LIST][LIST][*]let [I][B][SIZE=3]Q[/SIZE]*[/B] [/I]denote the set of [I][SIZE=3]p[/SIZE][/I]-smooth numbers[/LIST][LIST][*]let [I][B][SIZE=3]Q'[/SIZE][/B] [/I]be the set of all [I]odd, square-free[/I] members of [B][I][SIZE=3]Q[/SIZE]*, [/I][/B]so [SIZE=3]|[B][I]Q'[/I][/B]|[/SIZE] = [tex]2^{n-1}[/tex][/LIST][LIST][*]let [B][I][SIZE=3]S[/SIZE][/I]([/B][I][SIZE=3]p[/SIZE][/I][B]) [/B]be the set of all integers [tex]a[/tex] for which [tex]a({a-1}) \in [/tex] [B][I][SIZE=3]Q[/SIZE]*[/I][/B][/LIST][B][I]Algorithm to Enumerate [SIZE=3]S[/SIZE][/I]([/B][SIZE=3][I]p[/I][/SIZE][B]) ("[I]Lehmer's Method"[/I])[/B][LIST][*]for every [tex]D \in[/tex] [I][B][SIZE=3]Q'[/SIZE][/B], [/I]find [tex] (x_1, y_1) [/tex], the fundamental solution to the Pell equation [tex] x^2 - 2Dy^2 = 1 [/tex]. If ... [tex]y_1[/tex] ... is [SIZE=3][I]p[/I][/SIZE][B]-[/B]smooth, then [tex]x_1= 2a - 1[/tex], and both [I][SIZE=3][FONT=Times New Roman][SIZE=4]a[/SIZE][/FONT] [/SIZE][/I]and [I][SIZE=3][FONT=Times New Roman][SIZE=4]a[/SIZE][/FONT] [/SIZE][/I]- [SIZE=3]1[/SIZE] are [I][SIZE=3]p[/SIZE][/I][B]-[/B]smooth, ie [tex]a \in[/tex] [B][I][SIZE=3]S[/SIZE][/I]([/B][I][SIZE=3]p[/SIZE][/I][B])[/B][/LIST][LIST][*]repeat the step above for 4D, ie solving [tex]x^2 - 4Dy^2 = 1[/tex][/LIST][LIST][*]in both cases, should the Pell equation produce a [I][SIZE=3]p[/SIZE][/I][B]-[/B]smooth result, then also inspect the multiple-solution sequence [tex](x_k, y_k)[/tex], for [tex] k = {2, 3 ... max(3, (p+1)/2)}[/tex]. Check each [tex]y_k[/tex] ... for [I][SIZE=3]p[/SIZE][B]-[/B][/I]smoothness, and the corresponding [tex]x_k[/tex]will also produce a member of [B][I][SIZE=3]S[/SIZE][/I]([/B][I][SIZE=3]p[/SIZE][/I][B])[/B][/LIST][I][U]Remarks[/U][/I]
Remember, there is no need to generate and inspect the solution sequence unless you have got a "hit" with the fundamental solution. That's because ... [tex]y_1[/tex] divides all other ... [tex]y_k[/tex] ... so if it isn't smooth none of them can possibly be smooth. There are both 1st and 2nd order recurrence relations for iterating the multiple solutions: [tex]x_{n+1} = {x_1}{x_n} + Dy_1{y_n}[/tex] [tex]y_{n+1} = {x_1}{y_n} + x_n{y_1}[/tex] [tex]x_{n+1} = 2x_1{x_n} - x_{n-1}[/tex] [tex]y_{n+1} = 2x_1{y_n} - y_{n-1}[/tex] |
Størmer's Original Solution
[B]Carl Størmer [/B]must be given full credit for his demonstration in 1897, that Pell equation properties allowed a finite characterisation of the problem, and came up with an algorithm and the proof of its correctness, which constituted the first ever proof that [B][I][SIZE=3]S[/SIZE][/I]([/B][I][SIZE=3]p[/SIZE][/I][B]) [/B]was in fact always finite[B].[/B]
The properties of the sequences of multiple solutions of a Pell equation were not well known then, and Størmer gave the original method and proof in terms of fundamental solutions alone. A larger set of [tex]D[/tex] than the one we used above is shown to produce all the required values as fundamental solutions. Størmer showed that solving [tex]x^2 - Dy^2 = 1[/tex] for all [tex]D \in[/tex] [B][I][SIZE=3]Q''[/SIZE][/I][/B], where [SIZE=3][B][I]Q'' [/I][/B][/SIZE]is the set of all [I]cube-free [/I]members of [B][I][SIZE=3]Q*[/SIZE][/I][/B] would necessarily produce all [tex]a \in[/tex] [B][I][SIZE=3]S[/SIZE][/I]([/B][I][SIZE=3]p[/SIZE][/I][B]) [/B]in some solution as [tex]x_1 = 2a-1[/tex] It boils down to showing that every target value will turn up as fundamental solution for any [tex]D[/tex] that correctly matches the target's prime composition, and which also gets the exponent [I]parities[/I] right too. The number of equations that need to be checked, though, is much greater than in Lehmer's later refinement, as we have [SIZE=3]|[B][I]Q''[/I][/B]|[/SIZE] = [tex]3^n - 2^n[/tex] Mind you, even with Lehmer's reduction of the problem to [tex]O(2^n)[/tex], this is not a cheap computation by any means. Lehmer was able to do the first 13 primes on a 1962-vintage IBM704, and with todays 2GHz desktop box we can only advance that by 20 or so primes before hitting the wall ... As the number of equations to be solved doubles with each prime, so also does the individual cost of each equation, as the magnitudes of the integers involved spirals ever upward. In reality, the expected running time (with the Lehmer method), appears to be more like [tex]O(10^n)[/tex] |
[QUOTE=Jim White;113263][*]in both cases, should the Pell equation produce a [I][SIZE=3]p[/SIZE][/I][B]-[/B]smooth result, then also inspect the multiple-solution sequence [tex](x_k, y_k)[/tex], for [tex] k = {2, 3 ... max(3, (p+1)/2)}[/tex].[/QUOTE]
Why is it need to check up to only max(3,(p+1)/2) ? Is it trivial, because I don't see it. You can send the extensions of the Sloane's sequences to Neil Sloane as a "b-file", see: [URL="http://www.research.att.com/~njas/sequences/Submit.html"]http://www.research.att.com/~njas/sequences/Submit.html[/URL] |
If some one is interested in writing the code, may be we can search for more numbers in this series.
[url]http://www.mersenneforum.org/showthread.php?t=5630[/url] [url]http://www.research.att.com/~njas/sequences/A116486[/url] Thanks.:smile: |
A Brute-force Method
1 Attachment(s)
The only alternative method for complete enumeration appears to be a brute-force search of all [tex]S \in[/tex] [B][I][SIZE=3]Q[/SIZE]*[/I][/B], a search for which we will obviously need a [I]bound,[/I] [tex]S \leq X[/tex]
Any results are only provably correct if the bound [tex]X[/tex] is. So we can use known existing bounds, otherwise we'd need something like a bound produced by a lattice basis reduction algorithm. The method then is to enumerate [B][I][SIZE=3]Q[/SIZE]* [/I][/B]recursively, using the bound to limit the depth. For each [tex]S \in[/tex] [B][I][SIZE=3]Q[/SIZE][SIZE=2]* [/SIZE][/I][/B]we simply test [tex]S-1[/tex] for [I][SIZE=3]p-[/SIZE][/I]smoothness. Crude as it sounds, and also bearing in mind that our target subset [B][I][SIZE=3]S[/SIZE][/I]([/B][I][SIZE=3]p[/SIZE][/I][B]) [/B]is but a tiny fraction of the bounded subset of [I][B][SIZE=3]Q[/SIZE]*[/B], [/I]in reality this method actually runs much faster than Lehmer's method. On a 2GHz AMD64 (with GMP for MP-arithmetic where necessary), 17 primes (p \leq 59) takes about 4 hours using Lehmer's method, while the generative search method (armed with the known bound), gets there in just 20 seconds. Getting to the 18th prime, 61, with the Lehmer method would probably take 30 to 40 hours. The generative search can get to [B]25 [/B]primes (p \leq 97) in about an hour. Once again, we assume a tight bound is available, but we can assume, from what (little) I understand about the "LLL-BRA" method, that this is generally available, and at relatively low cost. The running time for the generative search appears [tex]O(2^n)[/tex], but only up to the point where it can all be done with native 64-bit integer arithmetic. I expect that the log gradient will begin to rise after that. I have not yet got enough data to estimate the trend beyond that point (around p = 97). There is a large "spike" at prime 27 = 103, where the upper bound has to be raised from [tex]2^{64}[/tex] to [tex]2^{75}[/tex]. That run I have done, and it took just under 4 hours. These spikes (due to the not-always-increasing sequence of maximum solutions) make it hard to predict any more, without some rather long and tedious test runs. I have a preliminary chart of these times, about somewhere, I'll attach it here. The times here are for 'incremental' runs - each run was targeting just those values where the maximum [B]p [/B]actually divides the solution |
[quote=Citrix;113318]
[URL]http://www.mersenneforum.org/showthread.php?t=5630[/URL] [URL]http://www.research.att.com/~njas/sequences/A116486[/URL] [/quote] Yes, there are obvious similarities ... ... and a few potentially significant differences perhaps :unsure: Are these "logarithmically smooth" numbers purely a curiosity, or do they have some application? Cheers |
[quote=R. Gerbicz;113313]You can send the extensions of the Sloane's sequences to Neil Sloane as a "b-file", see: [URL]http://www.research.att.com/~njas/sequences/Submit.html[/URL][/quote]
I plan to do that, also have a very interesting new proposed sequence relating to maximal orthogonal bases in the corresponding smooth-rational vector space [quote=R. Gerbicz;113313]Why is it need to check up to only max(3,(p+1)/2) ? Is it trivial, because I don't see it.[/quote] Not difficult, but not obvious, the Pell equation multiple-solution sequences [I]xn, yn [/I]are simple 1st- or 2nd- order recurrence sequences, and Lucas's theorems relating include a "Law of (prime) Apparition" which says that the [tex]n[/tex]-th term in any such sequence must have at least one prime divisor [tex]\geq 2n - 1[/tex] |
Incremental Enumeration with Lehmer Method
The [I]incremental [/I]version of the problem is:
[COLOR=black][SIZE=3]Given some prime [B]p[/B], [/SIZE][SIZE=3]for which [I][B]n[/B][/I] do we have [I][B]gpd[/B][/I]([B]n[/B]([B]n[/B]-[B]1[/B])) = [B]p[/B]? [/SIZE][/COLOR] That is, we replace the inequality of the original problem definition with equality. In the brute-force method, adapting the generative search to perform incrementally is straight-forward (we only visit/generate nodes that include [B]p[/B]). For the Pell equation approach, however, we need to adapt Lehmer's method slightly. We look at [tex]D[/tex] values corresponding to each of the [tex]2^{n-1}[/tex] combinations of primes [I]not[/I] including the new [tex]p[/tex], and for each such [tex]D[/tex] we check the Pell equations for both [tex]pD[/tex] and [tex]p^2D[/tex], thus covering both solution parity possibilities for the new divisor. This modification is, I think, provably correct, and follows from Størmer's Theorem (and works in practice!). It also suggests that multiple solution checking is probably going to be largely unnecessary - to what exact extent I haven't quite got around to figuring out just yet! That's because it really has no significant impact on the running time, which is dominated by the task of obtaining fundamental solutions. The result generally runs, as expected, in around half the time that it would take to generate the complete set for all [B]p'[/B] <= [B]p[/B] , so it is useful to have. |
Lehmer's multiple solution bound
[quote=Jim White;113336] ... the [tex]n[/tex]-th term in any such sequence must have at least one prime divisor [tex]\geq 2n - 1[/tex][/quote]
Lehmer's paper states this as [B]Lemma 5[/B]: If [tex]n > 3[/tex], then [tex]y_n[/tex] is divisible by some prime [tex]p \geq 2n-1[/tex] You'll find his full proof there. Empirical evidence suggests that Lehmer's effective bound, [tex]n \leq max (3, {p+1 \over 2})[/tex], for which [tex]y_n[/tex] might remain [tex]p[/tex]-smooth, might in fact be further reduced, but this is not of major consequence for expected running times, as I mentioned earlier, and so is not yet fully investigated. |
[QUOTE=Jim White;113329]
So we can use known existing bounds, otherwise we'd need something like a bound produced by a lattice basis reduction algorithm. [/QUOTE] One more question, Jim: What exact upper bound is known? |
Jim,
Out of curiosity. The only application I can think of right now, is to study Pell equations and the largest possible solution for each D. From what I understand, the prime values have the first solution as a large number, whereas smooth D values have smaller first solutions. But there has been no work done on the largest solution, if the first solution is known. May be some pell equations have infinite solutions? Any thoughts? :smile: |
Regarding [COLOR=darkgreen][B]Citrix[/B][/COLOR]'s question, if all variables are strictly positive integers then we know [tex]x^2 - Dy^2 = 1[/tex] does always have an infinite number of solutions in positive integers.
Now, going the other way, we may also find a particular solution [tex](x', y')[/tex] as a solution, even a fundamental solution, to more than one Pell equation An example (based on a smooth pair): [tex]a = 195 = 3.5.13[/tex] [tex]a+1 = 196 = 2^2.7^2[/tex] [tex]2a+1 = 391[/tex] [tex]a(a+1) = 38220[/tex] [tex]391^2 - 195(2^2 * 7)^2 = 1[/tex] [tex]391^2 - 780(2*7)^2 = 1[/tex] [tex]391^2 - 3120(7)^2 = 1[/tex] [tex]391^2 - 9555(2^2)^2 = 1 [/tex] [tex]391^2 - 38220.(2)^2= 1[/tex] [SIZE=5][SIZE=2]For each distinct square [tex]y^2[/tex] that divides [tex]4a(a+1)[/tex], we have a corresponding [tex]D[/tex] whose Pell equation solutions must include [tex](2a+1, y)[/tex]. In many such cases it can occur as a fundamental solution.[/SIZE][/SIZE] [SIZE=5][SIZE=2]If we call any [tex]D[/tex] that produces [tex]2a+1[/tex] as a solution a [B][I]producer[/I][/B] of [tex]a[/tex], then the Størmer/Lehmer schemes work by giving a scheme for constructing a finite set of [tex]D[/tex] which is guaranteed to include at least one producer of all target value [tex]a[/tex][/SIZE] [/SIZE] |
[quote=R. Gerbicz;113345]One more question, Jim:
What exact upper bound is known?[/quote] By [I]existing known bounds [/I]I meant only those which are themselves already established, which, strictly speaking, is limited to those resulting from complete and accurate applications of Lehmer's method (or of Størmer's, but that's very much slower). At the moment we have only two ways to confirm any individual bound (and for any given number of primes it must be individually computed). That's by either following Lehmer's recipe correctly, and completely, or by getting a provably correct (and usefully close) bound from above. The latter can perhaps be obtained from "Bakersfield", the general area of Baker's Theorems regarding linear forms in logarithms used to [I]approximate [/I]solutions to Diophantine equations. For [tex]n[/tex] primes there is an [tex]n[/tex]-dimensional integer lattice in which we can (theoretically) find a reduced basis that will yield a vector of "shortest height", from which we can derive such a bound. I think the tightness of the bound inevitably depends to some extent on how long you're prepared to wait, of course. Our particular problem is not one that the Bakersfield mob have really thought much about, other than to observe in passing that it is theoretically applicable ... I am corresponding with somebody knowledgable in the area and hope to lerrn more Meanwhile, Lehmer's results, meanwhile, which showed all 869 smooth pairs for the 13 primes up to 41, can be read as gospel, and are easily verified/reproduced. The sequence of greatest values currently on show at OEIS is, presumably, also verified. Myself, I have only performed such a strictly correct enumeration for the 17 primes up to 59, for which the incremental run alone was starting to take hours (see above posts). I assume the providers of the values for p to 97 have followed the recipe strictly, and have been able to devote sufficient time (and perhaps a more powerful machine) to the computation ... ... or they know something which I don't, but apparently should! :down: My figures for the primes beyond 97, which go up to p = 149 are not gospel, but are "almost certainly" correct. They can't yet be claimed correct, as they were performed by a "stripped-down" Lehmer method that does very much less work. This method is new and as yet unsupported by a theorem, but I have high hopes that will come in due course. I will describe this in a post soon, but meanwhile, those of you who have some form of working code for the Lehmer method can guess what I'm doing through a simple, but revealing, experiment: When your program reports each smooth-pair index value, [tex]a[/tex], have it also report the [I]period length [/I]for the producer of [tex]a[/tex], ie. the period length of the corresponding [tex]\sqrt{D}[/tex]. It will be sufficient to run it just for the Lehmer example (p <= 41), where the periods for all equations involved range up to 16k or so, and the maximum period encountered for a [I]producer[/I] is ... ?? A [I]caveat [/I]is necessary - even if a firm analytical result in these terms is obtainable, all it gives us is another finite increment in the number of primes (say around 10) that might be "doable" in reasonable time. It opens a door, but only to a larger room, not to the open! But there is cause for optimism in the nature of the periodicity properties which might well lead to an evantual escape from the tyrrany of running times exponential in terms of [tex]n[/tex]. One suspects that some combinatorial-number-theoretical piece of the jigsaw is just there waiting to be found ... ... this could be intuitive, or perhaps one simply [I]hopes [/I](desperately enough)that it turns out to be the case! :wink: |
On Multiple Solutions to the Pell Equations
Another thought regarding [COLOR=darkgreen][B]Citrix[/B][/COLOR]'s question: if you take the fundamental solution (which is just that involving the smallest possible pair of integers x,y), you can then apply either of the recurrence formulae above to generate the infinite number of pairs that also satisfy the same equation.
This I think will be found to be just the same process that lets you generate an infinite family of related but distinct Pythagorean triplets from any one starting case .... Each solution has common divisors with the fundamental one, in particular [tex]y_1 | y_k[/tex] always, and [tex]D[/tex] will always divide [tex]x_k^2 - 1[/tex], but also the sequences are increasing, so they are picking up new divisors that were not in the original [tex]D[/tex]. Some of these become [I]periodic, [/I]some do not. The solution number [I]k [/I]in which a prime divisor first appears is called its "Index of Appearance" (or Apparition), and various Laws relating thereto are called "Laws of Apparition" The prime divisors in any solution that do not divide [tex]D[/tex] are also called [I]extrinsic, [/I]for obvious reasons So Lehmer's bound on the range of multiple solutions that should be checked can most probably be tightened if expressed in the number of prime divisors of the solution in question, by comparison with the number of primes [I]available [/I](unused) that could possibly appear in solutions as extrinsic divisors ... well, I think so, anyway But as I said, no complexity gain is likely to arise from a tightening of this particular bound. Multiple solutions are more probable when the [tex]D[/tex] are small - they indicate that there are "shortcuts" to some solutions that can be found by extrinsic-divisor-based solutions, which tend to be cheaper ... as we try to work with more and bigger primes, their current role diminishes accordingly |
[QUOTE=Jim White;113329]
On a 2GHz AMD64 (with GMP for MP-arithmetic where necessary), 17 primes (p \leq 59) takes about 4 hours using Lehmer's method, while the generative search method (armed with the known bound), gets there in just 20 seconds. [/QUOTE] I've completed my own gmp program for the problem. You can download this from [URL="http://robert.gerbicz.googlepages.com/stormer.c"]http://robert.gerbicz.googlepages.com/stormer.c[/URL] This program takes only 4 seconds for N=17 so p=59 on my slow computer ( 1.7 GHz Celeron ). So probably it is faster than your program. I've assumed for this that S'(p[N])<2^(3*N+1) is true ( p[1]=2,p[2]=3,p[3]=5... are the primes ). Note that this is true for the known solutions. |
Thanks Robert. That sounds good, I'll have a good look at it ...
|
Very nice work, Robert. That certainly runs faster than my initial hack ... I'll make an updated version of that timing chart above with a plot for your program running times. I have spare suits - you can be diamonds!
A description of your approach would be welcome! Your smoothness testing, for example, looks interesting. Mine doesn't do any gcd calls, for a start! |
[I](a little later)[/I]
[I]I'm beginning to understand (and appreciate) it a little better now ... you've implemented a Bounded version of the Lehmer method?[/I] If the bound is known, then the CF development process can take an early exit when the convergents get too big ... We know that this will in fact be the case far more often than not, so the time saving over regular (unbounded) Lehmer method, is substantial ... all we need is a reasonably good bound ... Now I see how it works, I will try an experiment with it! Cheers |
[QUOTE=Jim White;113425]
A description of your approach would be welcome! Your smoothness testing, for example, looks interesting. Mine doesn't do any gcd calls, for a start![/QUOTE] First I generate the odd *squarefree* numbers of the Q' set. In fact half of the numbers are divisible by p[N]^2, the other half of them are divisible by only p[N], the reason for this that we've to guarantee that a or a-1 is divisible by p[N]. There are 2^(N-1) such numbers, and after testing 2*D I'm testing 4*D, but only if D!=1, otherwise it is a square number, and the Pell equation is trivial. That part of the code is a little crazy, but not time critical, for example the following code do the same job, in almost the same time ( it isn't faster or slower by 1% ): [CODE] mpz_set_ui(D,2); for(i=1;i<N-1;i++) { if(J&1) { mpz_mul_ui(D,D,primes[i]); } J>>=1; } if(J&1) { mpz_mul_ui(D,D,primes[N-1]); } else { mpz_mul_ui(D,D,primes[N-1]*primes[N-1]); } [/CODE] About testing smoothness: that's also not time critical. For example for N=17 there are only 1648 smoothness tests in my program but we've to solve much more Pell equations. The time critical part is in solving Pell equations. For this I've used a well known approach to compute the continued fraction of sqrt(D) using only integer arithmetic, see: [URL="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion"]http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion[/URL] This is the same in my program d[],a[],m[]. For this I'm using also exact division for calculating d[n]. The other parts of the code is what you've already described. Note that I'm using LARGEST where LARGEST=p[n]=2*a-1. But maximizing a or LARGEST is the same. |
Timing chart update (Gerbicz's "Bounded Lehmer")
1 Attachment(s)
Here is an updated version of the timing chart posted above, showing Robert Gerbicz's "Bounded Lehmer" performance on the same system.
Forgive the clumsy plotting, the gradient for his plotted times is in reality straight (uncannily so) and at 45 degrees, ie O(2^n). Here are the actual times, and verification of correct incremental counts (NS) ... [code] > N19, p 71, NS = 790, et = 7 sec., Max = 12820120234376, > N20, p 73, NS = 943, et = 15 sec., Max = 119089041053697, > N21, p 79, NS = 1201, et = 30 sec., Max = 2286831727304145, > N22, p 83, NS = 1401, et = 64 sec., Max = 9591468737351909376, > N23, p 89, NS = 1738, et = 132 sec., Max = 17451620110781857, > N24, p 97, NS = 1955, et = 274 sec., Max = 166055401586083681, > N25, p101, NS = 2240, et = 572 sec., Max = 49956990469100001, > N26, p103, NS = 2793, et =1182 sec., Max = 4108258965739505500, [/code] The importance of reducing the number of Pell equations that are fully solved is obvious. As the maximum [B]p [/B]value rises, the typical Pell equation determinant expands and so do the period lengths. The longer the period length then the greater must be the fundamental solution magnitudes, so having any reasonable bound on the size of that fundamental solution is going to save substantial wasted effort. |
Period length as an effective bound
1 Attachment(s)
The use of a size bound in Lehmer's method as demonstrated by Robert's code above is very effective, in fact [I]more effective [/I]than another bound I have been using.
Period-length is seen to be a potentially effective bound on inspection of the period length of the [I]producers[/I], that is, for those the values of [I]D [/I]that produced smooth-pair results. Here's the table given at the top of this thread with an extra column, L(S) indicate the maximum period length of producers in the corresponding run. [code] [SIZE=3][FONT=Courier New][COLOR=navy]N p S'(p) log2(S') L(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 2[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 3. 5 81 4[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 4. 7 4375 6[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 5. 11 9801 8[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 6. 13 123201 10[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 7. 17 336141 10[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 8. 19 11859211 23.4995 12[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy] 9. 23 5142501 22.2940 16[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]10. 29 177182721 27.4077 14[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]11. 31 1611308700 30.5856 20[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]12. 37 3463200000 31.6895 18[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]13. 41 63927525376 35.8957 14[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]14. 43 421138799640 38.6155 18[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]15. 47 1109496723126 40.0103 20[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]16. 53 1453579866025 40.4027 18[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]17. 59 20628591204481 44.2297 20[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]18. 61 31887350832897 44.8580 22[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]19. 67 12820120234376 43.5435 24[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]20. 71 119089041053697 46.7090 20[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]21. 73 2286831727304145 51.0223 22[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]22. 79 9591468737351909376 63.0565 22[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]23. 83 17451620110781857 53.9542 28[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]24. 89 166055401586083681 57.2044 26[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]25. 97 49956990469100001 55.4715 24[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]26. 101 4108258965739505500 61.8332 28[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]27. 103 19316158377073923834001 74.0322 28[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]28. 107 386539843111191225 58.4234 30[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]29. 109 90550606380841216611 66.2954 30[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]30. 113 205142063213188103640 67.4752 36[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]31. 127 53234795127882729825 65.5290 32[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]32. 131 4114304445616636016032 71.8011 28[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]33. 137 124225935845233319439174 76.7173 30[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]34. 139 3482435534325338530940 71.5606 32[/COLOR][/FONT][/SIZE] [SIZE=3][FONT=Courier New][COLOR=navy]35. 149 6418869735252139369210 72.4428 34[/COLOR][/FONT][/SIZE] [/code] I have attached another chart which is just the one above with a 4th "suit" (spades), which shows the times for my implementation of Lehmer with period length bounding It runs fastest of all so far, but I think that's mainly because it has a faster Pell solver - it uses various 'tricks' to speed up the Pell equation solving process (eg going directly from mid-period to fundamental solution). If I introduce period bounding into Robert's program it makes no difference at all - actually it runs slightly slower, unless I specify very accurate bounds. If I allow both bounds to be checked and count the cases, it is obvious that the size bound check is much more effective, kicking in first in well over 90% of cases (even though it is by contrast a fairly relaxed bound). Armed with this knowledge, I think we might still get a further shift to the right on the chart by blending the two ... I'll look into that tomorrow! |
In fact there is a much faster way to search the solution if we assume that say S'(p[N])<2^(3*N+1) is really true.
Unfortunately in practice for example for N=35 ( the largest known value ) this isn't give speedup, , it is still small N value. The algorithm: suppose that we know: a=S'(p[n])<2^(3*n+1), but x=S'(p[n])=2*a-1 and x^2-2*D*y^2=1 or x^2-4*D*y^2=1 From this 2^(6*n+4)>4*a^2>x^2>2*D*y^2>=2*D so D<2^(6*n+3) Is it possible, that all prime numbers up to p[n] divides D ? For large n this can't be true: because from prime number's theorem p[n] is about n*log(n) and the product of all primes up to n*log(n) is e^(n*log(n))=n^n ( also from prime number's theorem ) and for large n this is larger than the previous bound: 2^(6*n+3) I haven't calculated how many squarefree numbers are there up to 2^(6*n+3) whose smoothness is p[n]~n*log(n). But I think this number is much smaller than 2^n, my guess is about c^(n*log(log(n))/log(n)) ( where c>1 ). This is similar to Dickman's problem. By backtracking it is possible to generate only p[n] smooth and squarefree D values and then solve for only these values the Pell's equations. Another approach what I've tried yesterday: by bactracking generate all p[n] smooth numbers up to 2^(3*n+1) that are divisible by p[n] and check if k+1 or k-1 is also smooth or not. This program was about 100 times slower than my posted program. The above method I think is much better ( we use only squarefree p[n] smooth numbers but yes there is a larger computation to solve the pell's equations). |
[QUOTE=Jim White;113449]
I have attached another chart which is just the one above with a 4th "suit" (spades), which shows the times for my implementation of Lehmer with period length bounding ... If I introduce period bounding into Robert's program it makes no difference at all - actually it runs slightly slower, unless I specify very accurate bounds. [/QUOTE] Probably the reason for that period length bounding and bounding the p[n] values is almost the same is a deep theorem: [URL="http://en.wikipedia.org/wiki/Khinchin%27s_constant"]http://en.wikipedia.org/wiki/Khinchin%27s_constant[/URL] |
R. Gerbicz,
Can your program be modified to search for log smooth numbers? If yes, could you provide an exe file. Thank you. |
[QUOTE=Citrix;113454]R. Gerbicz,
Can your program be modified to search for log smooth numbers? If yes, could you provide an exe file. Thank you.[/QUOTE] For more than 2 consecutive numbers this approach is (much) slower than my posted method in Smooth power trios thread. And that algorithm already contain some very fast methods for example identify smooth numbers by sieving, what isn't possible when we are using Pell's equations. |
1 Attachment(s)
Robert, I made a stupid error in the timing chart above, and your time-line is one position to the right of where it should be - I had your program displaying summary lines like this
> N24, p 97, NS = 1955, et = 274 sec., Max = 166055401586083681, ... I plotted that time against p=97, but from the counter (1955) it's obviously the result for p=89 Corrected plot is attached .. I've figured out the gist of your code - it just took me a while to understand the comments :wink: Thanks for your latest feedback, I'll throw some ideas I have in the ring later today after I've read them properly ... Agree Pell Eqn solving is the real work - the earlier that we can abort a solution the better .... Even 100% optimal code is going to run in exponential time, [tex]c^n[/tex]. We have got [I]c [/I]down to around 2, and since the number of equations to be considered is [tex]2^n[/tex] that seems unlikely to change much. To open a door to a seriously larger set of primes seems only likely with some of combinatorial optimisation feature, like some way to say "you need not bother looking at any node below this one". A better depth bound ... I have interesting data on properties of solution sets, number of prime divisors in [I]a [/I]and [I]a+1[/I], these distributions are very compact and illustrate why 99.99% of the time is spent looking for 0.01% of the targets! |
[quote=R. Gerbicz;113451]Probably the reason for that period length bounding and bounding the p[n] values is almost the same is a deep theorem: [URL]http://en.wikipedia.org/wiki/Khinchin%27s_constant[/URL][/quote]
Yes, it could be something like that ... not that I really understand the subject that well I do have a copy of a 1966 paper co-authored by Daniel Shanks with the rather long title [I]"Questions Concerning Khintchine's Constant and the Efficient Computation of Regular Continued Fractions" ....[/I] Sadly, like so many others, it is still in my pile marked "Papers I Really Should Read". This pile, by the way, exhibits superlinear growth, dwarfing the other piles such as "Papers I have Read", and the even smaller "Papers I have Read and Understood" I try not to think about the possibility that the size of that last pile might be converging to a limit! I see on that Wiki page that the CF for [I]e[/I] satisfies the relationship, which is interesting because of the geometric mean aspect - I wonder if that might possibly relate to the fact that the arithmetic-geometric-mean (AGM) method happens to be a good way to compute the function log([I]x[/I]) for arbitrary real [I]x[/I] > 0? |
[quote=R. Gerbicz;113450]By backtracking it is possible to generate only p[n] smooth and squarefree D values and then
solve for only these values the Pell's equations. [/quote] That's more or less what the "Spades" program does, if I understand you correctly. To do the 'incremental' enumeration for 97, say, I generate all square-free [I]q [/I]in {3,5,7,11 ... 89}*, then look at the 4 cases [tex] D \in \lbrace \sp 2 \times 97q,\sp 2 \times 97^2q, \sp4 \times 97q,\sp 4 \times 97^2q\rbrace[/tex] The appearance of spades above is a result of my trying to find a way to insert spacing into a tex string - I was trying "\sp" and got a surprise, in spades! I never did find a way to insert spaces yet, so they will do instead! I've got two different generators I can use for the square-free combo's - a recursive descent, and a "breadth-first" (ie all combns of 2 primes, then all combns of 3, etc). Both are suitable for bounding via the number of primes ... I've been using rough but effective values based on what I've seen. I've been looking at the distributions of numbers of divisors in the [I]target [/I]values, rather than the [I]D [/I]values themselves, because the target values are a fixed quantuity, whereas [I]D [/I]sets can be formed different ways, and there may turn out to be better "producer superset" than the one we have now. On the other hand, maybe not! |
[quote=R. Gerbicz;113450]
Another approach what I've tried yesterday: by bactracking generate all p[n] smooth numbers up to 2^(3*n+1) that are divisible by p[n] and check if k+1 or k-1 is also smooth or not. This program was about 100 times slower than my posted program. The above method I think is much better ( we use only squarefree p[n] smooth numbers but yes there is a larger computation to solve the pell's equations).[/quote] I called that the "Brute force" or "generative search" above - the plot line marked [tex]\cl[/tex] (aha!) on the chart is for a program which does just that ... The spikes are because of the very tight known bounds which have those expensive little jumps ... Bounding on the solution size (or the [I]D [/I]size) is very much more effective, and being out by a factor of 10 is unlikely to be of noticable impact (maybe an extra solution step in some subset of all the Pell equations) |
[LIST][*]From this [tex]2^{6n+4}>4a^2>x^2>2Dy^2 >=2D[/tex], so we have [tex] D<2^{6n+3}[/tex][/LIST]Here is an example, the biggest [I]producer [/I](of a solution) for p = 103
[tex]D = 1670718379371535594099740[/tex] D = 2^2, 3, 5, 13, 17, 19, 23, 29, 31, 37, 41, 53, 59, 67, 97, 101, 103 Y = 142 X = 91771952961741 The maximum number of prime divisors for [I]D [/I]is here 17 (of the 27 in the full set 2...103) And the producer of the biggest solution: [tex]D = 500884459304740[/tex] Y = 1726163680847580 X = 19316158377073923834001 There is only 1 producer value here with 17 divisors, but there are [I]C(25,15) = 4,903,140[/I] ways to select the composition, and it would be nice indeed to be able to find that combination by some other means than checking 4 x [I]4,903,140 [/I]cases ... Here's the distribution for number of solutions v numbers of prime divisors of the producer [I]D, [/I]for p = 103. The divisor counts are inclusive of the two constant divisors {2, 103}: [code] [FONT=Courier New][COLOR=navy]npd = 3, solns = 22[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 4, solns = 76[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 5, solns = 152[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 6, solns = 355[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 7, solns = 502[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 8, solns = 598[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 9, solns = 593[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 10, solns = 467[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 11, solns = 299[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 12, solns = 149[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 13, solns = 74[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 14, solns = 41[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 15, solns = 6[/COLOR][/FONT] [FONT=Courier New][COLOR=navy]npd = 16, solns = 3[/COLOR][/FONT] [FONT=Courier New][FONT=Courier New][COLOR=navy]npd = 17, solns = 1[/COLOR][/FONT] [/FONT][/code] This well-balanced pattern appears to persist across all the cases I've looked at so far .... the number of solutions with few divisors is matched by the number with many, but the former are very much easier to find, of course. The biggest D here is only about 80 bits, not much bigger than the biggest solution [I]a = [/I]19316158377073923834001 which is about 74 bits. It would be nice, wouldn't it, if the greatest [I]D[/I] required was generally not much bigger than the max solution size [FONT=Symbol][FONT=Symbol][FONT=Verdana][SIZE=3][SIZE=2]I'll try and get more info from what results I have ....[/SIZE][/SIZE][/FONT][/FONT][/FONT] |
[QUOTE=Jim White;113449]
It runs fastest of all so far, but I think that's mainly because it has a faster Pell solver - it uses various 'tricks' to speed up the Pell equation solving process (eg going directly from mid-period to fundamental solution). [/QUOTE] Thanks. Yesterday I've figured out some tricks. I'll try to rewrite my program. Do you know that period-length can be odd? All of the posted period lengths in the maximal solutions are even but there are examples when the period length of the continued fraction expansion of sqrt(n) is odd ( where n is even ). |
Yes. Ignoring the case period = 1, odd periods are particularly rare when you have even [I]D's [/I](as we do currently, under the Lehmer scheme).
Here I've reported over various runs, the maximum odd period length that turned up, and the maximum [I]D [/I]which had an odd period: [code] p= 83 <none> p= 89 Odd periods = 37 Max length pl = 31, D = 22952210 Max D pl = 27, D = 416392730 p= 97 Odd periods = 60 Max length pl = 31, D = 1715930 MAx D pl = 17, D = 3774000501602 p=101 Odd periods = 72 Max length pl = 31, D = 20402 Max D pl = 29, D = 23010564730570 p=103 <none> p=107 <none> [/code] An odd period can generally be treated as just the mid-point of an even period, I think. |
Pell CF Tricks
Regarding Pell equation (CF development, etc) efficiency, the restriction of the CF development to the mid-point is definitely worth implementing, even in our relatively short periods - it's still effective for period lengths of say, 8 or more.
This is generally known as "the mid-point trick", it seems Another trick is one that seems peculiar to this problem - if we are going to reject period lengths that exceed some max [B]L[/B], and we know that the great majority of cases will be thus rejected, then it makes very good sense to separate the CF expansion into two stages: [INDENT][B]1. Periodicity + CF Denominators[/B] - compute and store just the CF denominators, aborting any cases where periodicity is not detected in less than [B]L [/B]steps[/INDENT][INDENT][B]2. Convergents [/B]- for acceptable cases only, generate the required convergents (via the recurrence relation multipliers given by the stored CF denominators)[/INDENT]Combine with mid-point shortcut in stage [B]2, [/B]and you have program [tex]\sp[/tex] in a nutshell. That's why it's quite fast, even though some aspects are not fully optimised. We can also use size bounding, of course, during stage 2. However, it looks like what happened when I applying period length bounds to [I]your [/I]code, they didn't make any real difference, as the size bound usually triggered first. With the period-bounding method described here, it's just the opposite - by rejecting periods > [B]L[/B][I],[/I]we have already filtered out most of those that would run over size (and we have not wasted much computational effort on them at all - [I]this[/I] is the main efficiency gain) So we only develop the convergents for those guys we know that have short periods, and we can still keep an eye on the size, although we expect to find such oversize cases less often. |
Finger trouble
[quote=Jim White;113567]We can also use size bounding, of course, during stage 2.
[I]However, [U]it looks like what happened when I applying[/U] period length bounds to your code, they didn't make any real difference, as the size bound usually triggered first.[/I] With the period-bounding method described here, it's just the opposite - ... ... [/quote] Egad! Must have fallen asleep at the keyboard (again!) I'm sorry! That should read: [quote=Jim White;113567]We can also use size bounding, of course, during stage 2. If I add period length bound checks to Robert's original program, however, they don't make any real difference - his existing size bound check is almost always more effective (catches exceptions earlier) than the priod length bound. With the period-bounding method described here, it's just the opposite - [/quote] |
Prime Combinations - Ordering Choices
The set of [I]D [/I]values that we have to generate can be done in various combinatorial ways. Two examples:
[INDENT][B]1. Recursive Generation[/B] - eg: 3 -> 3,5 -> 3,5,7 -> 3,5,7,11 -> 3,5,11 -> 3,7 - > 3,7,11 -> 3,11 ==> 5 -> ... (a pre-order traversal of the combination tree)[/INDENT][INDENT][B]2. Generating Same-size Selections [/B]- this involves generating all combinations of size [B][I]k [/I][/B]for k = 1, 2, ... . So pass 1 = {3 -> 5 -> 7 -> 11}, pass 2 = {3,5 -> 3,7 -> 3,11 -> 5,7 -> 5, 11 -> 7, 11} and so on[/INDENT]The first method is very much simpler to code, and neither one makes any significant difference to running time in this problem. But the second method has at least one interesting feature - it can locate the majority of the targets in a flash! For example, with [B]n = 30 (p = 113)[/B], we are combining the 28 primes {3, 5, ... 109} to form [I]D' [/I](which we then combine with 2 and 113 in the various appropriate ways), of which there are [tex]2^{28}[/tex] possible combinations (well, give or take 1). Here's a log from a sample run showing the results for various [B]k :[/B] [code] [U][B][FONT=Courier New] k C(n,k) Solns Total run time[/FONT][/B][/U] [FONT=Courier New] 1 28, 19, 23, [/FONT] [FONT=Courier New] 2 378, 72, 95, [/FONT] [FONT=Courier New] 3 ** 3276, 191, 286, [/FONT] [FONT=Courier New] 4 ***** 20475, 415, 701, .1s [/FONT] [FONT=Courier New] 5 ****** 98280, 676, 1377, .4s[/FONT] [FONT=Courier New] 6 ********* 376740, 878, 2255, 1.7s[/FONT] [FONT=Courier New] 7 ********* 1184040, 934, 3189, 5.6s[/FONT] [FONT=Courier New] 8 ********* 3108105, 819, 4008, 15.9s[/FONT] [FONT=Courier New] 9 ***** 6906900, 575, 4583, 39.7s[/FONT] [FONT=Courier New]10 **** 13123110, 357, 4940, 92.7s[/FONT] [FONT=Courier New]11 ** 21474180, 193, 5133, 181.8s[/FONT] [FONT=Courier New]12 * 30421755, 91, 5224, 311.4s[/FONT] [FONT=Courier New]13 37442160, 36, 5260, 471.8s[/FONT] [FONT=Courier New]14 40116600, 18, 5278, 643.8s[/FONT] [FONT=Courier New]15 37442160, 3, 5281, 804.5s[/FONT] [FONT=Courier New]16 30421755, 2, 5283, 934.9s[/FONT] [FONT=Courier New]17 21474180, 1, 5284, 1026.8s[/FONT] [FONT=Courier New]18 13123110, 0, 5284, 1083.0s[/FONT] [FONT=Courier New]19 6906900, 0, 5284, 1112.7s[/FONT] [FONT=Courier New]..... [/FONT] [/code] So it took just 16 seconds to find 4000 of the 5300 odd solutions, then nearly 20 minutes to find the the rest ... The number of possible combinations that have to be considered is listed, and this gives you yet another view of the "fundamental" problem ... The "peak" solution pass seems to be around [B]n/4 [/B]for all cases I've looked at so far. If you write a generic [B]k [/B]from [B]n [/B]selection generator, then you can do the selection passes in any order you like, of course .... |
Some known tuning settings
These settings might be useful if you want to save time on a particular run:
[code] [U][B]n p D'2 S'2 v(D') v(S') L(D)[/B][/U] 25 97 64 57 13 17 26 26 101 66 63 14 17 28 27 103 72 76 15 18 28 28 107 74 60 15 19 28 29 109 77 68 16 20 32 30 113 87 69 17 20 36 31 127 81 67 16 20 32 32 131 88 73 16 21 30 33 137 88 78 17 21 30 [/code] [B]n = [/B]index([B]p[/B]) [B]D'2 [/B]= max [I]reduced [/I]producer size (bits). The reduced determinants [I]D' [/I]are the odd square-free values. ie. subsets of {3, 5, ... [I]p'[/I]}, where [I]p'[/I] is the [B]n-1[/B]'th prime. This bound can save time by helping to eliminate many of the possible divisor combinations that are supposed to be tested. [B]S'2 [/B]= max solution size (bits). If [B]S' [/B]is the max [I]S [/I]for which [I]S(S-1) [/I]is a hit, then [B]S'2 = [/B][tex]log_2(2S-1)[/tex]. Like knowing max period length, this allows Pell equation solution development to be abandoned early when known to be futile. [B][I]v[/I](D') [/B]= [I]v(N) [/I]is the number of prime divisors of N. [B][I]v[/I](D') [/B]is the highest value for any (reduced) producer [I][B]D'[/B][/I]. In other words, it's pointless combining any more than this when making any [I]D'[/I]. [B][I]v[/I](S') [/B]= the highest number of divisors of any [I]S(S-1) [/I]pair. Includes all divisors, so includes 2 and [B]p. [/B] [B]L(D) [/B]= the largest period length of any producer. [B]D'2 [/B]and [B]L(D) [/B]are very effective bounds (when known!) As an example, a current program I have takes over 1 hour to run (70 mins) for the case[B] n=[/B]32, [B]p[/B]=131, using a reasonably good period bound (these seem very predictable, eg [B]n + 10 [/B]would usually do the job). Once I have a sharper value for the period bound, and also know the size of the largest producer I need to generate, re-running the job is quicker, completing in 40 minutes. |
[SIZE=3][FONT=Times New Roman]I am also interested in this topic.[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]I searched all p34-smooth number pair by my c language program and get 63428 solutions. My arithmetic is base on a conjecture, let (n,n+1) is a p34 –smooth number pair, the max of n should at most with 128 bits. The following is the largest 16 solutions (n) that satisfy with both n and n+1 is [/SIZE][/FONT][FONT=Arial CYR]139-smooth number[/FONT] [SIZE=3][FONT=Times New Roman]107109384837019296875[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]118991993751522079210[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]152295745769656587384[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]205142063213188103639[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]507882950033870979071[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]1043073004436787852800[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]1338614896790283750000[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]1492860563840742187104[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]1805692829069444659200[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]1811103583756769555714[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]2187239579855392547199[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]2888494687736348753790[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]3482435534325338530939[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]4114304445616636016031[/FONT][/SIZE] [SIZE=3][FONT=Times New Roman]19316158377073923834000[/FONT][/SIZE] [FONT=Times New Roman][SIZE=3]124225935845233319439173[/SIZE][/FONT] |
I google number [FONT=Arial CYR]124225935845233319439173 in internet and found a table as bellow, of course, it is spectacular result. The table give the max p_n smooth nubmer pair and n up to 40. I don't understand how to search such result in very very big range. [/FONT]
[FONT=Arial CYR][FONT=Times New Roman][SIZE=3]I believe your state is reasonable. “[/SIZE][/FONT][FONT=Arial]There is a bigger 157-limit comma”[/FONT] [FONT=Arial]This table can be found from [FONT=Times New Roman][URL="http://www.primefan.ru/stuff/math/maxs.xls"][COLOR=#800080]www.primefan.ru/stuff/math/maxs.xls[/COLOR][/URL][/FONT][/FONT][/FONT] [QUOTE] Index p k=1 (A002072) 1 2 1 2 3 8 3 5 80 4 7 4374 5 11 9800 6 13 123200 7 17 336140 8 19 11859210 9 23 11859210 10 29 177182720 11 31 1611308699 12 37 3463199999 13 41 63927525375 14 43 421138799639 15 47 1109496723125 16 53 1453579866024 17 59 20628591204480 18 61 31887350832896 19 67 31887350832896 20 71 119089041053696 21 73 2286831727304144 22 79 9591468737351909375 23 83 9591468737351909375 24 89 9591468737351909375 25 97 9591468737351909375 26 101 9591468737351909375 27 103 19316158377073923834000 28 107 19316158377073923834000 29 109 19316158377073923834000 30 113 19316158377073923834000 31 127 19316158377073923834000 32 131 19316158377073923834000 33 137 124225935845233319439173 34 139 124225935845233319439173 35 149 124225935845233319439173 36 151 124225935845233319439173 37 157 6318268857746831540296874 38 163 6318268857746831540296874 39 167 6318268857746831540296874 40 173 6318268857746831540296874 [/QUOTE] |
You (or the guy behind of primefan.ru) should report that [URL="http://oeis.org/A002072/list"]here[/URL].
My feeling is that the list would not be very difficult to extend, I will give it a try in pari if I find some free time over teh weekend. |
Basically, total 4 OEIS is related with this topic. They are A117581, A002072, A002071 and A145606.
let both m and m+1 is P(n)-smooth number, then A002072= max(m) for each of P(n) smooth number pair, and A117581=max(m+1), so A117581 [i] = A002072[i]+1. The A002071 is number count for all of m which satisfy m and m+1 is P(n) smooth number. The A145606 denote that largest number x such that x and x+1 are prime(n)-smooth but not prime(n-1)-smooth. It is said in both A14506 and A002072 "Jim White, Results to P = 173". If the OEIS owner thinks Jim White's result and computation method is exactly correct, then all of these 4 serial should extend to 40 term. But I think that because Jim White's computation method base on a conjecture, the upperbound should less than a const and this upperbound can not been prove by mathematical theorem, so only a part of serial be given. Jim White, If I am wrong, please correct me. |
[QUOTE=Jim White;113248]It makes sense to start a specific thread for this topic, I think ..
The discussion developed originally in this thread [URL]http://www.mersenneforum.org/showthread.php?t=5647[/URL] I'll start this thread by reproducing my first posting there, which has some useful data, and also give a simple definition of the problem for newcomers: [B][U]Størmer's Problem (1897)[/U][/B] [SIZE=3][COLOR=black]Write [I][B]gpd[/B][/I]([I][B]n[/B][/I]) for the greatest prime divisor of [I][B]n[/B][/I][/COLOR][/SIZE] [COLOR=black][SIZE=3]Given some prime [B]p[/B], [/SIZE][SIZE=3]for which [I][B]n[/B][/I] do we have [I][B]gpd[/B][/I]([B]n[/B]([B]n[/B]-[B]1[/B])) <= [B]p[/B]? [/SIZE][/COLOR] We can refer to the set of all such values of [B][I]n [/I][/B]for given [B]p [/B]as [FONT=Courier New][SIZE=3][COLOR=#000080][FONT=Verdana][SIZE=2][COLOR=black][B]S(p)[/B], and [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][SIZE=3][COLOR=#000080][SIZE=2][COLOR=black][B]S'[/B]([B]p[/B])[/COLOR][/SIZE] [/COLOR][/SIZE]for the [I]maximum[/I] value [B][I]n [/I][/B]for which [B][I]gpd[/I][/B]([B]n[/B]([B]n[/B]-[B]1[/B])) [B]=[/B] [B]p [/B](note that these sets are demonstrably [I]finite, [/I]and so [B]S'[/B]([B]p[/B]) always exists). The pairs ([B]n[/B],[B] n-1[/B]) are obviously representable as (twice the value of) triangular numbers, via their product, and are also known in musical interval theory as [I]Superparticular Ratios, [/I]when represented as rational quotients [B]n / n-1 [/B](these ratios are highly composite, and are as close to possible to 1) ======================================================= OEIS sequences [B]A002072[/B] and [B]A117581[/B] both list the sequence [B]S'(p)[/B], only the first one lists the lower value of each pair, ie [B]S'(p) - 1[/B] Using the higher value is preferable, I think, since the only published tables, the 1964 results of Dick Lehmer ("On a Problem of Størmer", [I]Illinois J. Math[/I], [B]8[/B], 1964, pp 57-79), for [B]p [/B]up to 41,use that convention. Also his proofs are given in the same terms, and it corresponds to the convention used by the muso's. Both sequences as recorded in OEIS have an inconvenient feature, though - there are duplicate values in the sequence, in order (presumably) to keep the sequence increasing. But this omits useful information. If we ask what is [B][I]S'[/I](23)[/B], the [I]greatest[/I] value of S for which [I]gpd [/I](S(S-1)) = 23? The answer is 5142501, but this is [I]less[/I] than [B][I]S'[/I](19) = [/B]11859211, so it does not appear in the sequence, the latter value is just repeated. Here is a list which applies the definition of [B][I]S'[/I](p) [/B]strictly, and which extends the sequence to the 35th prime (149): [code] [SIZE=3][FONT=Courier New][COLOR=navy]N p S'(p) 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] Jim White Math. Sciences Institute Australian National University[/QUOTE] brute force is basically: [CODE]gpd(y) = factor(y)[#factor(y)[,1],1][/CODE] and a infinite loop of values to check, a less brute force is knowing that for all all primes q<p , all values q*x for x<p are in the set also all powers q^y for q<p are in the set which lead to an infinite set. |
[QUOTE=LaurV;293177]You (or the guy behind of primefan.ru) should report that [URL="http://oeis.org/A002072/list"]here[/URL].[/QUOTE]The guy behind of primefan.ru is me :-)
I already reported these results here: [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] There are numbers [TEX]n[/TEX] such that [TEX]p(n,k) < p(i,k)[/TEX] for all [TEX]i > n[/TEX], where [TEX]p(n,k)[/TEX] is the largest prime factor of [TEX]\prod\limits_{d=0}^k (n+d)[/TEX]. Note that [TEX]log n[/TEX] grows nearly as [TEX]\sqrt{p(n,k)}[/TEX] irrespective of [TEX]k[/TEX]: [url]http://www.primefan.ru/stuff/math/maxs_plots.gif[/url] (the plot is taken from the Excel file noted before) For [TEX]k=1[/TEX], the case being discussed there, we have [TEX]\log{n} \approx 5.154\sqrt{p} + 7.276[/TEX]. Any thoughts about these constants? |
27129807647978258459761875 * 27129807647978258459761876 is 157-smooth, according to [url]http://bbs.emath.ac.cn/thread-4652-1-1.html[/url]
683232593267939977798585217 * 683232593267939977798585218 is 173-smooth, according to [url]http://forum.index.hu/Article/showArticle?go=40456539&t=9087484[/url] See also [url]http://doi.org/10.1090/S0025-5718-2010-02381-6[/url] and [url]http://dx.doi.org/10.1080/10586458.2013.768483[/url] |
| All times are UTC. The time now is 10:47. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.