# 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? Mar 4, 2019 at 17:09
• By the way, the tier three metasequence is OEIS A000125 Mar 4, 2019 at 17:31
• You may want to clarify if solutions have to work for input 20 or greater. 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
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}$. 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. 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}$$ 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]
f n=init$scanl(+)1$f$n-1  Try it online! Uses 1-indexed inputs (f 5 returns tier 5.) # Explanation scanl (+) 1 is a function that takes partial sums of a list, starting from (and prepending) 1. For example: scanl (+) 1 [20,300,4000] equals [1,21,321,4321]. It turns out that tier $$\n\$$ is just this function applied $$\ (n-1) \$$ times to the list $$\[1,2,3,\dots]\$$. (Or equivalently: $$\n\$$ times to a list of all ones.) We use either init or [1..20-n] to account for the list getting longer by $$\1\$$ every application. • [1..20-n] isn't going to work for $n > 20$ Mar 5, 2019 at 11:30 • take 20.(iterate(scanl(+)1)[1..]!!) would only cost a byte more to fix that Mar 5, 2019 at 16:27 • Your pointfree answer can be back to 34 bytes using your other answer: (iterate(init.scanl(+)1)[1..20]!!). – xnor Mar 6, 2019 at 1:52 # Jelly, 8 7 bytes 20ḶcþŻS  Try it online!  cþ Table of binom(x,y) where: 20Ḷ x = [0..19] Ż y = [0..n] e.g. n=3 → [[1, 1, 1, 1, 1, 1, …] [0, 1, 2, 3, 4, 5, …] [0, 0, 1, 3, 6, 10, …] [0, 0, 0, 1, 4, 10, …]] S Columnwise sum. → [1, 2, 4, 8, 15, 26, …]  This uses @alephalpha’s insight that $$\text{meta-sequence}_n(i) = \sum_{k=0}^n \binom ik.$$ • That is brutally succint. Just awesome. Mar 6, 2019 at 2:54 # Brain-Flak, 84 82 bytes <>((()()()()()){}){({}[((()))])}{}<>{({}[(())]<<>{({}<>({}))<>}<>{}{({}<>)<>}>)}<>  Try it online! ## Annotated <> Switch to the off stack ((()()()()()){}) Push 10 {({}[((()))])}{} Make twice that many 1s <> Switch back { While ... ({}[(())]< Subtract one from the input and push 1 <> Switch { For every x on the stack ({}<>({}))<> Remove x and add it to a copy of the other TOS } End loop <>{} Remove 1 element to keep it 20 {({}<>)<>} Copy everything back to the other stack >)}<> End scopes and loops  Try it online! • you know its funny how this is shorter than Rust Mar 6, 2019 at 3:06 # R, 36 bytes rowSums(outer(0:19,0:scan(),choose))  Try it online! Thanks to @Giuseppe for suggesting outer. This is based on the approach @alephalpha described • you might be able to use Map instead of outer? – JDL Mar 7, 2019 at 14:05 • @JDL I can’t see how that would work. I need every possible combination, not just pairs of combinations. Mar 7, 2019 at 14:38 # dzaima/APL REPL, 14 bytes (+\1,19↑)⍣⎕⍳20  Try it online! (+\1,19↑)⍣⎕⍳20 ( )⍣⎕ repeat the function below input times: +\ cumulative sum of 1, 1 prepended to 19↑ the first 19 items of the previous iteration ⍳20 starting with the first 20 integers  • -1 byte using dzaima/APL: 1∘,1, – Adám Mar 4, 2019 at 17:59 • @Adám oh duh.. right Mar 4, 2019 at 18:02 • Full program at 17: (≢↑(+\1∘,)⍣⎕)20⍴1 – Adám Mar 4, 2019 at 18:04 • 14 bytes by using the REPL (add the -s flag). Mar 4, 2019 at 19:26 • If you use the flag, language becomes -s btw (unless -s is repl flag?) Mar 5, 2019 at 0:08 # Python 2, 6958 55 bytes Saved bytes thanks to ovs and Jo King; also, it works in Python 3 now as well. m=lambda t:[1+sum(m(t-1)[:n])for n in range(~t and 20)]  Try it online! ### The math Let $$\a(t,n)\$$ be the $$\n^{th}\$$ term (0-indexed) of the sequence at tier $$\t\$$. A little analysis leads to the following recurrence formula: $$a(t,n) = 1+\sum_{i=0}^{n-1}a(t-1,i)$$ Working backwards, we define $$\a(0,n) = 1\$$ and $$\a(-1,n) = 0\$$ for all $$\n\$$. These definitions will simplify our base case. ### The code We define a function m(t) that returns the first 20 elements of the sequence at tier t. If t is nonnegative, we use the recursive formula above; if t is -1, we return an empty list. The empty list works as a base case because the result of each recursive call is sliced ([:n]) and then summed. Slicing an empty list gives an empty list, and summing an empty list gives 0. That's exactly the result we want, since tier $$\-1\$$ should behave like a constant sequence of all $$\0\$$'s. m=lambda t: # Define a function m(t): [ ] # List comprehension for n in range( ) # for each n from 0 up to but not including... ~n and 20 # 0 if n is -1, else 20: 1+sum( ) # a(t,n) = 1 + sum of [:n] # the first n elements of m(t-1) # the previous tier (calculated recursively)  • 61 bytes as a recursive lambda function (Significantly more inefficient). – ovs Mar 4, 2019 at 22:34 • @ovs Thanks! I found a couple more bytes by using a different base case, too. Mar 4, 2019 at 22:49 • :( the nice way is too long Mar 4, 2019 at 23:13 • (t>=0)*range(20) saves a byte, though there's probably a yet shorter expression. – xnor Mar 6, 2019 at 1:53 • if~t saves two more over @xnor – Jo King Mar 7, 2019 at 11:12 # Perl 6, 34 32 bytes -2 bytes thanks to Jo King {(@,{[\+] 1,|.[^19]}...*)[$_+1]}


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 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. 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*19)]


