Contexte

Pour ce défi, une `` métaséquence '' sera définie comme une séquence de nombres où non seulement les nombres eux-mêmes augmenteront, mais aussi l'incrément, et l'incrément augmentera d'une valeur croissante, etc.

Par exemple, la métaséquence de niveau 3 commencerait comme:

1 2 4 8 15 26 42 64 93 130 176

car:

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

Défi

Étant donné un entier positif, affichez les vingt premiers éléments de la métaséquence de ce niveau.

Cas de test

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

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

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

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

Comme vous pouvez vous en rendre compte, les premiers $t+1$ éléments de chaque séquence de niveau $t$ sont les premiers pouvoirs de 2 ...$t+1$

Règles

• Des échappatoires standard s'appliquent
• Il s'agit de code-golf , donc la réponse la plus courte en octets l'emporte

Gelée , 8 7 octets

20ḶcþŻS

Essayez-le en ligne!

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

Cela utilise la perspicacité de @ alephalpha que la

Wolfram Language (Mathematica) , 34 octets

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

Essayez-le en ligne!

La métaséquence de niveau $n$ est la somme des $n+1$ premiers éléments de chaque ligne du triangle Pascal.

Haskell , 34 octets

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

Utilise des entrées indexées 0 ( f 4renvoie le niveau 5.)

Haskell , 36 octets

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

Essayez-le en ligne! Utilise des entrées indexées 1 ( f 5renvoie le niveau 5.)

Explication

scanl (+) 1est une fonction qui prend des sommes partielles d'une liste, en commençant par (et en ajoutant) 1.

Par exemple: scanl (+) 1 [20,300,4000]égal [1,21,321,4321].

Il s'avère que le niveau $n$ est juste cette fonction appliquée $(n-1)$ fois à la liste $[1,2,3,\dots]$ .

(Ou de manière équivalente: $n$ fois à une liste de tous.)

Nous utilisons soit initou [1..20-n]pour tenir compte de l'allongement de la liste en$1$ chaque application.

Brain-Flak , 84 82 octets

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

Essayez-le en ligne!

Annoté

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

Essayez-le en ligne!

R , 36 octets

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

Essayez-le en ligne!

Merci à @Giuseppe d'avoir suggéré outer.

Ceci est basé sur l' approche @alephalpha décrite

Python 2 , 69 58 55 octets

Octets enregistrés grâce aux ovs et à Jo King ; aussi, cela fonctionne aussi dans Python 3 maintenant.

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

Essayez-le en ligne!

Les maths

Soit $a(t,n)$ le terme $n^{th}$ (indexé 0) de la séquence au niveau $t$ . Une petite analyse conduit à la formule de récurrence suivante:

En travaillant en arrière, nous définissons $a(0,n) = 1$ et $a(-1,n) = 0$ pour tout $n$ . Ces définitions simplifieront notre scénario de base.

Le code

Nous définissons une fonction m(t)qui renvoie les 20 premiers éléments de la séquence au niveau t. Si test non négatif, nous utilisons la formule récursive ci-dessus; si tc'est le cas -1, nous renvoyons une liste vide. La liste vide fonctionne comme un cas de base car le résultat de chaque appel récursif est découpé ( [:n]) puis additionné. Découper une liste vide donne une liste vide et additionner une liste vide donne 0. C'est exactement le résultat que nous voulons, car niveau $-1$ devrait se comporter comme une séquence constante de tous les $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 octets

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

Essayez-le en ligne!

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

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

Essayez-le en ligne!

Pari / GP , 40 octets

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

Essayez-le en ligne!

$n$

Perl 6 , 34 32 octets

-2 octets grâce à Jo King

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

Essayez-le en ligne!

Explication

{                              }  # 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 (pré-version) , 62 octets

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

Essayez-le en ligne!

Explication

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

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

Démo en ligne . Cela utilise la fonction bêta incomplète régularisée , qui donne la fonction de distribution cumulative d'un binôme, et a donc juste besoin d'un peu de mise à l'échelle pour donner des sommes partielles de lignes du triangle de Pascal.

Octave ( 66 46 octets)

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

