consecutive pairs of smooth numbers

liangbch

题目解释，可直译为"相邻的光滑数对儿".
描述，如x和x+1都是p阶光滑数，则数x,x+1为一对儿相邻的p阶光滑数对儿。
p阶光滑数的定义：若n的所有素因子都不超过p，则n为p阶光滑数。

由 Stormer's  theorem 可知，对所有素数p，相邻的p阶光滑数是有限的。若p是第k个素数，找出所有的相邻的p阶光滑数对儿需要解2^k方个方程，故复杂度为o(2^k).

参考文献：
1. Stormer's  theorem, http://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem
2. Smooth number,  http://en.wikipedia.org/wiki/Smooth_numbers

liangbch

关于此问题，我能在互连网上找到的链接如下。
http://11011110.livejournal.com/97325.html
http://tech.groups.yahoo.com/group/tuning-math/message/16692
http://www.mersenneforum.org/showthread.php?t=9159
http://www.primefan.ru/stuff/math/maxs.xls

liangbch

关于这个问题，两个主要的贡献者是
David Eppstein : Professor of Computer Science at University of California Irvine.
Jim White,  Math. Sciences Institute Australian National University (Canberra, Australia)

其最新进展来自于Jim White，见http://11011110.livejournal.com/97325.html?thread=351533#t351533，在这个帖子中，他宣称，173-smooth number pair 共有154326。见下

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.

我独立的编写了c程序，做类似的计算，试图找出所有的 173-smooth number pair。等于是对Jim White的一个验证。Jim White 说，在 AMD64 2.2GHz 电脑上需要计算一星期，我的程序则需要计算8个月。不过，Jim 在解Pell方程时的剪枝条件是限定连分数的周期（限定连分数的周期为60)。而我的剪枝条件是解大于2^127，一旦发现Pell方程的解会大于2^127，则放弃计算。

liangbch

这里列出关键字，便于搜索引擎抓到
number theory
smooth numbers
stomer's theorem
Pell Equation
Continued fraction

liangbch

I have just found a number 683232593267939977798585217, it shows that Jim White's search is not entire.

liangbch

683232593267939977798585217 = 7 * 19 * 31^2 * 37^2 * 43 * 53^2 * 61 * 71^3 * 89 * 127 * 131
683232593267939977798585218 = 2 * 3^4 * 13 * 23 * 47 * 67^2 * 107^2 * 113^3 * 149 * 157 * 173

liangbch

Another number , was not reported by Jim white.
27129807647978258459761875

27129807647978258459761875 = 3^4 * 5^4 * 7 * 17 * 41 * 47 * 53^2 * 71 * 97^2 * 103 * 107 * 113
27129807647978258459761876 = 2^2 * 13 * 23^2 * 31 * 43 * 59 * 67 * 73 * 89^2 * 101 * 137 * 149 * 157

liangbch

已经找到153799个数，距离目标（Jim 给出的）154326还差527个。

liangbch

已经找到153924个数，距离目标（Jim 给出的）154326还差402个。

liangbch

今天收成不好，只找到18个数，找到consecutive pairs of smooth numbers 总数达到153942.