A327742 Triangle T(k, n) read by rows, where the entries of the triangle are lengths of longest runs of consecutive sums of k-length combinations of first n primes. Specially, T(0, n) = 1.

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 2, 4, 4, 2, 1, 1, 2, 5, 6, 5, 2, 1, 1, 2, 5, 10, 10, 5, 2, 1, 1, 2, 5, 18, 16, 18, 5, 2, 1, 1, 2, 5, 22, 28, 28, 22, 5, 2, 1, 1, 2, 5, 22, 38, 46, 38, 22, 5, 2, 1, 1, 2, 5, 40, 46, 58, 58, 46, 40, 5, 2, 1, 1, 2, 5, 42, 64, 72, 76, 72, 64, 42, 5, 2, 1

Offset: 0

Author

Matej Veselovac, Oct 07 2019

Keywords

• nonn
• tabl

Comments

The terms of the sequence, when observed in conjunction with prime gaps of size <= T(k, n), can be used to determine natural numbers N which are "trivially" sums of exactly k+1 distinct primes. For example, if we observe k=9, n=12, this leads to conclusion that numbers N=179,...,15683 can be "trivially" represented as sums of exactly ten (k+1=9+1=10) distinct primes. That is, firstly, we have T(9, 12)=42. The starting value of the longest 42-long run is 138, and the next distinct prime, the 13(=n+1=12+1)th prime, is 41. This gives the number 138+41=179 as the smallest such "trivially" representable number. Secondly, the first smallest prime gap larger than T(9, 12)=42 is 44, appearing after (prime) number 15683, and the prime gaps before it are at most 36 < 42. Finally, all this implies that all numbers N=179,...,15683 have a "trivial" representation as a sum of exactly ten (k+1=9+1=10) distinct primes, since (k=9)-long combinations of the first n=12 primes are enough to cover all prime gaps (2,...,36 < 42) up to number 15683, when combined with tenth (k+1=9+1=10th among the summed primes) distinct (n+1=12+1=13th or larger among primes) prime p=41,...,15683.

Note that in the previous example, the 179,15683 are not smallest,largest such numbers in general, but just smallest,largest such "trivially" representable numbers. Determining the sets (intervals) of such "trivial" numbers, reduces the set of "nontrivial" such numbers that we need to check with other means, in more general cases.

A trivial upper bound is binomial(k, n) >= T(k, n), since there are binomial(k, n) k-long combinations of a set with n elements, and not necessarily all sums of those combinations are consecutive.

Examples

			Specially, if k=0, then we do not have sums, and this is defined as 1 = T(0, n).
Trivially, if k=n, then T(n, n) = 1, since we have only one sum, the sum of first n prime numbers.
Nontrivial example: if n=4, we have first four primes {2,3,5,7}. Now, for example, if k=2, we have the following sums of 2-combinations: "5,7,8,9,10,12", since:
{2,3} -> 2+3 = 5
{2,5} -> 2+5 = 7
{3,5} -> 3+5 = 8
{2,7} -> 2+7 = 9
{3,7} -> 3+7 = 10
{5,7} -> 5+7 = 12
We now see that the triangle entry is: T(k=2, n=4)=4, since "7,8,9,10" is the longest run of consecutive sums of 2-combinations of first 4 primes.
First 16 rows of triangle T(k, n) where n=0..15, k=0..n:
1;
1, 1;
1, 2, 1;
1, 2, 2,  1;
1, 2, 4,  2,  1;
1, 2, 4,  4,  2,   1;
1, 2, 5,  6,  5,   2,   1;
1, 2, 5, 10, 10,   5,   2,   1;
1, 2, 5, 18, 16,  18,   5,   2,   1;
1, 2, 5, 22, 28,  28,  22,   5,   2,   1;
1, 2, 5, 22, 38,  46,  38,  22,   5,   2,   1;
1, 2, 5, 40, 46,  58,  58,  46,  40,   5,   2,  1;
1, 2, 5, 42, 64,  72,  76,  72,  64,  42,   5,  2,  1;
1, 2, 5, 46, 70,  94,  94,  94,  94,  70,  46,  5,  2, 1;
1, 2, 5, 60, 76, 102, 118, 114, 118, 102,  76, 60,  5, 2, 1;
1, 2, 5, 66, 94, 124, 130, 142, 142, 130, 124, 94, 66, 5, 2, 1;
		

Links

• Matej Veselovac, (T(k, n) mod n) mod 2 visualization..
• Math StackExchange, How many natural number between 100 and 1000 exist which can be expressed as sum of 10 different primes..
• Wikipedia, Numerical results on prime gaps.

Crossrefs

Cf. A000040 (prime numbers).

Cf. A001223 (prime gaps), A005250 (record prime gaps), A002386 (Record prime gaps primes).

Programs

Python

p = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]
from itertools import combinations, groupby, count
def T(k, n):
    if k==0:
        return [0]
    lst = sorted(set([sum(combo) for combo in combinations(p[:n], k)]))
    c = count()
    return max((list(g) for _, g in groupby(lst, lambda x: x-next(c))), key=len)
for n in range(len(p)+1):
    for k in range(n+1):
        print(len(T(k,n)),end=", ")
    #print()