Hazme una metasecuencia

25

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 , por lo que la respuesta más corta en bytes gana
Geza Kerecsenyi
fuente
2
¿Asumo que quieres decir 20 términos, no dígitos?
Quintec
44
Por cierto, la metasecuencia de nivel tres es OEIS A000125
Encarnación de la ignorancia
66
Es posible que desee aclarar si las soluciones tienen que funcionar para la entrada 20 o superior.
FryAmTheEggman
44
¿Podemos elegir el índice 0 (entonces, nivel de salida 1 para entrada 0, nivel 2 para entrada 1, etc.)?
Lynn
1
@ MilkyWay90, no está muy claro lo que quieres decir: 219 (desde el nivel 5) solo ocurre en el triángulo de Pascal como y ( 219(2191) . (219218)
Peter Taylor

Respuestas:

8

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

meta-sequencen(i)=k=0n(ik).

Lynn
fuente
Eso es brutalmente sucinto. Simplemente impresionante.
Don brillante
22

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.

alephalpha
fuente
1
Hay casi un incorporado para eso , pero desafortunadamente es más largo.
Peter Taylor
1
No sé suficiente WL para hacer algo útil en él, pero me parece que podría beneficiarse de la identidad
T(norte,k)={1Si k=0 02T(norte,k-1)-(k-1norte)de otra manera
Peter Taylor
17

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 norte es solo esta función aplicada (norte-1) veces a la lista [1,2,3,...] .

(O equivalente: norte 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.

Lynn
fuente
1
[1..20-n]no va a funcionar para norte>20
Peter Taylor
take 20.(iterate(scanl(+)1)[1..]!!)solo costaría un byte más para arreglar eso
H.PWiz
1
Su respuesta puede ser pointfree de nuevo a 34 bytes utilizando su otra respuesta: (iterate(init.scanl(+)1)[1..20]!!).
xnor
7

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!

Asistente de trigo
fuente
3
sabes que es divertido cómo esto es más corto que Rust
don brillante
7

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

Nick Kennedy
fuente
podrías usar en Maplugar de externo?
JDL
@JDL No puedo ver cómo funcionaría eso. Necesito todas las combinaciones posibles, no solo pares de combinaciones.
Nick Kennedy
5

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 nth (indexado en 0) de la secuencia en el nivel t . Un pequeño análisis lleva a la siguiente fórmula de recurrencia:

a(t,n)=1+i=0n1a(t1,i)

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)
DLosc
fuente
61 bytes como una función lambda recursiva (significativamente más ineficiente).
ovs
@ovs Gracias! También encontré un par de bytes más usando un caso base diferente.
DLosc
1
(t>=0)*range(20)guarda un byte, aunque probablemente haya una expresión aún más corta.
xnor
1
if~tahorra dos más sobre @xnor
Jo King
4

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
dzaima
fuente
-1 byte usando dzaima / APL: 1∘,1,
Adám
@ Adám oh duh .. correcto
dzaima
Programa completo a las 17:(≢↑(+\1∘,)⍣⎕)20⍴1
Adám
14 bytes usando REPL (agregue la -sbandera).
Erik the Outgolfer
Si usa el indicador, el idioma se convierte en -sBTW (a menos que -ssea ​​el indicador de respuesta?)
Solo ASCII
3

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!


norte

yo=0 0norteXyo(1-X)yo+1=1-(X1-X)1+norte1-2X

alephalpha
fuente
3

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
nwellnhof
fuente
29 bytes (el en $^alugar de $_es necesario)
Jo King
1
@JoKing Nice, pero esto supone que $_no está definido al llamar a la función. Prefiero soluciones que no dependen del estado de las variables globales.
nwellnhof
3

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)
ovs
fuente
3

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.

Peter Taylor
fuente
2

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

CG One Handed
fuente
2

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.

sol(t,yo)={sol(t,yo-1)+sol(t-1,yo-1)Siyot>0 01Siyot=0 0
Y solo necesita generar una matriz de 20 elementos con [sol(t,0 0)...sol(t,19)]

tsh
fuente
2

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)
Kevin Cruijssen
fuente
1
Buen uso de !
Emigna
2

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!

Giuseppe
fuente
tio esto es solo 39 bytes (usando el enfoque binomial)
Nick Kennedy
@NickKennedy es un enfoque diferente, por lo que recomiendo publicarlo usted mismo, y es más elegante de usar outerque sapplypara 36 bytes
Giuseppe
1
La conversión de este enfoque a una función recursiva da 53 bytes (creo que en los recursivos tenemos que incluir la asignación? Si no, 51) TIO
CriminallyVulgar
1
@CriminallyVulgar podemos llegar a 49 bytes :-)
Giuseppe
@Giuseppe Jaja ¡Sabía que era golfable, simplemente no podía verlo! Me metí con cumsumun tiempo para tratar de hacerlo funcionar, pero eso Reducees muy hábil. Es bueno poder bajar el índice por 1 también, no lo vi en los comentarios.
CriminallyVulgar
1

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

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

Pruébalo en línea!

Arnauld
fuente
1

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
Jonás
fuente
1

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.

histocrat
fuente
tio.run/#ruby pls
Solo ASCII
también 49
solo ASCII
46
Solo ASCII
1

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!

Neil
fuente
1

Ó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

don brillante
fuente
1
Hay una mejor manera de calcular los coeficientes binomiales para el mismo costo pero que permite eliminar el 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)
Peter Taylor
1
De hecho, el binomio puede estar en línea: 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). Lo que sería bueno es combinar los dos pliegues, pero no estoy seguro de cuán sucintas son las tuplas.
Peter Taylor
1
Lo suficientemente sucinto: 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)
Peter Taylor
eso es increíble ... me cuesta incluso entender cómo funciona, pero es increíble.
Don brillante
Solo usa un truco algebraico:
norte!k!(norte-k)!=norte!(k-1)!(norte-(k-1))!×norte-k+1k
Peter Taylor
1

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.

Peter Taylor
fuente
1

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

Galen Ivanov
fuente
1
hazlo 1 indexado y guarda un byte: 1+!20->20#1
ngn
@ngn Gracias, como siempre hay algo que me he perdido :)
Galen Ivanov
0

Perl 5, 48 bytes

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

TIO

Nahuel Fouilleul
fuente
0

Japt , 15 bytes

0 indexado; reemplazar hcon p1 indexado.

ÈîXi1 å+}gNh20õ

Intentalo

Shaggy
fuente
0

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
Peter Taylor
fuente