 Prime numbers and primality testing

 Restricted Group,
 1109 members
How hard is it to find an APk?
Expand Messages
 0 Attachment
Jens Kruse Andersen's very nice "Primes in Arithmetic Progression Records" page at:
http://users.cybercity.dk/~dsl522332/math/aprecords.htm
lists "The largestknown APk", for k=3..25.
The number of digits range from 137514 (k=3) to 17 (k=25).
I have played around with simple formulae to smoothly interpolate this huge range of sizes, and offer the following, which gives a surprisingly close fit over the whole range.
The "score" for an APk with d digits is defined to be:
s = (k+3)*log(d)
Inserting the latest records from Jens's page gives this table:
k d log(d) s=(k+3)*log(d)
   
3 137514 11.831 70.989
4 11961 9.3894 65.726
5 7009 8.8550 70.840
6 1606 7.3815 66.434
7 1290 7.1624 71.624
8 1057 6.9632 76.595
9 425 6.0521 72.625
10 265 5.5797 72.536
11 195 5.2730 73.822
12 173 5.1533 77.299
13 78 4.3567 69.707
14 69 4.2341 71.980
15 48 3.8712 69.682
16 38 3.6376 69.114
17 29 3.3673 67.346
18 29 3.3673 70.713
19 27 3.2958 72.508
20 21 3.0445 70.024
21 20 2.9957 71.898
22 19 2.9444 73.611
23 19 2.9444 76.555
24 17 2.8332 76.497
25 17 2.8332 79.330
The average score is 72.063, and the median is 71.898 (for k=21).
Putting c=71.898, the values of d = exp(c/(k+3)) giving that same score would be as follows:
k d
 
3 160011.345
4 28886.8819
5 8000.42545
6 2947.36452
7 1325.83801
8 689.648341
9 400.014181
10 252.299124
11 169.961413
12 120.686950
13 89.4450973
14 68.6687430
15 54.2896355
16 43.9962878
17 36.4120586
18 30.6831697
19 26.2611565
20 22.7826664
21 20.0003545
22 17.7417390
23 15.8839266
24 14.3376492
25 13.0369250
Comparison of these 2 tables indicate that, in terms of this fit, the k=25 record (79.330) fills the top spot, which seems reasonable (it is indeed very impressive!),
while Jeff AndersonLee's record for k=12 (77.299) and Ken Davis's for k=8 (76.595) take the next 2 places.
Further corroboration that my measure is on the right track is that Ken's record heads the table of "Weighted Record Primes of this Type" on Chris Caldwell's "Arithmetic Progressions of Primes" page
http://primes.utm.edu/top20/page.php?id=14
At the other end of the scale, Ken's records for k=4 (65.726) and k=6 (66.434) look rather weak.
Back in 2006 I held both these, and as a result of this little exercise have decided to have a go at a major upgrade of the k=6 record.
The PFGW run will take 7 more weeks (at 3.79 GHz) to finish.
I'm also attacking the 3rdweakest (k=17).
Who wants to have a crack at some of the other ("weaker") ones?
Mike Oakes 0 Attachment
 In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:>
[snip]
> The "score" for an APk 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 APk, the number of APk's will be of order N^2/d^k.
For a search to get an even chance of finding an APk, 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 APk 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 APk 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 rankordering 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 abovecited page, for d > 1000 (the lower limit for inclusion in his table).
Mike 0 Attachment
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 APk 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 APk, the number of APk's will be of order N^2/d^k.
> For a search to get an even chance of finding an APk, 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 APk 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 APk 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 rankordering 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 abovecited page, for d > 1000 (the lower limit for inclusion in his table).
>
> Mike
> 0 Attachment
Hi Mike,
Having now "carefully" read your posting and while still thinking that the end result gives a good indication of difficulty I have questions about the statement "If the numbers are of size d digits, then by PNT a fraction of about 1/d of the numbers will be prime. If the numbers are of size d digits, then by PNT a fraction of about 1/d of the numbers will be prime"
Firstly doesn't the prime number theorem that for a number N the probability of a random number N being prime is
~= 1/log(N)
~= 1/dlog(10)
so for a random 265 digit number the chance of it being prime would be
~= 1/610.185
Secondly using p# further increases this probability.
= (1/(dlog(10))*(1/2*2/3*4/5*....*p1/p))
So for a 265 digit number of the form 617#+1 the probability would be
= 1/53.12 (not 1/265)
As a practical comparison for the ap10 mentioned (with 265 digits) I found 18,894,798 prps out of 1,000,000,000 candidates meaning that 1/52.92 numbers were prps
With the 1057 digit numbers used for the ap8 ~= 1/174 were prps
Does this affect the rest of your calculations?
Cheers
Ken 0 Attachment
 In primenumbers@yahoogroups.com, "Ken Davis" <kradenken@...> wrote:>
