login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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.

LINKS

Table of n, a(n) for n=0..90.

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.

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

Adjacent sequences:  A327739 A327740 A327741 * A327743 A327744 A327745

KEYWORD

nonn,tabl

AUTHOR

Matej Veselovac, Oct 07 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 11:50 EDT 2021. Contains 348212 sequences. (Running on oeis4.)