# Implement Euler's method

The goal of this challenge is to use Euler's method to approximate the solution of a differential equation of the form f(n)(x) = c.

The input will be a list of integers in which the nth value represents the value of f(n)(0). The first integer is f(0), the second is f'(0), and so on. The last integer in this list is the constant and will always remain the same.

Also provided as input will be a positive (nonzero) integer x, which represents the target value (you are trying to estimate f(x)). The step size for Euler's method will always be 1. Thus, you will need to take x steps total.

If you are unfamliar with Euler's method, here is a detailed example with an explanation for the input [4, -5, 3, -1], x = 8.

x       f(x)      f'(x)     f''(x)    f'''(x)
0          4         -5          3         -1
1   4-5 = -1  -5+3 = -2   3-1 =  2         -1
2  -1-2 = -3  -2+2 =  0   2-1 =  1         -1
3  -3+0 = -3   0+1 =  1   1-1 =  0         -1
4  -3+1 = -2   1+0 =  1   0-1 = -1         -1
5  -2+1 = -1   1-1 =  0  -1-1 = -2         -1
6  -1+0 = -1   0-2 = -2  -2-1 = -3         -1
7  -1-2 = -3  -2-3 = -5  -3-1 = -4         -1
8  -3-5 = -8


Essentially, each cell in the generated table is the sum of the cell above it and the cell above and to the right. So, f(a) = f(a-1) + f'(a-1); f'(a) = f'(a-1) + f''(a-1); and f''(a) = f''(a-1) + f'''(a-1). The final answer is f(8) ≈ -8.††

The input list will always contain 2 or more elements, all of which will have absolute values less than 10. x ≥ 1 is also guaranteed. The output is a single integer, the approximation of f(x). Input may be taken in either order (the list before x, or x before the list). x may also be the first or last element of the list, if desired.

Test cases:

[4, -5, 3, -1], x = 8 => -8
[1, 2, 3, 4, 5, 6], x = 10 => 3198
[1, 3, 3, 7], x = 20 => 8611
[-3, 3, -3, 3, -3, 3, -3, 3, -3], x = 15 => -9009
[1, 1], x = 1 => 2


†: it is notable that using an approximation method in this situation is, in fact, stupid. however, the simplest possible function was chosen for the purposes of this challenge.

††: the actual value happens to be -25⅓, which would qualify this approximation as "not very good."

l%n|n<1=l!!0|m<-n-1=l%m+tail(l++[0])%m


Try it online!

Improved from 39 bytes:

l%0=l!!0
l%n=l%(n-1)+tail(l++[0])%(n-1)


Recursively expresses the output l%n. Moving up corresponds to decrementing n, and moving right corresponds to taking tail l to shift all list elements one space left. So, the output l%n is the value above l%(n-1), plus the value above and to the right (tail l)%(n-1)

The base case n==0 is to take the first list element.

Ideally, the input would be padded with infinitely many zeroes to the right, since the derivatives of a polynomial eventually become zero. We simulate this by appending a 0 when we take the tail.

Weird alt 41:

(iterate(\q l->q l+q(tail l++[0]))head!!)


# MATL, 9 bytes

:"TTZ+]1)


### Explanation

:"      % Implicitly input x. Do the following x times
TT    %   Push [1 1]
Z+    %   Convolution, keeping size. Implicitly inputs array the first time
]       % End
1)      % Get first entry. Implictly display


# Jelly, 6 5 bytes

Ḋ+$¡Ḣ  Try it online! -1 byte thanks to @Doorknob Explanation Ḋ+$¡Ḣ  - Main dyadic link. First input list, second x
- (implicit) on the previous iteration (starting at input list)
Ḋ      - Dequeue. e.g. [-5,3,-1]
- (implicit) the previous iteration. e.g. [4+(-5),-5+3,3+(-1),-1+0]
\$¡   - apply this successively x times
Ḣ  - get the first element from the resultant list


# Brachylog, 13 12 bytes

{,0s₂ᶠ+ᵐ}ⁱ⁾h


Try it online!

## How it works

{,0s₂ᶠ+ᵐ}ⁱ⁾h
{       }ⁱ⁾   iterate the previous predicate
to the array specified by first element of input
as many times as the second element of input
h  and get the first element

example input to predicate: [4, _5, 3, _1]
,0           append 0: [4, _5, 3, _1, 0]
s₂ᶠ        find all substrings with length 2:
[[4, _5], [_5, 3], [3, _1], [_1, 0]]
+ᵐ      "add all the elements" mapped to each subarray:
[_1, _2, _2, _1]


## Previous 13-byte solution

{b,0;?z+ᵐ}ⁱ⁾h


Try it online!

### How it works

{b,0;?z+ᵐ}ⁱ⁾h
{        }ⁱ⁾   iterate the previous predicate
to the array specified by first element of input
as many times as the second element of input
h  and get the first element

example input to predicate: [4, _5, 3, _1]
b             remove the first element: [_5, 3, _1]
,0           append 0: [_5, 3, _1, 0]
;?         pair with input: [[_5, 3, _1, 0], [4, _5, 3, _1]]
z        zip: [[_5, 4], [3, _5], [_1, 3], [0, _1]]
+ᵐ      "add all the elements" mapped to each subarray:
[_1, _2, _2, _1]


## Mathematica, 32 bytes

#&@@Nest[#+Rest@#~Append~0&,##]&

                               &  make a pure function
