A292224 Irregular triangle read by rows. T(n, k) gives the number of admissible k-tuples from the interval of integers [0, 1, ..., n-1] starting with smallest tuple member 0.

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 1, 3, 2, 1, 4, 4, 1, 1, 4, 4, 1, 1, 5, 6, 2, 1, 5, 6, 2, 1, 6, 11, 8, 2, 1, 6, 11, 8, 2, 1, 7, 15, 14, 4, 1, 7, 15, 14, 4, 1, 8, 19, 20, 8, 1, 1, 8, 19, 20, 8, 1, 1, 9, 27, 39, 24, 5, 1, 9, 27, 39, 24, 5, 1, 10, 33, 54, 44, 16, 2, 1, 10, 33, 54, 44, 16, 2, 1, 11, 39, 69, 62, 26, 2, 1, 11, 39, 69, 62, 26, 2

Offset: 1

Author

Wolfdieter Lang, Oct 09 2017

Keywords

• nonn
• tabf
• changed

Comments

The row lengths are given by A023193 (the rhobar function of Schinzel and Sierpiński called rho* by Hensley and Richards).

This irregular triangle has already been considered by Engelsma, see Table 2, for n=1..56, p. 27.

A k-tuple of integers B_k = [b_1, ..., b_k] with 0 = b_1 < b_2 < ... < b_k <= n-1 is called admissible if for each prime p there exists at least one congruence class modulo p which contains none of the B_k elements. (This corresponds to the alternative definition of Hensley and Richards, p. 378 (*) or Richards, p. 423, 1.5 Definition and (*).) Note that the definition of "admissibility" is translation invariant (see the Note by Richards, p. 424, which is obvious from the translation equivalence of complete residue systems modulo p). Therefore the interval I_n = [0, n-1] of length n has been chosen. The b_1 = 0 choice is conventional. Without this choice other admissible k-tuples are obtained by translation as long as b_k + a < n-1. E.g., for n = 8 and k = 3 the tuple [1, 5, 7] is admissible and a translation of the considered tuple [0, 4, 6].

Only primes p <= k have to be tested to decide on the admissibility of a B_k tuple because for larger k there is always some residue class which contains none of the k members of B_k.

Because p = 2 already forbids even and odd numbers to appear in B_k for k >= 2, one can for the admissibility test eliminate all odd numbers in the chosen I_n. Therefore, only Ieven_n:= [0, 2, ..., 2*floor((n-1)/2)] =: 2*[0, 1, ..., floor((n-1)/2)] need be considered. B_1 = [0] is admissible for all n >= 1.

Because only the interval Ieven_n is of relevance, there will occur repetitions for admissible tuples for n if n = 2*k+1 and n = 2*k+2.

With the set B_k(p) = B_k (mod p) := {0, b_1 (mod p), ..., b_k (mod p)} the criterion for admissibility can be written as p - #(B_k(p)) > 0, for all primes 3 <= p <= k (because there are p congruence classes defined by smallest nonnegative complete residue system [0, 1, ..., p-1]).

Admissible tuples (starting with 0) with least b_k - b_1 = b_k value give rise to prime k-constellations of diameter b_k. E.g., for k = 2 the admissible tuple [0, 4] does not lead to a prime 2-constellation for n >= 5; [0, 6] is out for n >= 7, ... . But there are two prime 3-constellations given by [0, 2, 6] and [0, 4, 6] for n >= 7.

Row sums are in A292225, that is, total number of admissible tuples starting with 0 from the interval I_n = [0, n-1].

Examples

			The irregular triangle begins:
