Mach mich zu einer Metasequenz

25

Hintergrund

Für diese Herausforderung wird eine "Metasequenz" als eine Folge von Zahlen definiert, bei der nicht nur die Zahlen selbst, sondern auch das Inkrement und das Inkrement um einen zunehmenden Wert usw. zunehmen.

Beispielsweise würde die Tier 3-Metasequenz wie folgt beginnen:

1 2 4 8 15 26 42 64 93 130 176

da:

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

Herausforderung

Bei einer positiven Ganzzahl werden die ersten zwanzig Elemente der Metasequenz dieser Ebene ausgegeben.

Testfälle

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

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

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

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

Wie Sie vielleicht erkennen, sind die ersten Elemente jeder Sequenz der Stufe die ersten Potenzen von 2 ...t+1tt+1

Regeln

  • Es gelten Standardlücken
  • Das ist , also gewinnt die kürzeste Antwort in Bytes
Geza Kerecsenyi
quelle
2
Ich nehme an, Sie meinen 20 Begriffe, keine Ziffern?
Quintec
4
Übrigens ist die Metasequenz der dritten
Verkörperung der Ignoranz,
6
Möglicherweise möchten Sie klären, ob Lösungen für Eingabe 20 oder höher funktionieren müssen.
FryAmTheEggman
4
Können wir 0-Index wählen (also Ausgabeebene 1 für Eingabe 0, Ebene 2 für Eingabe 1usw.)?
Lynn
1
@ MilkyWay90, es ist nicht ganz klar, was Sie meinen: 219 (ab Stufe 5) kommt nur in Pascals Dreieck als und . (2191)(219218)
Peter Taylor

Antworten:

8

Gelee , 8 7 Bytes

20ḶcþŻS

Probieren Sie es 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, …]

Dies verwendet @ alephalphas Einsicht, dass

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

Lynn
quelle
Das ist brutal knapp. Einfach super.
Don Bright
22

Wolfram Language (Mathematica) , 34 Byte

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

Probieren Sie es online!

Die Metasequenz der Stufe ist die Summe der ersten Elemente jeder Zeile des Pascal-Dreiecks.nn+1

