Notes on A124064 (was Re: primes in arithmetic progression)

[David Wilson]

This is one of those cases where I think we have jumped the gun, creating a 
sequence without first determining the best structure for that sequence.

Richard Mather proposed a table of T(d,k) = the smallest possible initial 
element of a nondecreasing AP of k primes with difference d. Clearly, T(d,k) 
is defined only for d >= 0 and k >= 1.

For d = 0, it is pretty easy to show T(0, k) = 2 for any k >= 1. For d >= 1, 
however, T(d,k) is defined only for a finite number of k.

Proof: Suppose there exists AP P of primes with difference d >= 1 and 2d+2 
elements. Let c = d+1. Because P is an arithmetic progression of 2c elements 
with difference d, and c is coprime to d, P will have two elements divisible 
by c, call them cx and cy. Whereas P is an increasing sequence of positive 
integers, we can assume that 0 < cx < cy. Hence 0 < x < y, and y >= 2. But 
this makes cy composite, contrary to fact that P is a sequence of primes. 
Hence P does not exist, that is to say, any AP of primes with difference d 
 >= 1 has at most 2d+1 elements, and T(d,k) is undefined for k > 2d+1. QED.

In fact, assuming the k-tuple conjecture is true, we can give the precise 
domain of T for d >= 1: If p is the smallest prime not dividing d, then 
T(d,k) is defined precisely for 1 <= k <= p if the AP of p elements with 
initial element p and difference d is a prime AP, and for 1 <= k <= p-1 
otherwise.

This means that the table of T(d,k) looks as follows:

  \k|  1  2  3  4  5  6  7  8  9 10
  d\|
----+------------------------------
  0 |  2  2  2  2  2  2  2  2  2  2 ...
  1 |  2  2
  2 |  2  3  3
  3 |  2  2
  4 |  2  3  3
  5 |  2  2
  6 |  2  5  5  5  5
  7 |  2
  8 |  2  3  3
  9 |  2  2
 10 |  2  3  3
 11 |  2  2
 12 |  2  5  5  5  5
 13 |  2
 14 |  2  3  3
 15 |  2  2
 16 |  2  3
 17 |  2  2
 18 |  2  5  5  5
 19 |  2
 20 |  2  3  3
 ...

Two important points:

- Sometimes in the OEIS, we are tempted to pare down sequences to remove 
uninteresting values in order to emphasize the interesting values. In such 
cases, I think that the OEIS should include a main sequence that is 
complete, and additional pared-down sequences if they seem to augment our 
understanding of the main sequence. In this case, Mather's sequence included 
T(d,k) only for even d, presumably because T(d,k) is uninteresting for odd 
d. My table above includes T(d,k) for both even and odd d. In fact, it turns 
out that for odd d, T(d,1) = 2 and T(d,2) = 2 if 2+d is prime, not 
scintillating behavior, but not trivial either. My feeling is that the main 
sequence for T(d,k) (presumably A124064) should include all the values of 
T(d,k), and if restricting T(d,k) to even d seems to augment our 
understanding, a second pared-down sequence should be made referring back to 
the complete main sequence.

- For d >= 1 and sufficient k, T(d,k) is undefined. The standard 
diagonalization technique won't work for this irregular table. That is why 
NJAS's proposed A124064 ends where it does, because the next value, T(2,4), 
does not exist (it is not a matter of doing more computation, T(2,4) does 
not exist because there is no AP of 4 primes with difference 2). I can see 
two possible ways to address this problem, the (icky) option of making 
T(d,k) = 0 if undefined, or the (less icky) option of requiring the APs in 
question to be strictly increasing. This would dispense with the infinite d 
= 0 line and leave us with a list of finite sequences which we could 
concatenate to build A124064, vis:

2,2,2,3,3,2,2,2,3,3,2,2,2,5,5,5,5,2,2,3,3,2,2,2,3,3,2,2,2,5,5,5,5,2,2,
3,3,2,2,2,3,2,2,2,5,5,5,2,2,3,3,2,2,2,7,2,2,5,5,59,2,2,3,2,2,2,3,3,2,2,
2,7,7,7,7,7,2,2,5,2,2,3,3,2,2,2,5,7,31,2,2,3,3,2,2,2,3,3,2,2,2,5,5,5,5

We could put the line lengths in another sequence.

2,3,2,3,2,5,1,3,2,3,2,5,1,3,2,2,2,4,1,3,2,2,1,4,1,2,2,3,2,6,1,2,1,3,2,4,
1,3,2,3,2,5,1,2,2,2,1,5,1,3,2,2,1,4,1,2,2,2,2,6,1,2,1,3,2,4,1,3,2,2,2,4,
1,2,1,2,2,4,1,3,2,2,1,4,1,2,2,2,1,6,1,2,1,3,2,5,1,3,2,2,2,4,1,3,2,2,2,4

----- Original Message ----- 
From: "N. J. A. Sloane" <njas at research.att.com>
To: <seqfan at ext.jussieu.fr>; "Richard Mathar" <mathar at strw.leidenuniv.nl>
Sent: Saturday, November 04, 2006 2:10 PM
Subject: Re: primes in arithmetic progression


> Just to get the ball rolling, I am adding this entry:
>
> %I A124064
> %S A124064 2,2,2,2,3,2,2,3,3,2,2,5,3
> %N A124064 Array read by antidiagonals: T(d,k) (k >= 1, d = 2,4,6,8,...) = 
> smallest prime p of k (not necessarily consecutive) primes in arithmetic 
> progression with common difference d.
> %C A124064 The row d=0 and the column k=1 are degenerate and are filled 
> with the prime 2.
> %O A124064 1,1
> %K A124064 nonn,tabl,more
> %e A124064 Array begins:
> %e A124064 d.\...k=1.k=2..k=3..k=4..k=5..k=6
> %e A124064 0..|..2...2....2....2....2....2
> %e A124064 2..|..2...3....3
> %e A124064 4..|..2...3....3
> %e A124064 6..|..2...5....5....5....5
> %e A124064 8..|..2...3....3
> %e A124064 10.|..2...3....3
> %e A124064 12.|..2...5....5....5....5
> %e A124064 14.|..2...3....3.
> %e A124064 16.|..2...3
> %e A124064 18.|..2...5....5....5
> %e A124064 20.|..2...3
> %e A124064 22.|..2...7
> %e A124064 24.|..2...5....5...59
> %e A124064 26.|..2...3
> %e A124064 28.|..2...3....3
> %e A124064 30.|..2...7....7....7.....7....7
> %e A124064 32.|..2...5
> %e A124064 34.|..2...3....3
> %e A124064 36.|..2...5....7...31
> %e A124064 Example for row d=24 and column k=4: the 4 numbers 
> 59,59+24,59+2*24 and 59+3*24 are all primes.
> %A A124064 Richard Mathar (mathar(AT)strw.leidenuniv.nl), Nov 04 2006
>
>
>
>
> NJAS
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.5.430 / Virus Database: 268.13.27/517 - Release Date: 11/3/2006 
> 4:30 PM
>