n\k   1  2  3  4  5  6  7 ...
1:    1
2:    1
3:    1  1
4:    1  1
5:    1  2
6:    1  2
7:    1  3  2
8:    1  3  2
9:    1  4  4  1
10:   1  4  4  1
11:   1  5  6  2
12:   1  5  6  2
13:   1  6 11  8  2
14:   1  6 11  8  2
15:   1  7 15 14  4
16:   1  7 15 14  4
17:   1  8 19 20  8  1
18:   1  8 19 20  8  1
19:   1  9 27 39 24  5
20:   1  9 27 39 24  5
21:   1 10 33 54 44 16  2
22:   1 10 33 54 44 16  2
23:   1 11 39 69 62 26  2
24:   1 11 39 69 62 26  2
...
The first admissible k-tuples are (blanks within a tuple are here omitted):
n\k  1                2                                  3                       4  ...
1:  [0]
2:  [0]
3:  [0]  [0,2]
4:  [0]  [0,2]
5:  [0]  [[0,2], [0,4]]
6:  [0]  [[0,2], [0,4]]
7:  [0]  [[0,2], [0,4], [0,6]]          [[0,2,6], [0,4,6]]
8:  [0]  [[0,2], [0,4], [0,6]]          [[0,2,6], [0,4,6]]
9:  [0]  [[0,2], [0,4], [0,6], [0,8]]   [[0,2,6], [0,2,8], [0,4,6], [0,6,8]]  [0,2,6,8]
10: [0]  [[0,2], [0,4], [0,6], [0,8]]   [[0,2,6], [0,2,8], [0,4,6], [0,6,8]]  [0,2,6,8]
...
The first admissible k-tuples for prime k-constellations are:
n\k  1     2           3                 4                    5                       6  ...
1:  [0]
2:  [0]
3:  [0]  [0,2]
4:  [0]  [0,2]
5:  [0]  [0,2]
6:  [0]  [0,2]
7:  [0]  [0,2]  [[0,2,6], [0,4,6]]
8:  [0]  [0,2]  [[0,2,6], [0,4,6]]
9:  [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]
10: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]
11: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]
12: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]
13: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]   [[0,2,6,8,12],[0,4,6,10,12]]
14: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]   [[0,2,6,8,12],[0,4,6,10,12]]
15: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]   [[0,2,6,8,12],[0,4,6,10,12]]
16: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]   [[0,2,6,8,12],[0,4,6,10,12]]
17: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]   [[0,2,6,8,12],[0,4,6,10,12]] [0,4,6,10,12,16]
18: [0]  [0,2]  [[0,2,6], [0,4,6]]   [0,2,6,8]   [[0,2,6,8,12],[0,4,6,10,12]] [0,4,6,10,12,16]
...
-----------------------------------------------------------------------------------------------
T(7, 3) = 2 because Ieven_n = [0, 2, 4, 6], and the only admissible 3-tuples from this interval are [0, 2, 6] and [0, 4, 6]. For example, [0, 2, 4] is excluded because the set B_3 (mod 3) = {0, 1, 2}, thus #{0, 1, 2} = 3 and (p = 3) - 3 = 0, not > 0.
These two admissible 3-tuples both have diameter 6 and stand for prime 3-constellations for all n >= 7: p, p + 2, p + 6, and p, p + 4, p + 6. One of the Hardy-Littlewood conjectures is that there are in both cases infinitely many such prime triples. For the first members of such triples see A022004 and A022005.
		

Links

• Pontus von Brömssen, Table of n, a(n) for n = 1..1296 (rows 1..100)
• Thomas J. Engelsma, Permissible Patterns of Primes, September 2009, Table 2, p. 27.
• D. Hensley and I. Richards, Primes in intervals, Acta Arith. 25 (1974), pp. 375-391.
• Ian Richards, On the incompatibility of two conjectures concerning primes; a discussion of the use of computers in attacking a theoretical problem, Bulletin of the American Mathematical Society 80:3 (1974), pp. 419-438.
• A. Schinzel, Remarks on the paper 'Sur certaines hypothèses concernant les nombres premiers', Acta Arithmetica 7 (1961), pp. 1-8.
• A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4,3 (1958), pp. 185-208, Théorème 1, p. 201; erratum 5 (1958) p. 259.
• Wikipedia, Prime k-tuple.

Crossrefs

Cf. A020497, A022004, A022005, A023193, A292225.

Formula

T(n, k) = number of admissible k-tuples B_k = [0, b_2, ..., b_k] (see the comment above) from the interval of integers Ieven_n:= [0, 2, ..., 2*floor((n-1)/2)].