Fondo

Para este desafío, una 'metasecuencia' se definirá como una secuencia de números donde no solo los números aumentarán, sino también el incremento, y el incremento aumentará en un valor creciente, etc.

Por ejemplo, la metasecuencia de nivel 3 comenzaría como:

1 2 4 8 15 26 42 64 93 130 176

porque:

    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 <-|

Reto

Dado un número entero positivo, genera los primeros veinte elementos de la metasecuencia de ese nivel.

Casos de prueba

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

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

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

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

Como te darás cuenta, los primeros elementos $t+1$ de cada secuencia del nivel $t$ son los primeros poderes $t+1$ de 2 ...

Reglas

• Se aplican lagunas estándar
• Este es el código de golf , por lo que la respuesta más corta en bytes gana

Jalea , 8 7 bytes

20ḶcþŻS

Pruébalo en línea!

   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, …]

Esto utiliza la idea de @ alephalpha de que la

Wolfram Language (Mathematica) , 34 bytes

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

Pruébalo en línea!

La metasecuencia de nivel $n$ es la suma de los primeros $n+1$ elementos de cada fila del triángulo de Pascal.

Haskell , 34 bytes

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

Utiliza entradas indexadas 0 ( f 4devuelve el nivel 5)

Haskell , 36 bytes

f 1=[1..20]
f n=init$scanl(+)1$f$n-1

Pruébalo en línea! Utiliza entradas indexadas 1 ( f 5devuelve el nivel 5)

Explicación

scanl (+) 1es una función que toma sumas parciales de una lista, comenzando desde (y hasta antes) 1.

Por ejemplo: scanl (+) 1 [20,300,4000]igual [1,21,321,4321].

Resulta que el nivel $n$ es solo esta función aplicada $(n-1)$ veces a la lista $[1,2,3,\dots]$ .

(O equivalente: $n$ veces a una lista de todos).

Usamos inito [1..20-n]para dar cuenta de que la lista se alarga en $1$ cada aplicación.

Brain-Flak , 84 82 bytes

<>((()()()()()){}){({}[((()))])}{}<>{({}[(())]<<>{({}<>({}))<>}<>{}{({}<>)<>}>)}<>

Pruébalo en línea!

Anotado

<>               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

Pruébalo en línea!

R , 36 bytes

rowSums(outer(0:19,0:scan(),choose))

Pruébalo en línea!

Gracias a @Giuseppe por sugerir outer.

Esto se basa en el enfoque descrito por @alephalpha

Python 2 , 69 58 55 bytes

Bytes guardados gracias a ovs y Jo King ; Además, ahora también funciona en Python 3.

m=lambda t:[1+sum(m(t-1)[:n])for n in range(~t and 20)]

Pruébalo en línea!

Las matemáticas

Sea $a(t,n)$ el término $n^{th}$ (indexado en 0) de la secuencia en el nivel $t$ . Un pequeño análisis lleva a la siguiente fórmula de recurrencia:

Trabajando hacia atrás, definimos $a(0,n) = 1$ y $a(-1,n) = 0$ para todo $n$ . Estas definiciones simplificarán nuestro caso base.

El código

Definimos una función m(t)que devuelve los primeros 20 elementos de la secuencia en el nivel t. Si tno es negativo, usamos la fórmula recursiva anterior; si tes así -1, devolvemos una lista vacía. La lista vacía funciona como un caso base porque el resultado de cada llamada recursiva se divide ( [:n]) y luego se suma. Cortar una lista vacía da una lista vacía, y sumar una lista vacía da 0. Eso es exactamente el resultado que queremos, ya nivel $-1$ debería comportarse como una secuencia constante de todos $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)

dzaima / APL REPL, 14 bytes

(+\1,19↑)⍣⎕⍳20

Pruébalo en línea!

(+\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

Pari / GP , 39 bytes

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

Pruébalo en línea!

Pari / GP , 40 bytes

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

Pruébalo en línea!

$n$

Perl 6 , 34 32 bytes

-2 bytes gracias a Jo King

{(@,{[\+] 1,|.[^19]}...*)[$_+1]}

Pruébalo en línea!

Explicación

{                              }  # Anonymous block
   ,                ...*  # Construct infinite sequence of sequences
  @  # Start with empty array
    {              }  # Compute next element as
     [\+]     # cumulative sum of
          1,  # one followed by
            |.[^19]  # first 19 elements of previous sequence
 (                      )[$_+1]  # Take (n+1)th element

Python 3.8 (prelanzamiento) , 62 bytes

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

Pruébalo en línea!

Explicación

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)

Demo en línea . Esto utiliza la función beta incompleta regularizada , que proporciona la función de distribución acumulativa de un binomio y, por lo tanto, solo necesita un poco de escala para dar sumas parciales de filas del triángulo de Pascal.

Octava ( 66 46 bytes)

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