Try it online!

## Explanation

f=lambda n:     # funtion takes a single argument
[t:=1]     # This evaluates to  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 *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.

_+
$.&  Convert to decimal. Try it online! # JavaScript (Node.js), 58 bytes t=>Array(20).fill(t).map(g=(t,i)=>i--*t?g(t,i)+g(t-1,i):1)  Try it online! It is trivial to write down following recursive formula based on the description in question $$g(t,i)=\begin{cases} g(t,i-1)+g(t-1,i-1) & \text{if} \quad i\cdot t>0 \\ 1 & \text{if} \quad i\cdot t=0 \\ \end{cases}$$ And you just need to generate an Array of 20 elements with $$\[g(t,0)\dots g(t,19)]\$$ • 57? Mar 22, 2020 at 0:37 # Rust, 135 bytes fn t(m:u64)->Vec<u64>{let f=|y|(1..=y).fold(1,|a,n|a*n);(0..20).map(|i| (0..=u64::min(i,m)).fold(0,|a,x|a+f(i)/f(x)/f(i-x))).collect()}  used @alephalpha 's idea, like several others. there is no builtin factorial so that takes up at least 36 bytes, (plus dealing with negatives). no builtin choose, another 16 bytes. iterator->declared vector type, 20 bytes.. etc etc. Ungolfed at play.rust-lang.org • There's a better way to calculate binomial coefficients for the same cost but which allows removing the min: fn t(m:i64)->Vec<i64>{let b=|n,k|(1..=k).fold(1,|a,j|a*(n-j+1)/j);(0..20).map(|i|(0..=m).fold(0,|a,x|a+b(i,x))).collect()} (122 bytes) Mar 6, 2019 at 11:27 • In fact, the binomial can be inlined: fn t(m:i64)->Vec<i64>{(0..20).map(|i|(0..=m).fold(0,|a,x|a+(1..=x).fold(1,|a,j|a*(i-j+1)/j))).collect()} (104 bytes). What would be nice is to combine the two folds, but I'm not sure how succinct tuples are. Mar 6, 2019 at 14:36 • Succinct enough: fn t(m:i64)->Vec<i64>{(0..20).map(|i|(0..=m).fold((0,1),|a,b|(a.0+a.1,a.1*(b-i)/!b)).0).collect()} (98 bytes) Mar 6, 2019 at 15:59 • thats amazing... i struggle to even understand how it works but its amazing. Mar 7, 2019 at 0:02 • It just uses one algebraic trick: $$\frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-(k-1))!} \times \frac{n-k+1}{k}$$ Mar 7, 2019 at 10:23 # R, 59 49 bytes f=function(n)if(n,Reduce(+,f(n-1),1,,T),1:20)  Try it online! Recursively Reduce with +, init=1 and accumulation=TRUE to avoid having to subset. Thanks to Criminally Vulgar for suggesting the recursive approach! • tio this is only 39 bytes (using binomial approach) Mar 5, 2019 at 22:37 • @NickKennedy that's a separate approach, so I'd recommend posting it yourself, and it's golfier to use outer than sapply for 36 bytes Mar 5, 2019 at 22:51 • Converting this approach to a recursive function gives 53 bytes (I think in recursives we need to include the assignment? If not, 51) TIO Mar 6, 2019 at 12:27 • @CriminallyVulgar we can get to 49 bytes :-) Mar 6, 2019 at 16:34 • @Giuseppe Haha I knew it was golfable, just couldn't see it! I messed with cumsum for a while to try and make it work, but that Reduce is so slick. Nice to be able to drop the index by 1 as well, didn't see that in the comments. Mar 7, 2019 at 8:41 # 05AB1E, 119 8 bytes 19ÝIÝδcO  1-indexed -1 byte by porting @alephalpha's Mathematica answer, so make sure to upvote him!! Explanation: 19Ý # Push a list in the range [0, 19] IÝ # Push a list in the range [0, input-integer] δ # Apply on the two lists double-vectorized (as a table): c # The binomial coefficient O # And then sum each inner list # (after which the resulting list is output implicitly)  Old 11 9 bytes answer: 20LIF.¥>¨  0-indexed Explanation: 20L # Create a list in the range [1,20] IF # Loop the input amount of times: .¥ # Get the cumulative sum of the current list with 0 prepended automatically > # Increase each value in this list by 1 ¨ # Remove the trailing 21th item from the list # (after the loop, the result-list is output implicitly)  • Nice use of .¥! Mar 5, 2019 at 9:03 # Ruby, 74 bytes a=->b{c=;d=0;b==1?c=(1..20).to_a: 19.times{c<<c[d]+(a[b-1])[d];d+=1};c} Ungolfed version: def seq num ary =  index = 0 if num == 1 ary = (1..20).to_a else 19.times{ary << ary[index]+seq(num-1)[index]; index+=1} end return ary end  Quite resource-intensive--the online version can't calculate the 13th metasequence. Try it online # JavaScript (ES6), 68 67 bytes f=(n,a=[...f+f])=>n--?f(n,[s=1,...a.map(x=>s-=~--x)]):a.slice(0,20)  Try it online! # JavaScript (ES6), 63 bytes NB: this version works for $$\n\le20\$$. f=(n,a=[...Array(20-n)])=>n--?f(n,[s=1,...a.map(x=>s+=x||1)]):a  Try it online! # J, 24 bytes <:(1+/\@,])^:[(1+i.20)"_  Try it online! NOTE: Turns out this is a translation of dzaima's APL answer, though I actually didn't notice it before writing this. ## explanation <: (1 +/\@, ])^:[ (1+i.20)"_ <: NB. input minus 1 (left input) (1+i.20)"_ NB. 1..20 (right input) ( )^:[ NB. apply verb in parens NB. "left input" times (1 , ]) NB. prepend 1 to right input ( +/\@ ) NB. and take scan sum  # Ruby, 49 bytes f=->n{n<1?*20:[o=1]+f[n-1][0,19].map{|x|o+=x}}  Recursive definition: Tier 0 is 1,1,1,1... and each subsequent tier is 1 followed by a sequence whose first differences are the previous tier. Annoyingly this would give me 21 values if I didn't explicitly slice out the first 20; seems like there should be a way to shorten this by avoiding that. • Mar 4, 2019 at 23:45 • also 49 Mar 4, 2019 at 23:46 • 46 Mar 5, 2019 at 0:03 # C# (Visual C# Interactive Compiler), 120 bytes n=>{for(long i=-1,h=0,m=0;++i<20;Print(i<1?1:h))for(m=h=0;m<=n;)h+=f(i)/(f(m)*f(i-m++));long f(long a)=>a>1?a*f(a-1):1;}  Try it online! Based off of alephalpha's formula. # Perl 5, 48 bytes $x=1,@A=(1,map$x+=$_,@A[0..18])for 0..$_;$_="@A"


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
Mar 6, 2019 at 10:36
• @ngn Thanks, as always there's something I've missed :) Mar 6, 2019 at 11:59

# Jelly, 10 bytes

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:

1aK*      e# Start with an array of 20 1s
{         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