Quite right, Ken.
> Hi Mike,
>
> Having now "carefully" read your posting and while still thinking that the end result gives a good indication of difficulty I have questions about the statement "If the numbers are of size d digits, then by PNT a fraction of about 1/d of the numbers will be prime.
> Firstly doesn't the prime number theorem that for a number N the probability of a random number N being prime is
> ~= 1/log(N)
> ~= 1/dlog(10)
> so for a random 265 digit number the chance of it being prime would be
> ~= 1/610.185
I saw the sloppy wording just after hitting "Send", but thought I would wait till someone commented rather than send a trivial correction.
In fact, my "score" function would only have gained an overall factor of log(10), and since such factors have been removed (they make no difference to the goodness of fit and there is anyway another suppressed factor from the d^2 difficultyofprimalitytesting aspect), that will not affect anything.
> Secondly using p# further increases this probability.
This is a *much" harder one!
> = (1/(dlog(10))*(1/2*2/3*4/5*....*p1/p))
> So for a 265 digit number of the form 617#+1 the probability would be
> = 1/53.12 (not 1/265)
> As a practical comparison for the ap10 mentioned (with 265 digits) I found 18,894,798 prps out of 1,000,000,000 candidates meaning that 1/52.92 numbers were prps
> With the 1057 digit numbers used for the ap8 ~= 1/174 were prps
>
> Does this affect the rest of your calculations?
I have been exercised on this aspect ever since starting APk searches at the start of 2006  and no doubt you have too!
We need a description of what is happening when we choose the candidate integers from an AP rather than a contiguous set, don't we?
After about 3 days more or less continuous reflection and computer experimentation I think I have at last completely cracked this problem.
I have a HardyLittlewoodtype conjecture which does exactly what we want (and is able to predict your AP8 stats to an extraordinary degree of precision:)
A post on all that is in preparation.
Thanks for your encouragement.
Mike Oakes 0 Attachment
 In primenumbers@yahoogroups.com,
"Mike Oakes" <mikeoakes2@...> wrote:
> After about 3 days more or less continuous reflection and
Yum, yum! My saliva buds are already working.
> computer experimentation I think I have at last completely
> cracked this problem.
> I have a HardyLittlewoodtype conjecture which does exactly what
> we want (and is able to predict your AP8 stats to an extraordinary
> degree of precision:)
> A post on all that is in preparation.
David 0 Attachment
 In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:> A post on all that is in preparation.
