Smooth power trios - Page 5

grandpascorpion · 2007-08-30, 14:44

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

Jim White · 2007-08-30, 22:48

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

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 incrementally, 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)

XYYXF · 2011-08-01, 16:00

Quote:

Originally Posted by Jim White

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

Code:

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

That is A145606: http://oeis.org/A145606

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:
http://oeis.org/A003032

The similar sequence is A003033, where the chains of length 4 are considered:
http://oeis.org/A003033
(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:
http://www.primefan.ru/stuff/math/maxs.xls

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

XYYXF · 2011-08-08, 06:45

Quote:

Originally Posted by XYYXF

The better would be log(n)/sqrt(p), and the largest currently known is

log(407498958)/sqrt(89) = 2.1015

Oops, log(138982582998)/sqrt(103) = 2.52812 is larger.

XYYXF · 2011-08-11, 15:18

Smooth pairs up to p=173 are reported there by Jim White:
http://11011110.livejournal.com/9732...351533#t351533

XYYXF · 2014-11-11, 21:49

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

Conjecture:
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:
http://oeis.org/A193943
http://oeis.org/A193944
http://oeis.org/A193945
http://oeis.org/A193946
http://oeis.org/A193947
http://oeis.org/A193948
http://oeis.org/A199407
http://oeis.org/A200566
http://oeis.org/A200567
http://oeis.org/A200568
http://oeis.org/A200569
http://oeis.org/A200570
http://oeis.org/A209837
http://oeis.org/A209838
http://oeis.org/A209839

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.

2011-08-11, 15:18	#49
XYYXF Jan 2005 Minsk, Belarus 2⁴×5² Posts	Smooth pairs up to p=173 are reported there by Jim White: http://11011110.livejournal.com/9732...351533#t351533 Last fiddled with by XYYXF on 2011-08-11 at 15:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Not smooth enough numbers	Sam Kennedy	Factoring	5	2012-11-10 07:54
Remove the Smooth 2012	c10ck3r	Math	12	2012-09-18 12:38
Smooth Numbers	Yamato	Math	1	2005-12-11 11:09
NFS and smooth norm MOD N ?	bonju	Factoring	9	2005-08-26 13:29
Smooth?	Xyzzy	Factoring	5	2004-11-04 18:20

2007-08-30, 14:44	#45
grandpascorpion Jan 2005 Transdniestr 503 Posts	Good point Jim. Did you convert the script to C or just run it in Python?

2007-08-30, 22:48	#46
Jim White Aug 2007 Canberra, Australia 100001₂ Posts	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 ... 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 incrementally, 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)

2014-11-11, 21:49	#50
XYYXF Jan 2005 Minsk, Belarus 2⁴×5² Posts	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 Conjecture: 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: http://oeis.org/A193943 http://oeis.org/A193944 http://oeis.org/A193945 http://oeis.org/A193946 http://oeis.org/A193947 http://oeis.org/A193948 http://oeis.org/A199407 http://oeis.org/A200566 http://oeis.org/A200567 http://oeis.org/A200568 http://oeis.org/A200569 http://oeis.org/A200570 http://oeis.org/A209837 http://oeis.org/A209838 http://oeis.org/A209839 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.