Linear integer function generator

Question

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:

1. the kernel (a representation of the recurrence relation). More about this below.
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.

Answer 1

Wolfram Language (Mathematica), 16 bytes

LinearRecurrence

Try it online!

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

Answer 2

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

Answer 3

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.

Answer 4

Haskell, 54 49 bytes

g k(x:r)n=take n$x:g k(r++[sum$zipWith(*)k$x:r])n

Try it online! Use as g kernel seed n.

Previously, the function g only took the seed and the kernel as input and recursively build the sequence as an infinite list, with a second function truncating this infinite sequence to the given length with take n. However, it turns out we can just incorporate this truncation into g because of lazy evaluation, saving 5 bytes.

Answer 5

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

Try it online! or Try all cases!

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

Answer 6

Python 3, 72 67 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!

Answer 7

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!

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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!

Answer 12

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

Try it online! Try it online! (81 bytes/original input) Try it online! (75 bytes/reversed kernel)

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

Answer 13

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]

Answer 14

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!

Answer 15

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.

Answer 16

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!

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

Julia, 46 bytes

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

Try it online!