Alephalpha
quelle
1
Es gibt fast eine eingebaute , aber leider ist es länger.
Peter Taylor
1
Ich kenne nicht genug WL, um irgendetwas Nützliches zu tun, aber es scheint mir, dass es von der Identität profitieren könnte.
T(n,k)={1ob k=02T(n,k-1)-(k-1n)Andernfalls
Peter Taylor
17

Haskell , 34 Bytes

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

Verwendet 0-indizierte Eingaben ( f 4gibt Tier 5 zurück)

Haskell , 36 Bytes

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

Probieren Sie es online! Verwendet 1-indizierte Eingaben ( f 5gibt Tier 5 zurück)

Erläuterung

scanl (+) 1ist eine Funktion, die Teilsummen einer Liste annimmt, beginnend mit (und voranstehend) 1.

Zum Beispiel: scanl (+) 1 [20,300,4000]gleich [1,21,321,4321].

Es stellt sich heraus, dass Tier n genau diese Funktion (n-1) Mal auf die Liste [1,2,3,] angewendet wird .

(Oder gleichbedeutend: n mal zu einer Liste aller.)

Wir verwenden entweder initoder, um [1..20-n]zu berücksichtigen, dass die Liste mit jeder Anwendung um 1 länger wird .

Lynn
quelle
1
[1..20-n]wird nicht für n>20
Peter Taylor
take 20.(iterate(scanl(+)1)[1..]!!)würde nur ein Byte mehr kosten, um das zu beheben
H.PWiz
1
Ihre pointfree Antwort kann auf 34 Bytes wieder mit Ihrer anderen Antwort (iterate(init.scanl(+)1)[1..20]!!).
6.
7

Brain-Flak , 84 82 Bytes

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

Probieren Sie es online!

Kommentiert

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

Probieren Sie es online!

Weizen-Assistent
quelle
3
Sie wissen, es ist lustig, wie das kürzer ist als Rust
don bright
7

R , 36 Bytes

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

Probieren Sie es online!

Vielen Dank an @ Giuseppe für den Vorschlag outer.

Dies basiert auf dem beschriebenen Ansatz @alephalpha

Nick Kennedy
quelle
Sie könnten in der Lage sein, Mapanstelle von äußeren zu verwenden?
JDL
@JDL Ich kann nicht sehen, wie das funktionieren würde. Ich brauche jede mögliche Kombination, nicht nur Paare von Kombinationen.
Nick Kennedy
5

Python 2 , 69 58 55 Bytes

Gespeicherte Bytes dank Ovs und Jo King ; Außerdem funktioniert es jetzt auch in Python 3.

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

Probieren Sie es online!

Die Mathematik

Lassen ein(t,n) die A nth Laufzeit (0-indexiert) die Sequenz auf Stufe t . Eine kleine Analyse führt zu folgender Rekursionsformel:

ein(t,n)=1+ich=0n-1ein(t-1,ich)

Wir arbeiten rückwärts und definieren ein(0,n)=1 und ein(-1,n)=0 für alle n . Diese Definitionen vereinfachen unseren Basisfall.

Der Code

Wir definieren eine Funktion m(t), die die ersten 20 Elemente der Sequenz auf der Ebene zurückgibt t. Wenn dies nicht tnegativ ist, verwenden wir die obige rekursive Formel. Wenn tja -1, geben wir eine leere Liste zurück. Die leere Liste fungiert als Basisfall, da das Ergebnis jedes rekursiven Aufrufs aufgeteilt ( [:n]) und dann summiert wird. Das Schneiden einer leeren Liste ergibt eine leere Liste und das Summieren einer leeren Liste ergibt 0. Das ist genau das Ergebnis , das wir, da Tier wollen -1 wie eine konstante Folge aller verhalten sollte 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
quelle
61 Bytes als rekursive Lambda-Funktion (deutlich ineffizienter).
ovs
@ovs Danke! Ich habe ein paar Bytes mehr gefunden, indem ich auch einen anderen Basisfall verwendet habe.
DLosc
1
(t>=0)*range(20)Speichert ein Byte, obwohl es wahrscheinlich einen noch kürzeren Ausdruck gibt.
6.
1
if~tspart zwei weitere über @xnor
Jo King
4

dzaima / APL REPL, 14 Bytes

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

Probieren Sie es 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
dzaima
quelle
-1 Byte mit dzaima / APL: 1∘,1,
Adám
@ Adám oh duh .. richtig
dzaima
Volles Programm um 17 (≢↑(+\1∘,)⍣⎕)20⍴1
Uhr
14 Bytes mit der REPL (Füge das -sFlag hinzu).
Erik der Outgolfer
Wenn Sie die Flagge verwenden, wird die Sprache -sübrigens (außer -sRepl-Flagge?)
Nur ASCII
3

Pari / GP , 39 Bytes

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

Probieren Sie es online!


Pari / GP , 40 Bytes

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

Probieren Sie es online!


n

ich=0nxich(1-x)ich+1=1-(x1-x)1+n1-2x

Alephalpha
quelle
3

Perl 6 , 34 32 Bytes

-2 Bytes dank Jo King

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

Probieren Sie es online!

Erläuterung

{                              }  # 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
quelle
29 Bytes ( $^aanstelle von $_ist erforderlich)
Jo King
1
@JoKing Schön, aber das setzt voraus, dass $_beim Aufruf der Funktion undefiniert ist. Ich bevorzuge Lösungen, die nicht vom Zustand globaler Variablen abhängen.
Nwellnhof
3

Python 3.8 (Vorabversion) , 62 Byte

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

Probieren Sie es online!


Erläuterung

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

R ( 63 47 Bytes)

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

Online-Demo . Hierbei wird die regulierte unvollständige Betafunktion verwendet , die die kumulative Verteilungsfunktion eines Binomials ergibt und daher nur ein wenig Skalierung benötigt, um Teilsummen von Reihen des Pascalschen Dreiecks zu ergeben.

Oktave ( 66 46 Bytes)

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

Online-Demo . Genau das gleiche Konzept, aber etwas hässlicher, da betaincim Gegensatz zu pbetaRs das zweite und dritte Argument größer als Null sein müssen.

Vielen Dank an Giuseppe, der mir geholfen hat, diese mit erheblichen Einsparungen zu vektorisieren.

Peter Taylor
quelle
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}

Ungolfed-Version:

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

Sehr ressourcenintensiv - die Online-Version kann die 13. Metasequenz nicht berechnen.

Probieren Sie es online aus

CG Einhand
quelle
2

JavaScript (Node.js) , 58 Byte

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

Probieren Sie es online!

G(t,ich)={G(t,ich-1)+G(t-1,ich-1)obicht>01obicht=0
[G(t,0)G(t,19)]

tsh
quelle
2

05AB1E , 11 9 Bytes

20LIF.¥>¨

0-indiziert

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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
quelle
1
Gute Verwendung von !
Emigna
2

R , 59 49 Bytes

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

Probieren Sie es online!

Recursively Reducemit +, init=1und accumulation=TRUEzu vermeiden Teilmengen mit. Vielen Dank an Criminally Vulgar für den Hinweis auf den rekursiven Ansatz!

Giuseppe
quelle
tio dies ist nur 39 Bytes (binomische Ansatz)
Nick Kennedy
@ NickKennedy, das ist ein separater Ansatz, daher würde ich empfehlen, es selbst zu posten, und es ist golfer zu verwenden outerals sapplyfür 36 Bytes
Giuseppe
1
Wenn Sie diesen Ansatz in eine rekursive Funktion umwandeln, erhalten Sie 53 Bytes (Ich denke, in rekursiven müssen wir die Zuweisung einschließen? Wenn nicht, 51) TIO
CriminallyVulgar
1
@ CriminallyVulgar können wir 49 Bytes bekommen :-)
Giuseppe
@ Giuseppe Haha Ich wusste, dass es golffähig war, konnte es einfach nicht sehen! Ich habe cumsumeine Weile damit rumgespielt, um es zum Laufen zu bringen, aber das Reduceist so schlau. Schön, den Index auch um 1 senken zu können, habe ich in den Kommentaren nicht gesehen.
CriminallyVulgar
1

