# Background

For this challenge, a 'metasequence' will be defined as a sequence of numbers where not only the numbers themselves will increase, but also the increment, and the increment will increase by an increasing value, etc.

For instance, the tier 3 metasequence would start as:

1 2 4 8 15 26 42 64 93 130 176

because:

1 2 3  4  5  6  7  8   9       >-|
↓+↑ = 7                        | Increases by the amount above each time
1 2 4 7  11 16 22 29 37  46  >-| <-|
| Increases by the amount above each time
1 2 4 8 15 26 42 64 93 130 176 <-|

# Challenge

Given a positive integer, output the first twenty terms of the metasequence of that tier.

## Test cases

Input: 3 Output: [ 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160 ]

Input: 1 Output: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]

Input: 5 Output: [ 1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664 ]

Input: 13 Output: [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16383, 32752, 65399, 130238, 258096, 507624 ]

As you may realise, the first $$\t+1\$$ items of each sequence of tier $$\t\$$ are the first $$\t+1\$$ powers of 2...

# Rules

• Standard loopholes apply
• This is , so shortest answer in bytes wins
• I assume you mean 20 terms, not digits? Commented Mar 4, 2019 at 17:09
• By the way, the tier three metasequence is OEIS A000125 Commented Mar 4, 2019 at 17:31
• You may want to clarify if solutions have to work for input 20 or greater. Commented Mar 4, 2019 at 17:46
• Can we choose to 0-index (so, output tier 1 for input 0, tier 2 for input 1, etc.)?
– lynn
Commented Mar 4, 2019 at 18:06
• @MilkyWay90, it's not very clear what you mean: 219 (from level 5) only occurs in Pascal's triangle as $\binom{219}{1}$ and $\binom{219}{218}$. Commented Mar 5, 2019 at 11:04

# Wolfram Language (Mathematica), 34 bytes

