Linear integer function generator

Inspired by a recent challenge involving Fibonacci numbers in which OEIS was mentioned, I would like to present a challenge of creating a function that generates a wide array of different linear integer sequences, depending on user input.

Specifically, the user should provide three inputs:

2. the starting value of every 'seed' needed for the sequence, and
3. the number of integers to generate and display.

For example, the Fibonacci sequence has two members in the kernel and needs two starting seeds (0, 1). Then $$\F(n) = F(n-1) + F(n-2)\$$.

The Padovan sequence has three members in its kernel and needs three seeds, (1,0,0). Then $$\F(n) = F(n-2) + F(n-3)\$$.

I am not going to mandate the format of the 'kernel' input, though the natural form would be, I think, a list of the same length of the list of seeds, composed of integers corresponding to the weight to give to each of integers in the previous row.

This means that the kernel of the Fibonacci sequence, which adds together the previous two numbers, can be represented as (1,1). By contrast, the kernel of the Padovan sequence, which ignores the first member of the previous row and adds the second and third terms, can be represented as (0,1,1).

Your code should be able to handle an arbitrary number of seeds and lists of arbitrary length. For each sequence, the number of members of the kernel and the length of the seed list should be the same positive integer. For the sake of this challenge, assume all members of the kernel and all seed values are integers (though I suspect that most of the responses to this challenge will work for all real numbers). Similarly assume the required sequence length will be a positive integer.

My examples below use (parentheses) to encapsulate lists, but use whatever notation is most natural to your programming language.

Examples!

For the Fibonacci sequence, your function should take three inputs like

(1, 1), (0, 1), 10


(that's kernel, seed, and sequence length), and generate

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)


For the Padovan sequence, input like

(0, 1, 1), (1, 0, 0), 20


should generate

(1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37)


The Perrin Sequence takes input like

(0, 1, 1), (3, 0, 2), 10


to produce

(3, 0, 2, 3, 2, 5, 5, 7, 10, 12)


For edge cases,

(1, 1), (0, 0), 5


should produce

(0,0,0,0,0)


and

(-1, 0, 1, 0), (0, -1, 0, 1), 20


should produce

(0, -1, 0, 1, -2, 2, -1, -1, 3, -4, 3, 0, -4, 7, -7, 3, 4, -11, 14, -10).


I suspect there are going to be some extremely concise responses to this.

• Can we take the kernel as a function?
Jan 4, 2021 at 22:52
• Could the full range of typical sequence output be permitted, or are you committed to first-n only? Jan 4, 2021 at 23:12
• Will the required sequence length always be greater than (or equal to?) the seed length?
Jan 4, 2021 at 23:18
• @Adám, re: passing a function: if I had thought of that early on I would say yes, but given that we have a bunch of good responses already it doesn't seem fair to allow a technique that could significantly shorten things in some of the languages already on display. Sorry. And re: sequence length always greater than or equal to seed length. Yes, you can assume it will be. Jan 5, 2021 at 0:32
• @UnrelatedString first-n only Jan 5, 2021 at 0:33

Wolfram Language (Mathematica), 16 bytes

LinearRecurrence


Try it online!

Given the OP's background, I suppose this isn't too much of a surprise.

• I will confess, I was curious to see how much more concise some of these golfing languages would be than a Wolfram built-in. Jan 5, 2021 at 2:32
• @MichaelStern Yeah, it can be interesting to see. With some built-ins' verbosity sometimes the built-in isn't even the shortest way to do it in Mathematica.
– att
Jan 5, 2021 at 3:14

Kakoune, 62 keystrokes

<a-l>"ndd<a-l>S
"hddQxy<a-p><a-p>_S
a*<c-r>h+<a-;> <backspace><esc><a-h>|bc
k<a-i>ndd<a-j>Q:ex<tab> <c-r>nq
K<a-x>d%<a-s><a-h>w<a-l>d<a-j>


(note the trailing spaces on line 1 and 2)

Assumes the input in the following format, with the cursor at the start of the buffer:

number of items
kernel separated with spaces in reverse
seed separated by spaces


Gives the output as the numbers space separated.

Here is a video of the solution in action, with a few minor human errors :)

Factor, 38 bytes

[ [ 2dup v. prefix dup pop . ] times ]


Try it online!

Takes the inputs in the order of kernel seed(reversed) length, and prints out the desired sequence to STDOUT, one item per line. The seed must be of a sequence type that supports pop method, e.g. a vector.

