0xDE ([info]11011110) wrote,
@ 2007-03-23 16:40:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Entry tags:number theory, smooth numbers, stormer's theorem

Smooth pairs
All pairs of consecutive 47-smooth numbers, calculated by my Python code for Lehmer's improvement to Størmer's theorem. That is, this file lists pairs x, x+1 such that all prime factors of both x and x+1 are at most 47. There are 1502 such pairs, the largest of which is formed by 1109496723125 = 54 × 7 × 17 × 192 × 312 × 43 and 1109496723126 = 2 × 3 × 112 × 23 × 292 × 412 × 47.

It took nearly two days on a dual-core Pentium, so the next prime 53 may be in reach but would likely take more computer time than I'm willing to devote to it. Judging by A002072, faster codes are out there.


(14 comments) - (Post a new comment)


[info]leonardo_m
2007-03-24 11:51 am UTC (link)
There was a gmp-d library to use the multiprecision GMP with D, but it seems vanished.
But your program look simple enough, so maybe you can translate it to C that calls the GMP (I use GMP with Python + Psyco, but if you have many small numbers it's not a significative improvements on the python built-in longs).
ShedSkin doesn't support GMP yet, but maybe it's not difficult to use it.

(Reply to this) (Thread)

[info]11011110
2007-03-24 11:09 pm UTC (link)
I did make one change to my code since running the computation that should speed things up significantly: if the first solution to a given Pell equation is already not smooth, the rest of them for the same equation won't be either, so we can stop early. As there are 32768 Pell equations (for the 47-smooth calculation) but only 1502 smooth pairs, this early escape should happen very frequently.

(Reply to this) (Parent)(Thread)
Lehmer's Method
[info]mathimagics
2007-07-12 11:42 am UTC (link)
For the record, Lehmer did make this point clear - in Section 6 (Implementation notes) he says "since every y[n] is divisible by y[1], it is useless to examine multiple solutions if y[1] ... [is not smooth]"

Fixing this will not necessarily translate into dramatic speed increases in your program - the additional imposed cost of iterating the multiple solutions, assuming you check no more than M as specified, is likely to be modest compared wih the cost of computing the Pell solution.

For maximum speed clearly GMP (suitably CPU-targeted) is going to give the best results on most common CPU's.

Here are my times recently recorded for P = 47 and similar cases. The test rig is an AMD64 2.2 GHz.

Columns are no of primes, highest P, number of eqns, NS = number of pairs found, job time (seconds).

13 p = 41 8K NS = 869, .870 s
14 p = 43 16K NS = 1153, 7.490 s
15 p = 47 32K NS = 1502, 78.910 s
16 p = 53 64K NS = 1930, 1163.150 s
17 P = 59 128K NS = 2454, 15153~ 4hrs
18 P = 61 256K NS = 3106, 144838~ 40hrs

The first couple of runs look good, but the growth in cost of 10x per additional prime is the dominant, and crippling feature ... and that value "10" may also tutn out to be growing ...

Each extra prime doubles the number of equations, but also raises the average "weight" of the D values, so numbers and periods get heavier and heavier....

And, as you may have already realised, you can't handle each additional prime "incrementally" - if I have all 43-smooth pairs, and want to get the additional ones for 47, I still have to redo all the previous equations (with D 43-smooth) as some of them will produce 47-smooth pairs

So while an incremental approach (forcing 47 as a divisor of D) will generally identify _most_ new solutions, it will not be complete.

I don't totally understand why A002071 only lists counts for up to P = 47, yet A002072 lists maximum pair values for up to P = 97.

I sent an enquiry to eppstein (as A002071 suggests), but have had no reply ... from my results, one wonders just how long the A002071 results took to produce, and just how it was done

I'll try another enquiry, this time to Fred Schneider ... see if he has some tricks up his sleeve?

Cheers

(Reply to this) (Parent)(Thread)
Re: Lehmer's Method
[info]mathimagics
2007-07-12 11:44 am UTC (link)

Erratum: "one wonders just how long the A002072 results took ...."

(Reply to this) (Parent)
Re: Lehmer's Method
[info]11011110
2007-07-12 03:53 pm UTC (link)
I don't totally understand why A002071 only lists counts for up to P = 47, yet A002072 lists maximum pair values for up to P = 97.

I sent an enquiry to eppstein (as A002071 suggests), but have had no reply

That would be me. I've been traveling and largely away from my email. Though in the best of times I've been known not to reply to my emails...

Anyway, A002072 links to some code by Don Reble that may have been used to compute it — if so, I don't know why it would be so much faster than the code I used to compute the additional terms in A002071.

(Reply to this) (Parent)(Thread)
Re: Lehmer's Method
[info]mathimagics
2007-07-12 09:37 pm UTC (link)

Hello David!

I clearly failed to notice the significance of your user id "0xDE", it does not signify Diophantine (or DIfferential) Equations! :-)

I thought perhaps my email enquiry might have been skimmed by a spam-detector (understandable in these times) ...

My recent progress: I have computed the complete solution sets up to n=13 (p <=97), and the maximum values I encountered do tally with those givem in A002702 (which, by the way, I would prefer to see give the explicit maximal value for each prime, rather than repeating values)

The program I've developed took only 2 mins to do this, and involves a growth factor of just 2+e rather than 10+e for each additional prime.

The 40 hours it cost to produce the results for n=18 (p<=61) should now buy me a solution set for n=31 (p<=127), and I have just started a run with that in mind.

My values for A002071 for n=13 to 25 are:

