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: 3
Keluaran:[ 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160 ]
Input: 1
Keluaran:[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]
Input: 5
Keluaran:[ 1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664 ]
Input: 13
Keluaran:[ 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 item dari setiap urutan tingkat adalah yang pertama kekuatan dari 2 ...
Aturan
- Celah standar berlaku
- Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang
sumber
0
, tingkat 2 untuk input1
, dll.)?Jawaban:
Jelly ,
87 byteCobalah online!
Ini menggunakan @ wawasan alephalpha yangmeta-sequencen(i)=∑k=0n(ik).
sumber
Bahasa Wolfram (Mathematica) , 34 byte
Cobalah online!
Metasequence tingkatn adalah jumlah dari elemen n+1 pertama dari setiap baris segitiga Pascal.
sumber
Haskell , 34 byte
Menggunakan input yang diindeks 0 (
f 4
tingkat pengembalian 5.)Haskell , 36 byte
Cobalah online! Menggunakan input yang diindeks 1 (
f 5
tingkat pengembalian 5.)Penjelasan
scanl (+) 1
adalah fungsi yang mengambil jumlah parsial dari daftar, mulai dari (dan prepending)1
.Ternyata tingkatn hanya fungsi ini diterapkan (n−1) kali ke daftar [1,2,3,…] .
(Atau yang setara:n kali ke daftar semua yang ada.)
Kami menggunakan salah satu1 aplikasi.
init
atau[1..20-n]
untuk memperhitungkan daftar yang semakin lama setiapsumber
[1..20-n]
tidak akan bekerja untuktake 20.(iterate(scanl(+)1)[1..]!!)
hanya akan memerlukan biaya satu byte lebih untuk memperbaikinya(iterate(init.scanl(+)1)[1..20]!!)
.Brain-Flak ,
8482 byteCobalah online!
Beranotasi
Cobalah online!
sumber
R, 36 bytes
Try it online!
Thanks to @Giuseppe for suggesting
outer
.This is based on the approach @alephalpha described
sumber
Map
instead of outer?Python 2,
695855 bytesSaved bytes thanks to ovs and Jo King; also, it works in Python 3 now as well.
Try it online!
The math
Leta(t,n) be the nth term (0-indexed) of the sequence at tier t . A little analysis leads to the following recurrence formula:
Working backwards, we definea(0,n)=1 and a(−1,n)=0 for all n . These definitions will simplify our base case.
The code
We define a function−1 should behave like a constant sequence of all 0 's.
m(t)
that returns the first 20 elements of the sequence at tiert
. Ift
is nonnegative, we use the recursive formula above; ift
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 gives0
. That's exactly the result we want, since tiersumber
(t>=0)*range(20)
saves a byte, though there's probably a yet shorter expression.if~t
saves two more over @xnordzaima/APL REPL, 14 bytes
Try it online!
sumber
1∘,
→1,
(≢↑(+\1∘,)⍣⎕)20⍴1
-s
flag).-s
btw (unless-s
is repl flag?)Pari/GP, 39 bytes
Try it online!
Pari/GP, 40 bytes
Try it online!
The generating function of the tiern metasequence is:
sumber
Perl 6,
3432 bytes-2 bytes thanks to Jo King
Try it online!
Explanation
sumber
$^a
instead of$_
is necessary)$_
is undefined when calling the function. I prefer solutions that don't depend on the state of global variables.Python 3.8 (pre-release), 62 bytes
Try it online!
Explanation
sumber
R (
6347 bytes)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 (
6646 bytes)Online demo. Exactly the same concept, but slightly uglier because
betainc
, unlike R'spbeta
, requires the second and third arguments to be greater than zero.Many thanks to Giuseppe for helping me to vectorise these, with significant savings.
sumber
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:
Quite resource-intensive--the online version can't calculate the 13th metasequence.
Try it online
sumber
Wolfram Language (Mathematica), 42 bytes
Try it online!
sumber
JavaScript (Node.js), 58 bytes
Try it online!
It is trivial to write down following recursive formula based on the description in questiong(t,i)={g(t,i−1)+g(t−1,i−1)1ifi⋅t>0ifi⋅t=0
And you just need to generate an Array of 20 elements with [g(t,0)…g(t,19)]
sumber
05AB1E,
119 bytes0-indexed
Try it online or verify all test cases.
Explanation:
sumber
.¥
!R,
5949 bytesTry it online!
Recursively
Reduce
with+
,init=1
andaccumulation=TRUE
to avoid having to subset. Thanks to Criminally Vulgar for suggesting the recursive approach!sumber
outer
thansapply
for 36 bytescumsum
for a while to try and make it work, but thatReduce
is so slick. Nice to be able to drop the index by 1 as well, didn't see that in the comments.JavaScript (ES6),
6867 bytesTry it online!
JavaScript (ES6), 63 bytes
NB: this version works forn≤20 .
Try it online!
sumber
J, 24 bytes
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
sumber
Ruby, 49 bytes
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.sumber
Retina, 59 bytes
Replace the input with 19
1
s (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.
Remove the last element and prefix a
1
.Calculate the cumulative sum.
Convert to decimal.
Try it online!
sumber
C# (Visual C# Interactive Compiler), 120 bytes
Try it online!
Based off of alephalpha's formula.
sumber
Rust, 135 bytes
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
sumber
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)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.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)R (
6059 bytes)Online demo
Straightforward implementation of the observation
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.sumber
K (oK), 17 bytes
-1 byte thanks to ngn (switching from 0-indexed to 1-indexed)
Try it online!
1-indexed
K (oK), 18 bytes
Try it online!
0-indexed
sumber
1+!20
->20#1
Jelly, 10 bytes
Try it online!
0-indexed.
sumber
Perl 5, 48 bytes
TIO
sumber
Japt, 15 bytes
0-indexed; replace
h
withp
for 1-indexed.Try it
sumber
CJam (20 bytes)
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
Dissection
This applies the definition literally:
sumber