[               ! ( kernel seed length -- kernel seed' )
[             ! inner quotation ( kernel seed -- kernel seed' )
2dup v.     !   evaluate next item using vector dot product
prefix      !   prepend to seed
dup pop .   !   remove the last item from seed and print
] times       ! run the above length times
]


Factor, 45 bytes

[ [ 2dup reverse v. suffix unclip . ] times ]


Try it online!

Taking the seed in the given order costs 8 bytes for reverse<space> which is needed for dot product, but 1 byte can be saved by replacing dup pop with unclip.

(flip take.).g
g(x:r)k=x:g(r++[sum(zipWith(*)k$x:r)])k  Try it online! The function g takes the seed and the kernel as input and builds the sequence as an infinite list. The first line is an anonymous function taking the seed, the kernel and the length as input, passing the former two arguments to g and truncating the infinite sequence to the given length. 05AB1E, 9 7 bytes Inputs are the seed, then the kernel and the number of integers last. Thanks to Kevin Cruijssen for -2 bytes! λ£³ā₆*O  The challenge reads like it's made for the recursive list generation builtin λ ;) λ£ takes the seed and the number as input and generates the first terms of the sequence starting with the values from the seed. ²ā₆*O is executed to generate each a(n): ² pushes the second input, the kernel. ā pushes the range [1,2,...,len(kernel)]. For each k in this range ₆ gets the previous value a(n-k) to get the new list [a(n-1), a(n-2), ..., a(n-len(kernel))]. * multiplies this element-wise with the kernel. O sums up all values to generate a(n). 05AB1E, 10 bytes First input is the number of integers, then the the seed and the kernel last. FDŠR*Oª}¹£  Try it online! 1 byte longer without λ. F } # iterate input times D # duplicate the current sequence (initially: seed) Š # triple swap -> stack: [sequence, kernel, sequence] R # reverse the current sequence * # multiply element-wise with the kernel O # take the sum ª # append the new value to the sequence ¹£ # take as many numbers as required  • The recursive approach can be 7 bytes by taking the inputs in the order: seed, number of integers, kernel (second and third are swapped): λ£³ā₆*O. The recursive environment has three different options: λ (the default, which is the infinite list); λ£ (first $n$ amount of values); λè (0-based $n^{th}$ value). Jan 7, 2021 at 15:05 • @KevinCruijssen thanks a lot, this is looking much better now ;). There seems to be a third option, λj, which checks if the first input is contained in the (increasing) sequence. It's not the shortest for checking if a number is a Fibonacci number, but I guess this will be useful for sequences that don't have builtins. – ovs Jan 8, 2021 at 7:38 • Oh, didn't knew about j as option. Thanks for letting me know. :) I hadn't looked in the source code for the recursive environment before. Jan 8, 2021 at 7:39 Python 3, 7267 64 bytes Takes as input $$\k\$$, $$\s\$$ and $$\n\$$, which are the kernel, seed, and number of integers to display, respectively. lambda k,s,n:s[exec("s+=sum(map(int.__mul__,s[::-1],k)),;"*n):n]  Try it online! Python 3, 72 bytes f=lambda k,s,n:len(s)//n*s or f(k,s+[sum(map(int.__mul__,s[::-1],k))],n)  Try it online! J, 28 bytes 0{"1(}.@],1#.]*1>@{[)^:(0{[)  Try it online! There are a lot of ugly mechanics in this solution, even though the underlying "power of" verb ^: solves the problem nicely. The issue is that we have only two arguments in J, and have to get 3 pieces of information into the verb, so have to make one of the arguments do double duty, and then waste a lot of bytes de-structuring. J902 has the F: conjunction which expresses recurrences naturally, but you have use the awkward and verbose "terminate fold" Z: to express "n iterations". The other approach I tried was to create the powers of the appropriate matrix (the recurrence as the top row, stacked on the identity matrix with the last row cut off), and multiply those by the seed. Also a nice solution, but requires enough mechanics that I couldn't get the byte count down. J, another approach, 29 bytes 0{"1(}.@],1#.*)/@|.\@(0}#&>/)  Try it online! APL (Dyalog Extended), 23 (SBCS) Full program. Prompts for seed (reversed of OP's), then required length, then kernel (OP's). ⎕(⌽⊣≢⍛↓(⊢,⍨⊣+.×≢⍛↑)⍣⎕)⎕  Try it online! ⎕()⎕ apply the following tacit function with kernel and seed as left and right arguments: ()⍣⎕ prompt for required length, and apply the following tacit function that many times: ≢⍛↑ take length-of-kernel elements from the (reversed) seed/list …+.× dot product with: ⊣ the kernel ,⍨ append: ⊢ the seed/list …≢⍛↓ drop as many elements as there are elements in: ⊣ the kernel ⌽ reverse Old solution using a function kernel: APL (Dyalog Unicode), 12 bytes (SBCS) Anonymous infix lambda, taking seed as right argument and required sequence length as left argument. Prompts for kernel as a prefix function that takes a list as argument and computes the next term. {⍺↑,∘⎕⍨⍣⍺⊢⍵}  Try it online! (with helper operator to make kernel input easy) {} "dfn"; left and right arguments are ⍺ and ⍵: ⊢⍵ on the seed …⍣⍺ apply the following function as many times as terms required: ,∘⍨ catenate self with result of applying the following function: ⎕ get kernel function from console ⍺↑ take as many terms as required ARM Thumb-2, strict ruleset, 34 bytes Machine code: 4563 d90d 4664 2700 000a 3c01 5705 f912 6b01 fb06 7705 d8f8 7017 3101 3b01 e7ef 4770  Overcommented assembly with C-callable wrapper (not part of score, just for testing with C)  // Now with C-style comments because no ARM syntax highlighting .syntax unified .arch armv6t2 .thumb // Params (note kernel_length is r12, not r2) // int8_t *kernel: kernel (test case order) ker_p .req r0 // int8_t *seed_out_ptr: seed/output array out_p .req r1 // uint32_t kernel_length: Kernel length in elements ker_len .req r12 // uint32_t seq_length: Sequence length in elements seq_len .req r3 // Local temps // Clobbers r4-r7. i .req r4 // Loop counter j .req r2 // seq_p copy for loop k_co .req r5 // Kernel coefficient f_i .req r6 // F(n - i) dot_p .req r7 // Dot product // Custom calling convention, hence the dot. See below for a C wrapper. .globl .linear_gen .type .linear_gen, %function .thumb_func .linear_gen: .Lmain_loop: // Loop while seq_len > ker_len cmp seq_len, ker_len bls .Lmain_loop.end // Loop backwards from kernel_length to 0. mov i, ker_len // Initialize dot product at 0 movs dot_p, #0 // Make a copy of the pointer movs j, out_p .Ldot_product_loop: // Decrement loop counter subs i, #1 // Load kernel coefficient ldrsb k_co, [ker_p, i] // Load F(n - i), incrementing the pointer as we go. (wide insn) ldrsb f_i, [j], #1 // dot_p += f_i * k_co (wide insn) mla dot_p, f_i, k_co, dot_p // loop while i is > 0 (mla doesn't affect flags) bhi .Ldot_product_loop .Ldot_product_loop.end: // Store the dot product into out_p[kernel_length]. // We can just reuse j because the loop will leave it at // this point. strb dot_p, [j] // Increment out_p adds out_p, #1 // Decrement seq_len subs seq_len, #1 // loop b .Lmain_loop .Lmain_loop.end: // return bx lr #ifdef C_WRAPPER // C wrapper .global linear_gen .type linear_gen, %function .thumb_func // void linear_gen(int8_t *kernel, int8_t *seed_out, uint32_t kernel_len, uint32_t sequence_len); linear_gen: // save callee saved registers push {r4-r7, lr} // fix parameters mov ker_len, r2 // call the function bl .linear_gen // restore registers and return pop {r4-r7, pc} #endif // C_WRAPPER  C signature (for wrapped version) void linear_gen(int8_t *kernel, int8_t *seed_out, uint32_t kernel_len, uint32_t sequence_len);  The arrays are int8_t * as it is the easiest type to work with due to how offsetting works, but the algorithm would work with any integer type. This version is VERY awkward from an implementation standpoint. Specifically, these are the issues: • The kernel is in the opposite order of the seed, requiring one pointer to index forwards and the other to index backwards. Thumb doesn't have negative register indexing. • This extra pointer pushes us to use a high register which is very restrictive in what you can do with narrow instructions. • The sequence length is always greater or equal to the kernel length. This requires the comparison to be before the loop. Now, let's bend the rules a tiny bit to make things significantly less awkward. • The kernel order is reversed from the test cases. • This simplifies indexing, saving 4 bytes. • We only need one counter, removing a movs • This also allows us to keep everything in low registers, meaning we can still index the strb, with ker_len instead of j. • We can use the narrow form of ldrb in the loop. • The sequence length is always greater than, never equal to the kernel length. • This means we can move the branch to the bottom, saving 2 bytes. • Don't know why this isn't the case...running zero times is a little silly, and none of the test cases show the length being equal to the sequence length. Under this altered ruleset, we save 6 bytes and can be a lot more orthodox in the parameters, storing them in the traditional r0, r1, r2, r3 instead of r0, r1, r12, r3. ARM Thumb-2, altered ruleset (non-competing?), 28 bytes Machine code: 1a9b 0014 2700 3c01 5705 570e fb06 7705 d8f9 548f 3101 3b01 d8f3 4770  Commented assembly (Differing lines marked with // <)  // Now with C-style comments because no ARM syntax highlighting .syntax unified .arch armv6t2 .thumb // Params // int8_t *kernel: kernel (reversed from test case order) ker_p .req r0 // int8_t *seed_out_ptr: seed/output array out_p .req r1 // uint32_t kernel_length: Kernel length in elements ker_len .req r2 // <- not r12 // uint32_t seq_length: Sequence length in elements (> kernel_length) seq_len .req r3 // Local temps // Clobbers r4-r7. i .req r4 // Loop counter k_co .req r5 // Kernel coefficient f_i .req r6 // F(n - i) dot_p .req r7 // Dot product // custom calling convention. See linear_gen for a C wrapper. .globl .linear_gen .type .linear_gen, %function .thumb_func .linear_gen: // Subtract kernel_length from sequence_length to get // the iteration count. subs seq_len, ker_len // <- since ker_len is a low reg now, we can subtract .Lmain_loop: // Loop while seq_len > ker_len // cmp seq_len, ker_len // <- we no longer need the branch at the top, // bls .Lmain_loop.end // <- because we know it is never equal // Loop backwards from kernel_length to 0. movs i, ker_len // Initialize dot product at 0 movs dot_p, #0 .Ldot_product_loop: // Decrement loop counter subs i, #1 // Load kernel coefficient ldrsb k_co, [ker_p, i] // Load F(n - i) ldrsb f_i, [out_p, i] // <- not wide insn, just register+register // dot_p += f_i * k_co (wide insn) mla dot_p, f_i, k_co, dot_p // loop while i is > 0 (mla doesn't affect flags) bhi .Ldot_product_loop .Ldot_product_loop.end: // Store the dot product into out_p[kernel_length] strb dot_p, [out_p, ker_len] // <- Instead of j, we can use ker_len. Same size. // Increment out_p adds out_p, #1 // Decrement seq_len subs seq_len, #1 // Loop while not zero bhi .Lmain_loop // <- Use flags from subs for loop .Lmain_loop.end: // return bx lr #if 1 // C wrapper .global linear_gen .type linear_gen, %function .thumb_func // void linear_gen(int8_t *kernel, int8_t *seed_out, uint32_t kernel_length, uint32_t sequence_length); linear_gen: // save callee saved registers push {r4-r7, lr} // fix parameters // mov ker_len, r2 // <- kernel_len is already r2 // call the function bl .linear_gen // restore registers and return pop {r4-r7, pc} #endif  Technically, we could go further and say that the sequence_length should not include kernel_length for another 2 bytes, but that is DEFINITELY pushing it. 😂 Haskell, 70 65 bytes f k s n=take n$foldl(\a t->a++[sum$zipWith(*)(drop t a)k])s[0..n]  Try it online! • saved 5 thanks to @Laikoni take n$     - return n elements
foldl(...)s - fold adding to seed
[0..n]      - index of first seed to use(had to add n because infinite list didn't worked)
(\a t->a++  - again, add to seed
[sum[x*y|(x,y) - sum of terms
zip(drop t a)k]- make pairs dropping t elements from list

• Save one more byte with zipWith(*)k$drop t a. Also, here is some friendly competition if you don't mind. Jan 6, 2021 at 2:50 • @Laikoni don't worry I instantly voted your great answer and I saw you swapped arguments but I was too lazy to do it too, Thanks for the help! Jan 6, 2021 at 10:22 Scala, 75 71 bytes -4 bytes thanks to user! k=>n=>1.to(n-k.size)./:(_)((x,_)=>x:+(x.reverse,k).zipped.map(_*_).sum)  Try it online! • I love the use of zipped's natural behavior to only keep k.size elements from x. You can get 71 bytes by using an underscore for s and then currying the function. – user Jan 6, 2021 at 15:38 • Here is a 64 byte version, but you'll have to index n differently – user Jan 6, 2021 at 15:42 • @user Thank you! I think your second solution is not valid here since n should be the number of integers to generate and display. Jan 6, 2021 at 19:48 Zsh, 87 81 bytes -6 bytes thanks to @pxeger. -6 bytes for a score of 75 bytes by taking the kernel in reverse. K=(${(Oa)=1})    # Use "K=($=1)" if kernel is reversed S=($=2)
repeat $3-$#S S+=$[printf +%s\*%s${S[-$#K,-1]:^K}] <<<$S


Takes the lists as space-delimited.

kern=(${(Oa)=1}) # = split on$IFS, (Oa) reverse order
seed=($=2) # = split on$IFS
repeat $3-$#seed;{                 # repeat's argument is interpreted arithmetically
tmp=(${seed[-$#kern,-1]:^kern} # zip the last len(kern) arguments of seed with $kern printf -v next +%s\*%s$tmp    # next='+s_(n-1)*k_1+s_(n-2)*k_2 ...'
seed+=$[next] # interpret$next arithmetically, append to $seed } <<<$seed                          # output seed array

• Jan 5, 2021 at 20:30
• 71 if this is allowed. Takes input not in reverse. Try it online! Jan 5, 2021 at 21:09
• Clever. Although, that would be Zsh+coreutils because of tac. For mine, I'll use <&0 and keep the kernel in reverse order. Same length. Jan 6, 2021 at 20:21

Jelly, 9 8 bytes

Ṛḋ⁵ṭƲ⁴¡ḣ


Try it online!

Takes three arguments in this order: seed, number of repetitions, kernel.

Explanation

Ṛḋ⁵ṭƲ⁴¡ḣ   Main dyadic link (third argument can't be accessed tacitly)
¡    Repeat [on the first argument, the seed]
⁴     (second argument) times
Ʋ      (
Ṛ            Reverse
ḋ           Dot product
⁵          with the third argument, the kernel
ṭ         Append that to the first argument
Ʋ      )
ḣ   Take the first (second argument) items [because we produced too many terms]


R, 62 bytes

function(k,s,n)for(i in 1:n){show(s[1]);s=c(s[-1],rev(k)%*%s)}


Try it online!

Raku, 50 bytes

{@^k;(|@^s,{sum @k Z*@_[@_-1…@_-@k]}…*)[^$^z]}  Try it online! • @^k (the kernel), @^s (the seed), and $^z (the count of elements to return) are the parameters to the function.
• (|@^s, { ... } … *) is an infinite sequence starting with the flattened seed array. The brace expression is a function which generates successive elements; it takes the entire list of previous elements in the @_ variable.
• @_[@_-1 … @_-@k] is the last N elements of the sequence so far, in reverse order, where N is the size of the kernel list.
• sum @k Z* @_[...] computes the sum of the kernel zip-multiplied with the previous N elements of the sequence.

PowerShell, 90 67 bytes

-Thanks to mazzy yet again for putting me to shame with a 23 byte save!!

$r,$s,$l=$args;for(;$l-$s.Count){$s+=&{$r|%{$a+=$_*$s[--$i]};$a}}$s


Try it online!

C (tcc), 99 98 bytes

t,i;f(k,s,n,z)int*k,*s;{for(;n--;s[z-1]=t)for(t=i=!printf("%d ",*s);i<z;s[i]=s[++i])t+=s[i]*k[i];}


Try it online!

• saved 1 thanks to @ceilingcat.

• essentially moves the seed array along the sequence, printing the first element, n times.

f(k,s,n,z) - input: kernel, seed, number, length of k,s
{for(;n--;s[z-1]=t) - repeat n times, updating last seed with next term
for(.. i<z;s[i]=s[++i]) - loop trough k,s swapping s back
printf("%d ",*s) - and printing first seed
t+=s[i]*k[i] : accumulate next term

Charcoal, 17 bytes

Ｆζ⊞ηΣＥθ×κ§⮌ηλＩ…ηζ


Try it online! Link is to verbose version of code. Explanation:

Ｆζ


Generate l more terms:

⊞η


Push to the seed...

ΣＥθ×κ§⮌ηλ


... the dot product of the kernel and the reversed seed.

Ｉ…ηζ


Print the first l terms of the seed (it's slightly golfier to generate extra unwanted terms).

Husk, 10 bytes

↑⁴¡ȯΣz*²↔⁰


Try it online!

↑⁴              # first n=arg3 elements of
¡ȯ     ⁰      # list created from repeatedly applying to arg1 and appending results:
Σ           # sum of
z*         # elementwise products of
²        # arg2, and
↔       # reverse of arg1


Julia, 46 bytes

g(k,s,n)=try s[1:n]catch;g([0;k],[s;s'k],n)end


Try it online!