13 p = 41 NS = 869
14 p = 43 NS = 1153
15 p = 47 NS = 1502
16 p = 53 NS = 1930
17 P = 59 NS = 2454
18 P = 61 NS = 3106
19 P = 67 NS = 3896
20 P = 71 NS = 4839
21 P = 73 NS = 6040
22 P = 79 NS = 7441
23 P = 83 NS = 9179
24 P = 89 NS = 11134
25 P = 97 NS = 13374

a) Are you able to confirm any of these?

b) Are you aware of any known values beyond n=25, p=97? One of the problems with my method is that (currently) it is not yet provably correct - I need to sharpen Lehmer's "Theorem" before I can claim the p=127 results will be definitive. Meantime all I can say is that they will almost certainly be correct!

This work is not purely for fun - my current research is motivated by a broader practical application, in which one approach to the problem is dependent on having an "efficient" method of finding these "smooth-pairs".


Cheers
0xJW
(MSI, ANU, Canberra)

(Reply to this) (Parent)(Thread)
Re: Lehmer's Method
[info]11011110
2007-07-13 06:34 am UTC (link)
Are you able to confirm any of these?

The first three terms you already know from A002071. I'm not really in a position to do anything compute-intensive while traveling. But given the 10x growth in my code's runtime it seems that it might take several days to compute even the next term after that.

(Reply to this) (Parent)(Thread)
Re: Lehmer's Method
[info]mathimagics
2007-07-13 10:20 am UTC (link)

No need to waste any time on it, then ...

I'll send those figures over to Mr Schneider (last indicated correspondent at A002072) for comment ...

Regarding the "express method", this is not a new method, just a nice refinement of Lehmer's method.

I only "discovered" the trick a few days ago, hence the uncertainty as to its verifiability ... I've been preoccupied with its implementation and performance ... I am devoting this weekend, however, to a look at whether it can be shown to be correct, since ...

I'm giving an informal talk (as PhD candidates are obliged to do from time to time) on Monday, and I now wish to abandon my previous topic and talk about this fascinating problem ...

so I'll be knocking up some notes, which I should be able to provide shortly after...


Cheers
0xJW

(Reply to this) (Parent)
Results to p = 127
[info]mathimagics
2007-07-13 02:04 am UTC (link)

The job for n=31, p <= 127, took just 3h 20m.

Predicted A00271 terms:

P = 97 NS = 13374
P = 101 NS = 16167
P = 103 NS = 19505
P = 107 NS = 23361
P = 109 NS = 27939
P = 113 NS = 33208
P = 127 NS = 39240

Cheers
0xJW

(Reply to this) (Thread)
Re: Results to p = 127
[info]mathimagics
2007-07-13 06:56 am UTC (link)

Errata:

When setting up that job, I missed a "section", in which 43 additional pairs were to be found (a sparsely populated section it was, too, requiring 2 further hours to check).

P = 97 NS = 13374, max = 49956990469100001
P = 101 NS = 16167, max = 4108258965739505500
P = 103 NS = 19508, max = 19316158377073923834001
P = 107 NS = 23372, max = 386539843111191225
P = 109 NS = 27956, max = 90550606380841216611
P = 113 NS = 33250, max = 205142063213188103640
P = 127 NS = 39312, max = 53234795127882729825


max for each P is the value s+1 in the highest pair (s, s+1), with P dividing either s or s+1.

(Reply to this) (Parent)(Thread)
Re: Results to p = 127
(Anonymous)
2008-10-13 08:31 pm UTC (link)
Note that for p=97 (the 25th prime), max=49956990469100001 is smaller than A002072(25)=166055401586083680. Someone is wrong.

(Reply to this) (Parent)(Thread)
Re: Results to p = 127
[info]11011110
2008-10-13 08:54 pm UTC (link)
166055401586083680 gives an 89-smooth solution. Maybe the max reported by [info]mathimagics is only among solutions in which 97 is one of the actual factors?

(Reply to this) (Parent)(Thread)
Re: Results to p = 127
[info]mathimagics
2008-10-14 10:11 am UTC (link)
Indeed, I did say "with P dividing s(s+1)" ...

(Reply to this) (Parent)
Results to P =173
[info]mathimagics
2008-10-14 10:54 am UTC (link)
Here are my latest results for P=101 to 173

n P(n) Count Total Largest found
26: 101 2793 16167 4108258965739505500
27: 103 3340 19507 19316158377073923834001
28: 107 3860 23367 386539843111191225
29: 109 4582 27949 90550606380841216611
30: 113 5284 33233 205142063213188103640
31: 127 6050 39283 53234795127882729825
32: 131 6883 46166 4114304445616636016032
33: 137 7984 54150 124225935845233319439174
34: 139 9278 63428 3482435534325338530940
35: 149 10579 74007 6418869735252139369210
36: 151 12118 86125 5937710767815990134896
37: 157 13957 100082 6318268857746831540296875
38: 163 15722 115804 2360921292131204442428217
39: 167 18138 133942 2730144006466475742187500
40: 173 20384 154326 811150370266636218705705

None of these results would be possible without a bailout feature in my program that ignores any CF whose period exceeds a given parameter. I've been running with maxperiod = 60 and have yet to see a "hit" involving a period length of more than 42.

Unfortunately there are no available results in Number Theory that either suggest some period limit, or explain why it is that all "hits" have such exceptionally short periods.

So for now, all I can say about my counts is that they are lower-bounds - theoretically more examples in each prime category might well exist.

By the way, even with a period-limit, the job-size is growing expoentially -it took about a week on an AMD64 2.2GHz to get the P=173 set ...

Finally, you can see from the up-and-down fluctuation of the largest pair identifiers why A002072 might be better if changed to indicate these values instead of what it does now.

(Reply to this)

(14 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…