Démo en ligne . Exactement le même concept, mais un peu plus laid parce que betainc, contrairement aux Rpbeta , les deuxième et troisième arguments doivent être supérieurs à zéro.

Un grand merci à Giuseppe de m'avoir aidé à les vectoriser, avec des économies importantes.

Rubis, 74 octets

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}

Version non golfée:

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

Beaucoup de ressources - la version en ligne ne peut pas calculer la 13e métaséquence.

Essayez-le en ligne

Wolfram Language (Mathematica) , 42 octets

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

Essayez-le en ligne!

JavaScript (Node.js) , 58 octets

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

Essayez-le en ligne!

05AB1E , 11 9 octets

20LIF.¥>¨

0 indexé

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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 octets

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

Essayez-le en ligne!

Récursivement Reduceavec +, init=1et accumulation=TRUEpour éviter d'avoir à sous-ensemble. Merci à Criminally Vulgar d' avoir suggéré l'approche récursive!

JavaScript (ES6),  68  67 octets

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

Essayez-le en ligne!

JavaScript (ES6), 63 octets

NB: cette version fonctionne pour $n\le20$.

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

Essayez-le en ligne!

J , 24 octets

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

Essayez-le en ligne!

REMARQUE: Il s'avère que c'est une traduction de la réponse APL de dzaima, bien que je ne l'ai pas remarqué avant d'écrire ceci.

explication

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

Rubis, 49 octets

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

Définition récursive: le niveau 0 est 1,1,1,1...et chaque niveau suivant est 1 suivi d'une séquence dont les premières différences sont le niveau précédent. De façon ennuyeuse, cela me donnerait 21 valeurs si je ne découpais pas explicitement les 20 premiers; semble qu'il devrait y avoir un moyen de raccourcir cela en évitant cela.

Rétine , 59 octets

.+
19*$(_,

Remplacez l'entrée par 19 1 s (en unaire). (La 20e valeur est 0 car elle est toujours supprimée lors du premier passage dans la boucle.)

"$+"{`
)`

Répétez la boucle le nombre d'entrées d'origine.

(.+),_*
_,$1

Supprimer le dernier élément et préfixer un 1 .

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

Calculez la somme cumulée.

_+
$.&

Convertissez en décimal.

Essayez-le en ligne!

C # (Visual C # Interactive Compiler) , 120 octets

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

Essayez-le en ligne!

Basé sur la formule d'alephalpha.

Rouille , 135 octets

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()}

a utilisé l'idée de @alephalpha, comme plusieurs autres. il n'y a pas de factoriel intégré, ce qui prend au moins 36 octets (plus le traitement des négatifs). aucun choix intégré, 16 autres octets. itérateur-> type de vecteur déclaré, 20 octets .. etc etc.

Non golfé sur play.rust-lang.org

R ( 60 59 octets)

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

Démo en ligne

Mise en œuvre simple de l'observation

T (n, k) = 2 T (n-1, k) - binôme (n-1, k). - MF Hasler, 30 mai 2010

à partir de OEIS A008949 . Les arguments pour Reducesont la fonction (évidemment), le tableau sur lequel mapper, la valeur de départ, une valeur fausse (à replier de gauche plutôt que de droite), et une valeur vraie pour accumuler les résultats intermédiaires dans un tableau.

K (oK) , 17 octets

-1 octet grâce à ngn (passage de l'index 0 à l'index 1)

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

Essayez-le en ligne!

1 indexé

K (oK) , 18 octets

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

Essayez-le en ligne!

0 indexé

Gelée , 10 octets

20RṖ1;ÄƲ⁸¡

Essayez-le en ligne!

0 indexé.

Perl 5, 48 octets

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

TIO

Japt , 15 octets

Indexé 0; remplacer hpar ppour 1 indexé.

ÈîXi1 å+}gNh20õ

Essayez-le

CJam (20 octets)

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

Démo en ligne . C'est un programme qui prend l'entrée de stdin et imprime sur stdout; pour le même score, un bloc (fonction) anonyme peut être obtenu

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

Dissection

Cela applique la définition littéralement:

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