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

[snip]

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

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

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