Two key references for this post are Chris's wonderfully informative "Arithmetic Progressions of Primes" page
http://primes.utm.edu/top20/page.php?id=14
and references cited therein; plus Jens's comprehensive "Primes in Arithmetic Progression Records" page
http://users.cybercity.dk/~dsl522332/math/aprecords.htm
It follows from the HardyLittlewood prime ktuple conjecture that the number of arithmetic progressions of k terms, all primes and not larger than x, is asymptotically (for large x):
c_k(x) = D_k*x^2/(2*(k1)*log(x)^k) .. (1)
where
D_k={product: p prime}beta(p)
with
beta(p)=(11/p)^(1k)*(1/p) p <= k
=(11/p)^(1k)*(1(k1)/p) p >= k
Consider the sequence u(a,d,n)=a+d*n, 0<=n<k.
The count of all such sequences with 0 < u(a,d,n) <= x is approximately:
t_k(N) = x^2/(2*(k1)) ..(2)
Comparison of (1) and (2) shows that the probability of a typical sequence consisting of *all* primes is just the product of the probabilities for each term separately to be prime (which by the PNT is 1/log(x), since x is the typical size of a term) times the factor D_k, which incorporates the fact that the terms are not independent from one another, primefactorwise.
Apply the above probability argument now to a kterm sequence u(a,d,n), where a is drawn at random from a set of Na values {A}, and d is drawn at random from a set of Nd values {D},
giving a total of Na*Nd sequences.
Let p(n) be the probability that u(n)=(a+n*d) be prime, 0<=n<k.
Conjecture: the probability P that u(n) is a sequence consisting of *all* primes is
P=D(k,d)*product{0<=n<k}p(n)
where
D(k,d)={product: p prime, p does not divide d}beta(p)
===
To see how the number of factors in d affects the "scaling" factor D(k,d), here is a table of computed values, with the number of significant digits displayed being approximately the number that can be trusted.
[D(k,1), D(k,1009#) and D(k,10007#) were computed using all primes to 10^8, the others using primes up to 10^7.]
For all q, we have:
D(2,q#)=1.00000000000
D(3,1)=1.32032363
D(3,2#)=0.6601618
D(3,3#)=0.8802158
D(3,5#)=0.9388968
D(3,7#)=0.9657224
D(3,17#)=0.9861509
D(3,37#)=0.9943893
D(3,67#)=0.9972169
D(3,1009#)=0.99987387
D(3,10007#)=0.999990194
D(4,1)=2.85824860
D(4,2#)=0.7145622
D(4,3#)=0.6351664
D(4,5#)=0.8130129
D(4,7#)=0.8959735
D(4,17#)=0.9581001
D(4,37#)=0.9830958
D(4,67#)=0.9916287
D(4,1009#)=0.99962152
D(4,10007#)=0.999970581
D(5,1)=4.1511809
D(5,2#)=0.5188976
D(5,3#)=0.3074949
D(5,5#)=0.6297495
D(5,7#)=0.7931539
D(5,17#)=0.9160594
D(5,37#)=0.9661407
D(5,67#)=0.9832363
D(5,1009#)=0.999242915
D(5,10007#)=0.999941160
D(6,1)=10.131795
D(6,2#)=0.6332372
D(6,3#)=0.2501678
D(6,5#)=0.4098749
D(6,7#)=0.6637208
D(6,17#)=0.8608535
D(6,37#)=0.9436427
D(6,67#)=0.9720641
D(6,1009#)=0.99873807
D(6,10007#)=0.99990193
D(7,1)=17.298612
D(7,2#)=0.5405817
D(7,3#)=0.1423754
D(7,5#)=0.1866143
D(7,7#)=0.5180388
D(7,17#)=0.7939335
D(7,37#)=0.9158195
D(7,67#)=0.9581607
D(7,1009#)=0.99810703
D(7,10007#)=0.99985290
D(8,1)=53.971949
D(8,2#)=0.8433118
D(8,3#)=0.1480712
D(8,5#)=0.1552639
D(8,7#)=0.3694376
D(8,17#)=0.7173459
D(8,37#)=0.8829862
D(8,67#)=0.9415983
D(8,1009#)=0.99734991
D(8,10007#)=0.99979405
D(9,1)=148.55163
D(9,2#)=1.1605598
D(9,3#)=0.1358497
D(9,5#)=0.1139590
D(9,7#)=0.2324194
D(9,17#)=0.6336562
D(9,37#)=0.8455522
D(9,67#)=0.9224727
D(9,1009#)=0.99646687
D(9,10007#)=0.99972541
D(10,1)=336.03433
D(10,2#)=1.3126344
D(10,3#)=0.1024339
D(10,5#)=0.0687422
D(10,7#)=0.1201712
D(10,17#)=0.5458231
D(10,37#)=0.8040131
D(10,67#)=0.9009026
D(10,1009#)=0.99545810
D(10,10007#)=0.99964695
D(11,1)=511.42229
D(11,2#)=0.9988719
D(11,3#)=0.0519659
D(11,5#)=0.02789898
D(11,7#)=0.04180406
D(11,17#)=0.4570322
D(11,37#)=0.7589416
D(11,67#)=0.8770283
D(11,1009#)=0.99432385
D(11,10007#)=0.99955869
D(12,1)=1312.3197
D(12,2#)=1.2815626
D(12,3#)=0.04444851
D(12,5#)=0.01909049
D(12,7#)=0.02451887
D(12,17#)=0.3704957
D(12,37#)=0.7109748
D(12,67#)=0.8510107
D(12,1009#)=0.9930644
D(12,10007#)=0.99946063
D(13,1)=2364.5990
D(13,2#)=1.1545898
D(13,3#)=0.02669647
D(13,5#)=0.009172838
D(13,7#)=0.010098114
D(13,17#)=0.2892347
D(13,37#)=0.6607992
D(13,67#)=0.8230294
D(13,1009#)=0.9916802
D(13,10007#)=0.99935277
D(14,1)=7820.6003
D(14,2#)=1.9093271
D(14,3#)=0.02943169
D(14,5#)=0.00809012
D(14,7#)=0.00763387
D(14,17#)=0.2158645
D(14,37#)=0.6091338
D(14,67#)=0.7932804
D(14,1009#)=0.9901715
D(14,10007#)=0.99923512
D(15,1)=22938.910
D(15,2#)=2.8001612
D(15,3#)=0.02877575
D(15,5#)=0.00632785
D(15,7#)=0.00511799
D(15,17#)=0.1524021
D(15,37#)=0.5567125
D(15,67#)=0.7619744
D(15,1009#)=0.9885387
D(15,10007#)=0.99910766
D(16,1)=55651.466
D(16,2#)=3.3966978
D(16,3#)=0.02327069
D(16,5#)=0.00409382
D(16,7#)=0.00283808
D(16,17#)=0.1001208
D(16,37#)=0.5042644
D(16,67#)=0.7293338
D(16,1009#)=0.9867825
D(16,10007#)=0.99897041
D(17,1)=91555.117
D(17,2#)=2.7940422
D(17,3#)=0.01276128
D(17,5#)=0.00179599
D(17,7#)=0.00106722
D(17,17#)=0.0594701
D(17,37#)=0.4524954
D(17,67#)=0.6955905
D(17,1009#)=0.9849033
D(17,10007#)=0.99882337
D(18,1)=256474.88
D(18,2#)=3.9134989
D(18,3#)=0.01191613
D(18,5#)=0.001341636
D(18,7#)=0.000683341
D(18,17#)=0.03007454
D(18,37#)=0.4020697
D(18,67#)=0.6609823
D(18,1009#)=0.9829017
D(18,10007#)=0.9986665
D(19,1)=510992.05
D(19,2#)=3.8985631
D(19,3#)=0.007913765
D(19,5#)=0.0007128086
D(19,7#)=0.0003111922
D(19,17#)=0.01081699
D(19,37#)=0.3535932
D(19,67#)=0.6257508
D(19,1009#)=0.9807783
D(19,10007#)=0.9984999
D(20,1)=1900972.8
D(20,2#)=7.251642
D(20,3#)=0.009813495
D(20,5#)=0.0007071368
D(20,7#)=0.0002646138
D(20,17#)=0.007264514
D(20,37#)=0.3075983
D(20,67#)=0.5901376
D(20,1009#)=0.9785338
D(20,10007#)=0.9983236
D(21,1)=6423764.9
D(21,2#)=12.2523717
D(21,3#)=0.01105392
D(21,5#)=0.0006372150
D(21,7#)=0.0002043846
D(21,17#)=0.004431580
D(21,37#)=0.2645322
D(21,67#)=0.5543818
D(21,1009#)=0.9761689
D(21,10007#)=0.9981374
D(22,1)=18606668
D(22,2#)=17.744721
D(22,3#)=0.01067269
D(22,5#)=0.000492191
D(22,7#)=0.000135316
D(22,17#)=0.002317266
D(22,37#)=0.2247477
D(22,67#)=0.5187169
D(22,1009#)=0.9736844
D(22,10007#)=0.9979415
D(23,1)=38734737
D(23,2#)=18.470185
D(23,3#)=0.007406019
D(23,5#)=0.0002732339
D(23,7#)=0.00006438774
D(23,17#)=0.000870855
D(23,37#)=0.1884984
D(23,67#)=0.4833680
D(23,1009#)=0.9710811
D(23,10007#)=0.9977358
D(24,1)=153217040
D(24,2#)=36.5298376
D(24,3#)=0.009764950
D(24,5#)=0.00028821046
D(24,7#)=0.00005821456
D(24,17#)=0.000621857
D(24,37#)=0.1559370
D(24,67#)=0.4485489
D(24,1009#)=0.9683599
D(24,10007#)=0.99752023
D(25,1)=568632600
D(25,2#)=67.7863864
D(25,3#)=0.01208018
D(25,5#)=0.0002852353
D(25,7#)=0.0000493831
D(25,17#)=0.0004166331
D(25,37#)=0.1271171
D(25,67#)=0.4144603
D(25,1009#)=0.9655215
D(25,10007#)=0.9972951
D(26,1)=1941938900
D(26,2#)=115.74876
D(26,3#)=0.0137517
D(26,5#)=0.00025986
D(26,7#)=0.000038548
D(26,17#)=0.00025686
D(26,37#)=0.1019998
D(26,67#)=0.3812867
D(26,1009#)=0.9625671
D(26,10007#)=0.9970601
For k=3..26, we have:
D(k,130003#)=1.00000000000
In order to confront this conjecture with experiment, I have computed some expected vs. actual probabilities for three scenarios representative of actuallyundertaken searches for APk's, in particular, those in which the common difference d has very many factors.
===
Consider arithmetic progressions {u(n)=a+n*d, 0<=d<k},
where every term is of the form m*q#+1, with M1<=m<=M2.
Take M1=99000001, M2 = 101000000, so M_mean=10^8, M_count=2*10^7.
If ck is a count of the number of APk's,
and "dig" is the mean number of digits in u(n), viz. log(M_mean*q#)/log(10),
and ck_theor=D(k,q#)*x^2/(2*(k1)*log(x)^k)
with x=M_mean*q#,
then we find the following theoreticallypredicted and experimentallyfound counts:
q dig c1_theor c1_exp
1 8.0 108573.62 108540
2 8.3 209272.58 209370
3 8.8 296846.89 296845
5 9.5 343691.77 343261
7 10.3 368145.32 368052
11 11.4 367848.22 368073
13 12.5 362925.64 363158
17 13.7 350995.75 350821
19 15.0 338882.78 339794
23 16.3 324776.66 324653
29 17.8 308757.02 309100
31 19.3 294398.04 294802
37 20.9 279840.28 279217
41 22.5 266260.73 266648
43 24.1 254136.55 254326
47 25.8 242825.31 241998
53 27.5 231984.23 232039
59 29.3 221713.58 221056
61 31.1 212456.16 212742
67 32.9 203702.70 203981
[Of course c2=c1*(c11)/2.]
q c3_theor c3_exp
1 211233780.6 202841435
2 756305702.2 728944254
3 2878038897.6 2773618467
5 4764697012.5 4512210251
7 6023101499.9 5675518754
17 5330389807.1 5022131103
37 2723937336.5 2586439661
67 1053634545.6 1020369385
q c4_theor c4_exp
1 16549544.5 15871419
2 57105514.8 55044966
3 205497365.8 197860176
5 472675149.7 439294189
7 685742445.9 629037681
17 605908579.3 554325985
37 251203375.0 232545604
67 71141821.6 67735580
q c5_theor c5_exp
1 978618.2 898748
2 3254342.9 3012277
3 11074405.9 10254290
5 47188217.0 43775930
7 83805770.3 75904604
17 76252302.8 68614763
37 25906665.1 23613957
67 5388424.9 5081205
q c6_theor c6_exp
1 103731.9 97097
2 332445.4 313857
3 1069809.4 1007089
5 4222271.7 3980463
7 10327165.7 9313827
17 10060520.6 8959287
37 2832363.2 2554552
67 434065.9 406473
q c7_theor c7_exp
1 8012.2 6911
2 24746.6 21828
3 75306.3 66759
5 275294.6 244774
7 1236420.0 1116660
17 1356956.5 1201795
37 320516.4 287877
67 36314.9 33676
q c8_theor c8_exp
1 1163.2 1013
2 3462.4 3033
3 9963.7 8952
5 33737.7 30323
7 139119.3 126565
17 184431.7 163219
37 37061.9 33069
67 3115.5 2800
q c9_theor c9_exp
1 152.1 136
2 436.3 359
3 1187.2 1129
5 3723.4 3350
7 14096.7 13059
17 25017.3 22276
37 4345.1 3883
67 272.0 248
q c10_theor c10_exp
1 16.6 19
2 45.9 37
3 118.1 122
5 343.1 341
7 1192.6 1101
17 3361.7 3041
37 513.9 457
67 24.1 24
q c11_theor c11_exp
1 1.23 0
2 3.29 1
3 8.00 7
5 21.54 22
7 68.73 58
17 444.60 389
37 61.08 59
67 2.15 1
q c12_theor c12_exp
1 0.156 0
2 0.401 0
3 0.924 0
5 2.302 5
7 6.745 4
17 57.502 47
37 7.279 4
67 0.193 0
q c13_theor c13_exp
1 0.0140 0
2 0.0347 0
3 0.0755 0
5 0.1742 0
7 0.4688 0
17 7.2216 9
37 0.8677 1
67 0.0174 0
q c14_theor c14_exp
1 0.00232 0
2 0.00554 0
3 0.01140 0
5 0.02438 0
7 0.06021 0
17 0.87312 1
37 0.10331 0
67 0.00158 0
q c15_theor c15_exp
1 0.00034 0
2 0.00079 0
3 0.00154 0
5 0.00304 0
7 0.00690 0
11 0.01975 0
13 0.06839 1
17 0.10045 0
37 0.01227 0
67 0.00014 0
===
As another set of experiments, this time oriented towards the statistics of actual APk records, as per Jens's page cited above, consider, again, arithmetic progressions {u(n)=a+n*d, 0<=d<k},
where every term is of the form m*q#+1, with M1<=m<=M2.
Take M1 = 1, M2=2000000000, so M_mean=10^9, M_count=2*10^9.
We find the following theoretical predictions for counts ck of APk's:
** k=3 **
q dig c1 c3 c4 c5
317363 137513.7 142526.25 361905.02 17.19 0.00092
298409 129237.3 150912.59 429621.89 21.61 0.0012
** k=4 **
q dig c1 c3 c4 c5 c6
27751 11961.6 1323796.29 289982931.39 127958.82 63.52 0.034
23159 10005.8 1555099.09 470092004.06 243678.36 142.10 0.088
** k=5 **
q dig c1 c3 c4 c5 c6 c7
16229 7009.5 2141861.98 1228237350.34 876896.25 704.31 0.60 0.00054
5113 2197.7 6022927.71 27310170302.0 54826899.86 123824.60 298.29 0.75
** k=6 **
q dig c1 c4 c5 c6 c7 c8
3739 1607.1 7938323.71 165450204.95 492482.39 1563.62 5.17 0.018
3529 1503.9 8415847.33 208997272.44 659523.38 2219.91 7.78 0.028
3011 1289.5 9634046.26 358902669.50 1296491.56 4995.46 20.05 0.083
** k=7 **
q dig c1 c5 c6 c7 c8 c9
3011 1289.5 9634046.26 1296491.56 4995.46 20.05 0.083 0.00035
3001 1286.0 9656898.99 1311940.73 5066.98 20.38 0.084 0.00036
** k=8 **
q dig c1 c6 c7 c8 c9 c10
2459 1055.7 11477930.33 14284.51 68.30 0.34 0.0017 0.0000086
2411 1035.4 11674422.61 15815.82 76.92 0.38 0.0020 0.000010
** k=9 **
q dig c1 c7 c8 c9 c10 c11
997 424.3 25284285.59 17171.15 185.93 2.05 0.023 0.00026
941 400.4 26574383.43 24323.82 276.80 3.22 0.038 0.00045
757 324.2 31826848.17 85922.60 1170.78 16.28 0.23 0.0033
701 301.3 33877610.42 132997.69 1928.83 28.55 0.43 0.0065
499 215.1 45063613.24 978740.14 18871.29 371.34 7.42 0.15
463 201.7 47569642.89 1429072.60 29082.78 604.01 12.74 0.27
** k=10 **
q dig c1 c8 c9 c10 c11 c12
617 264.6 37815477.56 4645.93 76.75 1.29 0.022 0.00038
607 259.1 38504142.29 5366.94 90.27 1.54 0.027 0.00047
463 201.7 47569642.89 29082.78 604.01 12.74 0.27 0.0059
** k=11 **
q dig c1 c9 c10 c11 c12 c13
449 193.7 49209748.70 819.14 17.87 0.39 0.0088 0.00020
401 172.6 54198048.78 1950.83 46.86 1.14 0.028 0.00069
349 149.4 61132838.21 5755.11 155.84 4.27 0.12 0.0033
281 124.4 71150930.76 22489.10 708.20 22.57 0.73 0.024
** k=12 **
q dig c1 c10 c11 c12 c13 c14
401 172.6 54198048.78 46.86 1.14 0.028 0.00069 0.000017
283 126.8 70023070.54 603.89 18.94 0.60 0.019 0.00061
229 100.3 84886301.52 4114.22 156.20 5.99 0.23 0.0090
199 90.9 91980354.17 9152.84 376.24 15.61 0.65 0.027
173 77.2 104883968.89 33805.65 1582.07 74.71 3.55 0.17
157 70.5 112761422.84 69464.48 3491.45 177.07 9.04 0.46
** k=13 **
q dig c1 c11 c12 c13 c14 c15
173 77.2 104883968.89 1582.07 74.71 3.55 0.17 0.0082
139 64.0 121865274.43 8151.93 446.18 24.59 1.36 0.076
127 57.6 132424730.49 20177.45 1197.92 71.61 4.30 0.26
103 49.4 149105671.60 73303.06 4883.26 327.42 22.07 1.49
** k=14 **
q dig c1 c12 c13 c14 c15 c16
151 68.4 115642693.09 239.12 12.52 0.66 0.035 0.0019
131 59.7 128712444.82 854.53 49.69 2.91 0.17 0.010
101 47.4 153932686.06 7117.19 492.08 34.19 2.39 0.17
** k=15 **
q dig c1 c13 c14 c15 c16 c17
101 47.4 153932686.06 492.08 34.19 2.39 0.17 0.012
** k=16 **
q dig c1 c14 c15 c16 c17 c18
73 37.6 183222748.55 370.57 30.47 2.51 0.21 0.017
71 35.7 190132666.62 611.87 52.05 4.44 0.38 0.032
43 25.1 244018322.25 17022.92 1801.94 190.50 20.10 2.11
** k=17 **
q dig c1 c15 c16 c17 c18 c19
53 28.5 223848160.09 541.91 53.41 5.26 0.52 0.051
43 25.1 244018322.25 1801.94 190.50 20.10 2.11 0.22
** k=18 **
q dig c1 c16 c17 c18 c19 c20
53 28.5 223848160.09 53.41 5.26 0.52 0.051 0.0050
31 20.3 279897280.35 1305.69 150.81 17.28 1.96 0.22
23 17.3 306055912.16 3761.57 442.62 51.13 5.78 0.64
** k=19 **
q dig c1 c17 c18 c19 c20 c21
31 20.3 279897280.35 150.81 17.28 1.96 0.22 0.024
23 17.3 306055912.16 442.62 51.13 5.78 0.64 0.068
** k=20 **
q dig c1 c18 c19 c20 c21 c22
23 17.3 306055912.16 51.13 5.78 0.64 0.068 0.0071
** k=21 **
q dig c1 c19 c20 c21 c22 c23
23 17.3 306055912.16 5.78 0.64 0.068 0.0071 0.00070
** k=22 **
q dig c1 c20 c21 c22 c23 c24
23 17.3 306055912.16 0.64 0.068 0.0071 0.00070 0.000067
** k=23 **
q dig c1 c21 c22 c23 c24 c25
23 17.3 306055912.16 0.068 0.0071 0.00070 0.000067 0.0000059
** k=24 **
q dig c1 c22 c23 c24 c25
23 17.3 306055912.16 0.0071 0.00070 0.000067 0.0000059
** k=25 **
q dig c1 c23 c24 c25
23 17.3 306055912.16 0.00070 0.000067 0.0000059
Note (1): The k=8, q=2459 stats agree beautifully with Ken's actual counts  see his post:
http://tech.groups.yahoo.com/group/primenumbers/message/20140
Note (2): If, instead of M_count=2*10^9, one were to choose a different value, then the above counts are all to be multiplied by (M_count/2*10^9)^2; this is an excellent way of estimating what block size woud be required to obtain a predicted count of 1.0.
===
As a final set of experiments, oriented this time towards the statistics of APk records for large k, consider arithmetic progressions {u(n)=a+n*d, 0<=d<k}, where every term is of the form a+q#, with a_min<=a<=a_max.
Taking always a_max=a_min+10^12, we find the following theoretical predictions for counts of APk's:
a_min=10^16, q=23, dig=17:
c20_theor=131491.513618
c21_theor=15277.0009101
c22_theor=1715.86594350
c23_theor=185.099954827
c24_theor=19.0095562007
c25_theor=1.83517574326
c26_theor=0.163311641770
a_min=10^18, q=43, dig=19:
c20_theor=605995.069496
c21_theor=87300.2072397
c22_theor=12504.4660274
c23_theor=1779.79385925
c24_theor=251.582566249
c25_theor=35.2976557067
c26_theor=4.91254506617
a_min=10^20, q=53, dig=21:
c20_theor=111588.394854
c21_theor=14827.7334326
c22_theor=1962.13961648
c23_theor=258.478592621
c24_theor=33.8849092473
c25_theor=4.41903581907
c26_theor=0.573116905364
Comments (pos. or neg.) welcome  especially from APk practitioners!
Mike Oakes 0 Attachment
 In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:>
which is nonsense. I meant:
> As a final set of experiments, oriented this time towards the
> statistics of APk records for large k, consider arithmetic
> progressions {u(n)=a+n*d, 0<=d<k}, where every term is of the
> form a+q#, with a_min<=a<=a_max.
.. consider arithmetic progressions {u(n)=a+n*d, 0<=n<k}, where d=q#, with a_min<=a<=a_max.
Mike 0 Attachment
 In primenumbers@yahoogroups.com,
"Mike Oakes" <mikeoakes2@...> wrote:
> Chris's wonderfully informative
http://primes.utm.edu/top20/page.php?id=14
> "Arithmetic Progressions of Primes" page
Yes, that Grosswald conjecture is rather remarkable,
About your tables of ck_theor and ck_exp for k > 2:
the theory side seems to be systematically high.
Not by much, but still more than the 1/sqrt(N) fluctuations.
Can you please spell out the comparison with Ken's data:
> 189,178,618,167 ap3s
It seems that you did not so far show your expectations
> 543,008,443 ap4s
> 3,117,826 ap5s
for c3,c4,c5, where his stats are good. (I take your point
about c6 and c7 looking good.)
Thanks for an interesting posting.
David 0 Attachment
 In primenumbers@yahoogroups.com, "David Broadhurst" <d.broadhurst@...> wrote:>
My program output says:
> Can you please spell out the comparison with Ken's data:
>
> > 189,178,618,167 ap3s
> > 543,008,443 ap4s
> > 3,117,826 ap5s
>
> It seems that you did not so far show your expectations
> for c3,c4,c5, where his stats are good. (I take your point
> about c6 and c7 looking good.)
>
counts_theor(3,2459)=189008276732.
counts_theor(4,2459)=723074851.939
counts_theor(5,2459)=3111847.13368
Note that Ken qualified his ap4s count by
"(psuedo eg. 1,2,3,5 as only processed AP3's with an even difference)"
Mike 0 Attachment
 In primenumbers@yahoogroups.com,
"Mike Oakes" <mikeoakes2@...> wrote:
> > 189,178,618,167 ap3s
Very nice: congrats!
> > 3,117,826 ap5s
> counts_theor(3,2459)=189008276732.
> counts_theor(5,2459)=3111847.13368
David 0 Attachment
Hi Mike,
A few quick comparisons with some of my other searches.
AP9
With m_count = 1*10^9 and your formula (M_count/2*10^9)^2 = 1/4
Gives
q dig c1 c7 c8 c9
Theory 997 424.3 12642142 4293 46 0
Actual 997 424.3 12658662 4331 53 0
If you want to compare further
Ap6s = 409947
Ap5s = 40570738
Ap4s = 3207896756 (this might have been pseudo's I'd have to check my C++ code which I don't have access to at the moment)
Ap3's = lost count
AP10
With m_count = 1*10^9
Gives
q dig c1 c8 c9 c10
Theory 617 264.6 18907739 1161 19 0
Actual 617 264.6 18894798 1133 14 0
Ap7s = 71214
I only have valid counts down to this level as I only processed AP3s with a difference of 3 (looking inside them for an Ap7)
All in all your theory nicely agrees with my results and should help me greatly for future searches.
Thanks Mike!
A very nice result.
Cheers
Ken 0 Attachment
 In primenumbers@yahoogroups.com, "Ken Davis" <kradenken@...> wrote:>
counts_theor(1,997)=12642142.7943
> Hi Mike,
> A few quick comparisons with some of my other searches.
>
> AP9
> With m_count = 1*10^9 and your formula (M_count/2*10^9)^2 = 1/4
> Gives
>
> q dig c1 c7 c8 c9
> Theory 997 424.3 12642142 4293 46 0
> Actual 997 424.3 12658662 4331 53 0
>
> If you want to compare further
> Ap6s = 409947
> Ap5s = 40570738
> Ap4s = 3207896756 (this might have been pseudo's I'd have to check my C++ code which I don't have access to at the moment)
> Ap3's = lost count
>
counts_theor(2,997)=7.99118808941 E13
counts_theor(3,997)=505064537331.
counts_theor(4,997)=4255649343.14
counts_theor(5,997)=40334993.7203
counts_theor(6,997)=407728.896596
counts_theor(7,997)=4292.73732756
counts_theor(8,997)=46.4810674074
counts_theor(9,997)=0.513708974304
counts_theor(10,997)=0.00576689464294
counts_theor(11,997)=0.0000655399693707
counts_theor(12,997)=0.000000752280002281
> AP10
counts_theor(1,617)=18895165.9208
> With m_count = 1*10^9
> Gives
>
> q dig c1 c8 c9 c10
> Theory 617 264.6 18907739 1161 19 0
> Actual 617 264.6 18894798 1133 14 0
>
> Ap7s = 71214
> I only have valid counts down to this level as I only processed AP3s with a difference of 3 (looking inside them for an Ap7)
>
counts_theor(2,617)=1.78513638140 E14
counts_theor(3,617)=1.68615682803 E12
counts_theor(4,617)=21230924677.6
counts_theor(5,617)=300675388.024
counts_theor(6,617)=4541098.43467
counts_theor(7,617)=71426.2578907
counts_theor(8,617)=1155.29887582
counts_theor(9,617)=19.0717479232
counts_theor(10,617)=0.319764874922
counts_theor(11,617)=0.00542713429128
counts_theor(12,617)=0.0000930206866839
counts_theor(13,617)=0.00000160729956878
Thanks for your feedback, Ken.
Mike 0 Attachment
 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
Your message has been successfully submitted and would be delivered to recipients shortly.