JavaScript (ES6),  68 bis  67 Byte

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

Probieren Sie es online!


JavaScript (ES6), 63 Byte

n20

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

Probieren Sie es online!

Arnauld
quelle
1

J , 24 Bytes

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

Probieren Sie es online!

HINWEIS: Es hat sich herausgestellt, dass dies eine Übersetzung der APL-Antwort von dzaima ist, obwohl ich es tatsächlich nicht bemerkt habe, bevor ich dies geschrieben habe.

Erläuterung

<: (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
Jona
quelle
1

Ruby, 49 Bytes

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

Rekursive Definition: Tier 0 ist 1,1,1,1...und jedes nachfolgende Tier ist 1, gefolgt von einer Sequenz, deren erste Unterschiede das vorherige Tier sind. Ärgerlicherweise würde dies mir 21 Werte geben, wenn ich die ersten 20 nicht explizit herausschneide; Anscheinend sollte es einen Weg geben, dies zu verkürzen, indem man dies vermeidet.

Histokrat
quelle
tio.run/#ruby pls
ASCII
auch 49
ASCII
46
Nur ASCII
1

Netzhaut , 59 Bytes

.+
19*$(_,

Ersetzen Sie den Eingang durch 19 1s (in unary). (Der 20. Wert ist 0, da er beim ersten Durchlauf der Schleife immer gelöscht wird.)

"$+"{`
)`

Wiederholen Sie die Schleife so oft wie ursprünglich eingegeben.

(.+),_*
_,$1

Entfernen Sie das letzte Element und stellen Sie a voran 1.

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

Berechnen Sie die kumulative Summe.

_+
$.&

In Dezimalzahl konvertieren.

Probieren Sie es online!

Neil
quelle
1

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

@alephalphas Idee verwendet, wie einige andere. Es gibt keine eingebauten Fakultäten, die mindestens 36 Bytes belegen (plus Umgang mit Negativen). Keine eingebaute Auswahl, weitere 16 Bytes. Iterator-> deklarierter Vektortyp, 20 Bytes .. etc etc.

Ungolfed auf play.rust-lang.org

Don Bright
quelle
1
Es gibt eine bessere Möglichkeit, Binomialkoeffizienten für dieselben Kosten zu berechnen, die jedoch das Entfernen der minfolgenden 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()}
Peter Taylor
1
Tatsächlich kann das Binomial inline geschrieben werden: 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). Was wäre schön, ist die Kombination der beiden Falten, aber ich bin nicht sicher, wie prägnante Tupel sind.
Peter Taylor
1
Prägnant genug: 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
Das ist erstaunlich ... Ich habe Mühe zu verstehen, wie es funktioniert, aber es ist erstaunlich.
Don Bright
n!k!(n-k)!=n!(k-1)!(n-(k-1))!×n-k+1k
1

R ( 60 59 Bytes)

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

Online-Demo

Einfache Umsetzung der Beobachtung

T (n, k) = 2 T (n - 1, k) - Binomial (n - 1, k). - MF Hasler, 30. Mai 2010

von OEIS A008949 . Die Argumente dafür Reducesind (offensichtlich) die Funktion, das abzubildende Array, der Startwert, ein falscher Wert (von links anstatt von rechts zu falten) und ein wahrer Wert zum Akkumulieren der Zwischenergebnisse in einem Array.

Peter Taylor
quelle
1

K (oK) , 17 Bytes

-1 Byte dank ngn (Umschalten von 0-indiziert auf 1-indiziert)

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

Probieren Sie es online!

1-indiziert

K (oK) , 18 Bytes

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

Probieren Sie es online!

0-indiziert

Galen Ivanov
quelle
1
mach es 1-indiziert und speichere ein Byte: 1+!20->20#1
ngn
@ngn Danke, wie immer habe ich etwas verpasst :)
Galen Ivanov
0

Perl 5, 48 Bytes

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

TIO

Nahuel Fouilleul
quelle
0

Japt , 15 Bytes

0-indiziert; Ersetzen Sie hmit pfür 1-indiziert.

ÈîXi1 å+}gNh20õ

Versuch es

Zottelig
quelle
0

CJam (20 Bytes)

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

Online-Demo . Dies ist ein Programm, das Eingaben von stdin nimmt und nach stdout druckt. für die gleiche Punktzahl kann ein anonymer Block (Funktion) erhalten werden als

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

Präparation

Dies gilt wörtlich für die Definition:

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
quelle