Demo en línea . Exactamente el mismo concepto, pero un poco más feo porque betainc, a diferencia de los R pbeta, requiere que el segundo y el tercer argumento sean mayores que cero.

Muchas gracias a Giuseppe por ayudarme a vectorizarlos, con ahorros significativos.

Ruby, 74 bytes

a=->b{c=[1];d=0;b==1?c=(1..20).to_a: 19.times{c<<c[d]+(a[b-1])[d];d+=1};c}

Versión sin golf:

def seq num
    ary = [1]
    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

Muy intensivo en recursos: la versión en línea no puede calcular la 13ª metasecuencia.

Pruébalo en línea

Wolfram Language (Mathematica) , 42 bytes

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

Pruébalo en línea!

JavaScript (Node.js) , 58 bytes

t=>Array(20).fill(t).map(g=(t,i)=>i--*t?g(t,i)+g(t-1,i):1)

Pruébalo en línea!

Es trivial escribir la siguiente fórmula recursiva basada en la descripción en cuestión.

05AB1E , 11 9 bytes

20LIF.¥>¨

0 indexado

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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, output the result-list implicitly)

R , 59 49 bytes

f=function(n)`if`(n,Reduce(`+`,f(n-1),1,,T),1:20)

Pruébalo en línea!

Recursivamente Reducecon +, init=1y accumulation=TRUEpara evitar tener que subconjunto. ¡Gracias a Criminally Vulgar por sugerir el enfoque recursivo!

JavaScript (ES6),  68  67 bytes

f=(n,a=[...f+f])=>n--?f(n,[s=1,...a.map(x=>s-=~--x)]):a.slice(0,20)

Pruébalo en línea!

JavaScript (ES6), 63 bytes

NB: esta versión funciona para $n\le20$.

f=(n,a=[...Array(20-n)])=>n--?f(n,[s=1,...a.map(x=>s+=x||1)]):a

Pruébalo en línea!

J , 24 bytes

<:(1+/\@,])^:[(1+i.20)"_

Pruébalo en línea!

NOTA: Resulta que esta es una traducción de la respuesta APL de dzaima, aunque en realidad no me di cuenta antes de escribir esto.

explicación

<: (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?[1]*20:[o=1]+f[n-1][0,19].map{|x|o+=x}}

Definición recursiva: el nivel 0 es 1,1,1,1...y cada nivel subsiguiente es 1 seguido de una secuencia cuyas primeras diferencias son el nivel anterior. Molesto, esto me daría 21 valores si no cortara explícitamente los primeros 20; Parece que debería haber una forma de acortar esto evitando eso.

Retina , 59 bytes

.+
19*$(_,

Reemplace la entrada con 19 1s (en unario). (El valor 20 es 0 porque siempre se elimina en el primer paso a través del ciclo).

"$+"{`
)`

Repita el ciclo el número de entrada original de veces.

(.+),_*
_,$1

Elimine el último elemento y prefijo a 1.

_+(?<=((_)|,)+)
$#2*

Calcule la suma acumulativa.

_+
$.&

Convierte a decimal.

Pruébalo en línea!

C # (compilador interactivo de Visual C #) , 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;}

Pruébalo en línea!

Basado en la fórmula de alephalpha.

Óxido , 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()}

usé la idea de @alephalpha, como muchas otras. no hay factorial incorporado, por lo que ocupa al menos 36 bytes (además de tratar con negativos). sin elegir, otros 16 bytes. iterador-> tipo de vector declarado, 20 bytes ... etc. etc.

Sin golf en play.rust-lang.org

R ( 60 59 bytes)

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

Demostración en línea

Implementación directa de la observación

T (n, k) = 2 T (n-1, k) - binomio (n-1, k). - MF Hasler, 30 de mayo de 2010

de OEIS A008949 . Los argumentos para Reduceson la función (obviamente), la matriz sobre la cual asignar, el valor inicial, un valor falso (doblar desde la izquierda en lugar de la derecha) y un valor verdadero para acumular los resultados intermedios en una matriz.

K (oK) , 17 bytes

-1 byte gracias a ngn (cambio de 0 indexado a 1 indexado)

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

Pruébalo en línea!

1 indexado

K (oK) , 18 bytes

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

Pruébalo en línea!

0 indexado

Jalea , 10 bytes

20RṖ1;ÄƲ⁸¡

Pruébalo en línea!

0 indexado.

Perl 5, 48 bytes

$x=1,@A=(1,map$x+=$_,@A[0..18])for 0..$_;$_="@A"

TIO

Japt , 15 bytes

0 indexado; reemplazar hcon p1 indexado.

ÈîXi1 å+}gNh20õ

Intentalo

CJam (20 bytes)

1aK*{1\{1$+}/;]}q~*p

Demo en línea . Este es un programa que toma datos de stdin e imprime en stdout; para el mismo puntaje se puede obtener un bloque anónimo (función) como

{1aK*{1\{1$+}/;]}@*}

Disección

Esto aplica la definición literalmente:

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