0~Range~19~Binomial~i~Sum~{i,0,#}&

Try it online!

The tier $$\n\$$ metasequence is the sum of the first $$\n+1\$$ elements of each row of the Pascal triangle.

• There's almost a built-in for that, but unfortunately it's longer. Commented Mar 5, 2019 at 12:41
• I don't know enough WL to do anything useful in it, but it seems to me that it might benefit from the identity $$T(n,k) = \begin{cases}1 & \textrm{if }k=0 \\ 2T(n,k-1) - \binom{k-1}{n} & \textrm{otherwise}\end{cases}$$ Commented Mar 5, 2019 at 15:13

(iterate(init.scanl(+)1)[1..20]!!)

Uses 0-indexed inputs (f 4 returns tier 5.)

f 1=[1..20]

Try it online!

### Explanation

{                              }  # Anonymous block
,                ...*  # Construct infinite sequence of sequences
{              }  # Compute next element as
[\+]     # cumulative sum of
1,  # one followed by
|.[^19]  # first 19 elements of previous sequence
(                      )[$_+1] # Take (n+1)th element • 29 bytes (the$^a instead of $_ is necessary) – Jo King Commented Mar 4, 2019 at 22:18 • @JoKing Nice, but this assumes that$_ is undefined when calling the function. I prefer solutions that don't depend on the state of global variables. Commented Mar 5, 2019 at 9:47

# Python 3.8 (pre-release), 62 bytes

f=lambda n:[t:=1]+[t:=t+n for n in(n and f(n-1)[:-1]or[0]*19)]

Try it online!

## Explanation

f=lambda n:     # funtion takes a single argument
[t:=1]     # This evaluates to [1] and assigns 1 to t
# assignment expressions are a new feature of Python 3.8
+        # concatenated to
[  ....  ] # list comprehension

# The list comprehesion works together with the
# assignment expression as a scan function:
[t := t+n for n in it]
# This calculates all partial sums of it
# (plus the initial value of t, which is 1 here)

# The list comprehension iterates
# over the first 19 entries of f(n-1)
# or over a list of zeros for n=0
for n in (n and f(n-1)[:-1] or [0]*19)

## R (63 47 bytes)

function(n,k=0:19)2^k*pbeta(.5,pmax(k-n,0),n+1)

Online demo. This uses the regularised incomplete beta function, which gives the cumulative distribution function of a binomial, and hence just needs a bit of scaling to give partial sums of rows of Pascal's triangle.

## Octave (66 46 bytes)

@(n,k=0:19)2.^k.*betainc(.5,max(k-n,1E-9),n+1)

Online demo. Exactly the same concept, but slightly uglier because betainc, unlike R's pbeta, requires the second and third arguments to be greater than zero.

Many thanks to Giuseppe for helping me to vectorise these, with significant savings.

# Pari/GP, 36 bytes

n->vector(20,i,i<n+2)*matpascal(19)~

Try it online!

A port of my Mathematica answer.

# Pari/GP, 39 bytes

n->Vec(sum(i=1,n+1,(1/x-1)^-i)+O(x^21))

Try it online!

# Pari/GP, 40 bytes

n->Vec((1-(1/x-1)^-n++)/(1-2*x)+O(x^20))

Try it online!

The generating function of the tier $$\n\$$ metasequence is:

$$\sum_{i=0}^n\frac{x^i}{(1-x)^{i+1}}=\frac{1-\left(\frac{x}{1-x}\right)^{1+n}}{1-2x}$$

# Wolfram Language (Mathematica), 42 bytes

Nest[FoldList[Plus,1,#]&,Range[21-#],#-1]&

Try it online!

# Retina, 59 bytes

.+
19*$(_, Replace the input with 19 1s (in unary). (The 20th value is 0 because it always gets deleted by the first pass through the loop.) "$+"{
)

Repeat the loop the original input number of times.

(.+),_*
_,$1 Remove the last element and prefix a 1. _+(?<=((_)|,)+)$#2*

Calculate the cumulative sum.

_+

TIO

## R (60 59 bytes)

function(n)Reduce(function(p,q)2*p-choose(q-1,n),1:19,1,,1)

Online demo

Straightforward implementation of the observation

T(n,k) = 2 T(n-1,k) - binomial(n-1,k). - M. F. Hasler, May 30 2010

from OEIS A008949. The arguments to Reduce are the function (obviously), the array over which to map, the starting value, a falsy value (to fold from the left rather than the right), and a truthy value to accumulate the intermediate results in an array.

# K (oK), 17 bytes

-1 byte thanks to ngn (switching from 0-indexed to 1-indexed)

{x(+\1,19#)/20#1}

Try it online!

1-indexed

# K (oK), 18 bytes

{x(+\1,19#)/1+!20}

Try it online!

0-indexed

• make it 1-indexed and save a byte: 1+!20 -> 20#1
– ngn
Commented Mar 6, 2019 at 10:36
• @ngn Thanks, as always there's something I've missed :) Commented Mar 6, 2019 at 11:59

20RṖ1;ÄƲ⁸¡

Try it online!

0-indexed.

# Japt, 15 bytes

0-indexed; replace h with p for 1-indexed.

ÈîXi1 å+}gNh20õ

Try it

## CJam (20 bytes)

1aK*{1\{1$+}/;]}q~*p Online demo. This is a program which takes input from stdin and prints to stdout; for the same score an anonymous block (function) can be obtained as {1aK*{1\{1$+}/;]}@*}

### Dissection

This applies the definition literally:

{         e# Loop:
1\      e#   Push a 1 before the current list
{1\$+}/  e#   Form partial sums (including that bonus 1)
;]      e#   Ditch the last and gather in an array (of length 20)
}
q~*       e# Take input and repeat the loop that many times
p         e# Pretty print

# VyxalR, 7 bytes

20⁰(ÞR›

Try it Online!

0-indexed.

## How?

20⁰(ÞR›
20      # Push number 20
⁰(    # Loop input times
ÞR  # Take the cumulative sum of list (20, R flag makes this a [1, 20] range), remove last item, and prepend 0. Short for ¦Ṫ0p
› # Increment (implicit vectorization)

# VyxalRM, 7 bytes

19ƛ⁰ʀƈ∑

Try it Online!

1-indexed.

## How?

19ƛ⁰ʀƈ∑
19      # Push the number 19
ƛ     # Map, R and M flags make this be a [0, 19] range
⁰ʀ   # Inclusive zero range of input
ƈ  # Binomial coefficient, implicit vectorization
∑ # Sum these binomimal coefficients