Nest[                 &,##]   call inner function as many times as specified
Rest@#                 drop the first element of the list
~Append~0        and add a 0 to get [b,c,d,0]
#+                       add original list to get [a+b,b+c,c+d,d]
#&@@                              take the first element after x iterations


# Python, 80 58 bytes

Love the math for this challenge.

f=lambda a,x:x and f(map(sum,zip(a,a[1:]+[0])),x-1)or a[0]


How it works (only works with python 2):

f=lambda a,x:                                              - new lambda function
x and                                         - iterate itself x times
map(sum,zip(a,a[1:]+[0]))             - e.g; f(a) = f(a-1) + f'(a-1)
f(                         ,x-1)        - iterate new array into itself
or a[0] - return first element


Try it online!

100 byte alternate with use of pascals triangle

from math import factorial as F
f=lambda a,x:sum([(a+[0]*x)[i]*F(x)/(F(x-i)*F(i))for i in range(x)])


How it works (works for python 2 and 3):

sum([                                                ]) - take the sum of array
(a+[0]*x)                                        - append x zeros
[i]*F(x)/(F(x-i)*F(i))                  - multiply each element by x choose i
for i in range(x) - do this for every element


This formula works by mapping the coefficients of row x of pascals triangle onto the array. Each element of pascals triangle is determined by the choose function of the row and index. The sum of this new array is equivalent to the output at x. It's also intuitive as the iterated process of newtons method (shown in the example) acts exactly as the construction of pascals triangle.

Try it online!

Big thanks to ovs for reducing 22 bytes by converting loop into a recursive function

• Here is an improved version. I converted the for loop to an recursive function
– ovs
Commented May 6, 2017 at 22:04
• Ah, great idea @ovs Commented May 6, 2017 at 22:08
• even shorter Note that it will only work with python2
– ovs
Commented May 6, 2017 at 22:09

l#n=iterate(zipWith(+)=<<tail.(++[0]))l!!n!!0


Usage example: [-3,3,-3,3,-3,3,-3,3,-3] # 15 -> -9009. Try it online!

How it works

iterate(      )l          -- apply the function again and again starting with l
-- and collect the intermediate results in a list
-- the function is
(++[0])         -- append a zero
zipWith(+)=<<tail       -- and build list of neighbor sums
!!0  -- take the first element from
!!n     -- the nth result


Edit: @xnor saved 7 bytes. Thanks!

• I think the iterated function can be zipWith(+)=<<tail.(++[0]), i.e. fix the list beforehand rather than afterward.
– xnor
Commented May 6, 2017 at 20:21
• @xnor: yes, that saves a lot of bytes. Thanks!
– nimi
Commented May 6, 2017 at 23:13
• I just cannot wrap my mind around the use of =<< here, this is insane:) Commented May 7, 2017 at 10:45
• @flawr: =<< is used in function context and is defined as: (=<<) f g x = f (g x) x. Here we use =<< infix: (f =<< g) x with f = zipWith(+) and g = tail, which translates to zipWith(+) (tail x) x.
– nimi
Commented May 7, 2017 at 15:22
• Thank you for the detailed explanation, I was not aware of the function monad! Commented May 7, 2017 at 18:35

# CJam, 12 bytes

q~{_(;.+}*0=


Try it online!

### Explanation

The code directly implements the procedure described in the challenge.

q~            e# Read input and evaluate. Pushes the array and the number x
{     }*    e# Do the following x times
_          e# Duplicate array
(;        e# Remove first element
.+      e# Vectorized sum. The last element in the first array, which doesn't
e# have a corresponding entry in the second, will be left as is
0=  e# Get first element. Implicitly display


# Pyth, 10 bytes

s.e*b.cQkE


Test suite.

## How it works

s.e*b.cQkE
.e      E   for (b,k) in enumerated(array):
.cQk        (input) choose (k)
*b            * b
s            sum


# APL (Dyalog), 29 bytes

{0=⍺:⊃⍵
(⍺-1)∇(+/¨2,/⍵),¯1↑⍵}


Try it online!

This is a recursive dfn, but it turns out to be too verbose. Golfing in progress...

# Actually, 7 bytes

;lr(♀█*


Try it online!

## How it works

;lr(♀█*  input:
8, [4, -5, 3, -1]
top of stack at the right
;        duplicate
8, [4, -5, 3, -1], [4, -5, 3, -1]
l       length
8, [4, -5, 3, -1], 4
r      range
8, [4, -5, 3, -1], [0, 1, 2, 3]
(     rotate stack
[4, -5, 3, -1], [0, 1, 2, 3], 8
♀█   map "n choose r"
[4, -5, 3, -1], [1, 8, 28, 56]
*  dot product
-8


# Octave, 42 bytes

@(a,x)conv(a,diag(flip(pascal(x+1))))(x+1)


This defines an anonymous function. Try it online!

### Explanation

The solution could be computed by repeatedly convolving the input array and the resulting arrays with [1, 1]. But convolving twice, or thrice, or ... with [1, 1] corresponds to convolving once with [1, 2 ,1], or [1, 3, 3, 1], or ...; that is, with a row of the Pascal triangle. This is obtained as the anti-diagonal of the Pascal matrix of order x+1.

## JavaScript (ES6), 41 bytes

f=(a,x,[b,...c]=a)=>x--?f(a,x)+f(c,x):b|0


f=(a,x)=>x--?f(a.map((e,i)=>e+~~a[i+1]),x):a[0]


# Python 3 with Numpy, 82 bytes

import numpy
def f(a,x):
for n in range(x):a=numpy.convolve(a,[1,1])
return a[x]


Similar to my MATL answer, but using full-size convolution, and thus the result is the x-th entry of the final array.

Try it online!

# Python, 51 bytes

f=lambda l,n:n and f(l,n-1)+f(l[1:]+[0],n-1)or l[0]


Try it online!