- Hi Mike,

You're right I like the second ranking better ;-)

rank k d s=(k+4)*log(d)

---- - - --------------

1 8 1057 83.558

5 5 7009 79.695

9 7 1290 78.786

10 9 425 78.677

11 10 265 78.116

15 4 11961 75.115

19 6 1606 73.815

Having found the above APs I tend to agree with your difficulty ranking. The AP8 was definitely the hardest.

cheers

Ken

--- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:

>

> --- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@> wrote:

> >

> > The "score" for an AP-k with d digits is defined to be:

> > s = (k+3)*log(d)

> [snip]

>

> I retract yesterday's post.

>

> Further reflection and numerical experiments have shown that using "(k+3)" is no better than using "(k+4)",

> and it is the latter that has a theoretical motivation, as follows.

>

> A typical search method is to sieve and then test for primality a block of N numbers of the form m*p#+1,

> for some fixed prime p and N consecutive values of m.

> If the numbers are of size d digits, then by PNT a fraction of about 1/d of the numbers will be prime.

> In this block of N, there will be approximately (N/d) primes, and 0.5*(N/d)^2 prime pairs.

> Considering each of these pairs as the start of a potential AP-k, the number of AP-k's will be of order N^2/d^k.

> For a search to get an even chance of finding an AP-k, we must have N^2/d^k of order 1, i.e. N=d^(k/2).

> To perform a primality test on a number of size d digits is of difficulty approximately d^2 (neglecting terms of order log(d)).

> The amount of computation involved in finding an AP-k is therefore of order N*d^2=d^(k/2+2).

> The log of this (if we multiply by 2) is (k+4)*log(d).

>

> We therefore define the "score" for an AP-k with d digits to be

> s = (k+4)*log(d)

>

> NB If factors of order 1 are neglected, this coincides with Chris Caldwell's definition of weight on his "Arithmetic Progressions of Primes" page

> http://primes.utm.edu/top20/page.php?id=14

> where he presents a detailed theoretical justification, with references, for the algebraic expression he uses.

>

> Inserting the latest records from Jens's page

> http://users.cybercity.dk/~dsl522332/math/aprecords.htm

> gives this table:-

>

> k d log(d) s=(k+4)*log(d)

> - - ------ --------------

> 3 137514 11.831 82.817

> 4 11961 9.3894 75.115

> 5 7009 8.8550 79.695

> 6 1606 7.3815 73.815

> 7 1290 7.1624 78.786

> 8 1057 6.9632 83.558

> 9 425 6.0521 78.677

> 10 265 5.5797 78.116

> 11 195 5.2730 79.095

> 12 173 5.1533 82.453

> 13 78 4.3567 74.064

> 14 69 4.2341 76.214

> 15 48 3.8712 73.553

> 16 38 3.6376 72.752

> 17 29 3.3673 70.713

> 18 29 3.3673 74.081

> 19 27 3.2958 75.803

> 20 21 3.0445 73.068

> 21 20 2.9957 74.893

> 22 19 2.9444 76.554

> 23 19 2.9444 79.499

> 24 17 2.8332 79.330

> 25 17 2.8332 82.163

>

> The mean score is 77.166, the median is 76.554 (for k=22).

> The range of values is 70.713..82.817, giving a spread of 12.104,

> which is better than the spread with "(k+3)" of 13.604.

> This new fit has also a smaller relative variance: 0.002085 compared with 0.002258.

>

> Putting c=76.554, the values of d = exp(c/(k+4)) giving that same score would be as follows:-

>

> k d(theor.) d(actual)

> - --------- ---------

> 3 56178.293 137514

> 4 14317.674 11961

> 5 4944.3461 7009

> 6 2112.0198 1606

> 7 1053.0590 1290

> 8 589.63282 1057

> 9 360.96075 425

> 10 237.01960 265

> 11 164.61345 195

> 12 119.65648 173

> 13 90.303523 78

> 14 70.316044 69

> 15 56.213554 48

> 16 45.956716 38

> 17 38.299183 29

> 18 32.450871 29

> 19 27.894646 27

> 20 24.282356 21

> 21 21.373674 20

> 22 18.998967 19

> 23 17.036078 19

> 24 15.395441 17

> 25 14.010305 17

>

> The rank-ordering is considerably different than when "(k+3)" was used in the formula. The new ordering is:-

>

> rank k d s=(k+4)*log(d)

> ---- - - --------------

> 1 8 1057 83.558 was 3rd

> 2 3 137514 82.817 was 14th

> 3 12 173 82.453 was 2nd

> 4 25 17 82.163 was 1st

> 5 5 7009 79.695 was 15th

> 6 23 19 79.499

> 7 24 17 79.330

> 8 11 195 79.095

> 9 7 1290 78.786 was 13th

> 10 9 425 78.677

> 11 10 265 78.116

> 12 22 19 76.554 MEDIAN

> 13 14 69 76.214

> 14 19 27 75.803

> 15 4 11961 75.115 was 23rd

> 16 21 20 74.893

> 17 18 29 74.081

> 18 13 78 74.064

> 19 6 1606 73.815 was 22nd

> 20 15 48 73.553

> 21 20 21 73.068

> 22 16 38 72.752

> 23 17 29 70.713

>

> The main changes are that the records with smaller k have moved up in the rankings - for k=3, dramatically so!

> The k=4 and k=6 records don't now look quite so relatively weak (which should please Ken:-)

>

> The rank order now agrees with Chris's in his above-cited page, for d > 1000 (the lower limit for inclusion in his table).

>

> Mike

> - --- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:
>

That was as per 6 Jun.

> Inserting the latest records from Jens's page

> http://users.cybercity.dk/~dsl522332/math/aprecords.htm

> gives this table:-

>

> rank k d s=(k+4)*log(d)

> ---- - - --------------

> 1 8 1057 83.558

> 2 3 137514 82.817

> 3 12 173 82.453

> 4 25 17 82.163

> 5 5 7009 79.695

> 6 23 19 79.499

> 7 24 17 79.330

> 8 11 195 79.095

> 9 7 1290 78.786

> 10 9 425 78.677

> 11 10 265 78.116

> 12 22 19 76.554 MEDIAN

> 13 14 69 76.214

> 14 19 27 75.803

> 15 4 11961 75.115

> 16 21 20 74.893

> 17 18 29 74.081

> 18 13 78 74.064

> 19 6 1606 73.815

> 20 15 48 73.553

> 21 20 21 73.068

> 22 16 38 72.752

> 23 17 29 70.713

>

Just over 5 months on, the revised table is:-

rank k d s=(k+4)*log(d)

---- - - ------ -------

1 8 1057 83.558

2 3 137514 82.817

3 12 173 82.453

4 25 17 82.163

5 5 7009 79.695

6 24 18 80.930

7 23 19 79.499

8 11 196 79.172

9 7 1290 78.786

10 9 425 78.677

11 10 274 78.584

12 17 42 78.491 was 23rd

13 6 2145 76.709 was 19th

14 22 19 76.554

15 14 69 76.214

16 19 27 75.803

17 15 54 75.791 was 20th

18 4 11961 75.115 was 15th

19 21 20 74.893 was 16th

20 16 42 74.753

21 18 29 74.081 was 17th

22 13 78 74.064 was 18th

23 20 21 73.068

Note that the lowest score was 70.713 and is now 73.068.

The comments are against k values which have changed rank by more than 2.

The first 11 positions are almost unchanged.

The latest table might help in suggesting to people (but perhaps I shouldn't be giving these clues:-) which records to try for next.

-Mike Oakes