Buat saya metasequence

25

Latar Belakang

Untuk tantangan ini, 'metasequence' akan didefinisikan sebagai urutan angka di mana tidak hanya angka itu sendiri akan meningkat, tetapi juga kenaikan, dan kenaikan akan meningkat dengan nilai yang meningkat, dll.

Misalnya, metasequence tingkat 3 akan dimulai sebagai:

1 2 4 8 15 26 42 64 93 130 176

karena:

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

Tantangan

Dengan bilangan bulat positif, hasilkan dua puluh item pertama dari metasequence dari tier itu.

Uji kasus

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

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

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

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

Seperti yang Anda menyadari, pertama t+1 item dari setiap urutan tingkat t adalah yang pertama t+1 kekuatan dari 2 ...

Aturan

  • Celah standar berlaku
  • Ini adalah , jadi jawaban tersingkat dalam byte menang
Geza Kerecsenyi
sumber
2
Saya menganggap Anda maksud 20 istilah, bukan angka?
Quintec
4
Omong-omong, tingkat tiga metasequence adalah OEIS A000125
Perwujudan Ketidaktahuan
6
Anda mungkin ingin mengklarifikasi jika solusi harus bekerja untuk input 20 atau lebih besar.
FryAmTheEggman
4
Bisakah kita memilih untuk mengindeks 0 (jadi, tingkat output 1 untuk input 0, tingkat 2 untuk input 1, dll.)?
Lynn
1
@ MilkyWay90, tidak terlalu jelas apa yang Anda maksud: 219 (dari level 5) hanya terjadi pada segitiga Pascal sebagai dan ( 219(2191) . (219218)
Peter Taylor

Jawaban:

8

Jelly , 8 7 byte

20ḶcþŻS

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

Ini menggunakan @ wawasan alephalpha yang

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

Lynn
sumber
Itu adalah bantuan brutal. Menakjubkan.
don cerah
22

Bahasa Wolfram (Mathematica) , 34 byte

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

Cobalah online!

Metasequence tingkat n adalah jumlah dari elemen n+1 pertama dari setiap baris segitiga Pascal.

alephalpha
sumber
1
Ada hampir built-in untuk itu , tapi sayangnya itu lebih lama.
Peter Taylor
1
Saya tidak cukup tahu WL untuk melakukan sesuatu yang berguna di dalamnya, tetapi bagi saya sepertinya itu akan mendapat manfaat dari identitas
T(n,k)={1if k=02T(n,k1)(k1n)otherwise
Peter Taylor
17

Haskell , 34 byte

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

Menggunakan input yang diindeks 0 ( f 4tingkat pengembalian 5.)

Haskell , 36 byte

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

Cobalah online! Menggunakan input yang diindeks 1 ( f 5tingkat pengembalian 5.)

Penjelasan

scanl (+) 1adalah fungsi yang mengambil jumlah parsial dari daftar, mulai dari (dan prepending) 1.

Sebagai contoh: scanl (+) 1 [20,300,4000]sama dengan [1,21,321,4321].

Ternyata tingkat n hanya fungsi ini diterapkan (n1) kali ke daftar [1,2,3,] .

(Atau yang setara: n kali ke daftar semua yang ada.)

Kami menggunakan salah satu initatau [1..20-n]untuk memperhitungkan daftar yang semakin lama setiap 1 aplikasi.

Lynn
sumber
1
[1..20-n]tidak akan bekerja untuk n>20
Peter Taylor
take 20.(iterate(scanl(+)1)[1..]!!)hanya akan memerlukan biaya satu byte lebih untuk memperbaikinya
H.PWiz
1
Jawaban pointfree Anda dapat kembali ke 34 byte menggunakan jawaban Anda lainnya: (iterate(init.scanl(+)1)[1..20]!!).
xnor
7

Brain-Flak , 84 82 byte

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

Cobalah online!

Beranotasi

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

Cobalah online!

Wisaya Gandum
sumber
3
Anda tahu lucu bagaimana ini lebih pendek dari Rust
don bright
7

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

Nick Kennedy
sumber
you might be able to use Map instead of outer?
JDL
@JDL I can’t see how that would work. I need every possible combination, not just pairs of combinations.
Nick Kennedy
5

Python 2, 69 58 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 nth term (0-indexed) of the sequence at tier t. A little analysis leads to the following recurrence formula:

a(t,n)=1+i=0n1a(t1,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)
DLosc
sumber
61 bytes as a recursive lambda function (Significantly more inefficient).
ovs
@ovs Thanks! I found a couple more bytes by using a different base case, too.
DLosc
1
(t>=0)*range(20) saves a byte, though there's probably a yet shorter expression.
xnor
1
if~t saves two more over @xnor
Jo King
4

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
dzaima
sumber
-1 byte using dzaima/APL: 1∘,1,
Adám
@Adám oh duh.. right
dzaima
Full program at 17: (≢↑(+\1∘,)⍣⎕)20⍴1
Adám
14 bytes by using the REPL (add the -s flag).
Erik the Outgolfer
If you use the flag, language becomes -s btw (unless -s is repl flag?)
ASCII-only
3

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:

i=0nxi(1x)i+1=1(x1x)1+n12x

alephalpha
sumber
3

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
  @  # 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
sumber
29 bytes (the $^a instead of $_ is necessary)
Jo King
1
@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.
nwellnhof
3

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

Try it online!


Explanation

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

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.

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

Quite resource-intensive--the online version can't calculate the 13th metasequence.

Try it online

CG One Handed
sumber
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)

Try it online!

It is trivial to write down following recursive formula based on the description in question

g(t,i)={g(t,i1)+g(t1,i1)ifit>01ifit=0
And you just need to generate an Array of 20 elements with [g(t,0)g(t,19)]

tsh
sumber
2

05AB1E, 11 9 bytes

20LIF.¥>¨

0-indexed

Try it online or verify all test cases.

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, output the result-list implicitly)
Kevin Cruijssen
sumber
1
Nice use of !
Emigna
2

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!

Giuseppe
sumber
tio this is only 39 bytes (using binomial approach)
Nick Kennedy
@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
Giuseppe
1
Converting this approach to a recursive function gives 53 bytes (I think in recursives we need to include the assignment? If not, 51) TIO
CriminallyVulgar
1
@CriminallyVulgar we can get to 49 bytes :-)
Giuseppe
@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.
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)

Try it online!


JavaScript (ES6), 63 bytes

NB: this version works for n20.

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

Try it online!

Arnauld
sumber
1

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
Jonah
sumber
1

Ruby, 49 bytes

f=->n{n<1?[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.

histocrat
sumber
tio.run/#ruby pls
ASCII-only
also 49
ASCII-only
46
ASCII-only
1

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!

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

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

don bright
sumber
1
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)
Peter Taylor
1
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.
Peter Taylor
1
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)
Peter Taylor
thats amazing... i struggle to even understand how it works but its amazing.
don bright
It just uses one algebraic trick:
n!k!(nk)!=n!(k1)!(n(k1))!×nk+1k
Peter Taylor
1

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.

Peter Taylor
sumber
1

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

Galen Ivanov
sumber
1
make it 1-indexed and save a byte: 1+!20 -> 20#1
ngn
@ngn Thanks, as always there's something I've missed :)
Galen Ivanov
0

Perl 5, 48 bytes

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

TIO

Nahuel Fouilleul
sumber
0

Japt, 15 bytes

0-indexed; replace h with p for 1-indexed.

ÈîXi1 å+}gNh20õ

Try it

Shaggy
sumber
0

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