login
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.
0
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,5
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.
EXAMPLE
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;
PROG
(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()
CROSSREFS
Cf. A000040 (prime numbers).
Cf. A001223 (prime gaps), A005250 (record prime gaps), A002386 (Record prime gaps primes).
Sequence in context: A238392 A144464 A138015 * A103444 A099172 A214246
KEYWORD
nonn,tabl
AUTHOR
Matej Veselovac, Oct 07 2019
STATUS
approved