loda-lang / loda-cpp

Runtime and miner for the LODA language written in C++
https://loda-lang.org/
Apache License 2.0
21 stars 1 forks source link

Simplify formulas using Gaussian elimination #292

Closed ckrause closed 8 months ago

ckrause commented 10 months ago

Example:

; A275698: a(0) = 2, after that a(n) is 3 plus the least common multiple of previous terms.
; Formula: a(n) = a(n-1)*b(n-1)+3, a(1) = 5, a(0) = 2, b(n) = a(n-1)*b(n-1), b(1) = 2, b(0) = 1

mov $1,1
mov $2,2
lpb $0
  sub $0,1
  mul $1,$2
  mov $2,$1
  add $2,3
lpe
mov $0,$2

Notice that:

a(n) = a(n-1)*b(n-1)+3
b(n) = a(n-1)*b(n-1)

subtract the two equations we obtain

a(n)-b(n) = 3

and thus b(n) = a(n)-3. Therefore we can simplify the main formula to a(n) = a(n-1)*(a(n-1)-3)+3.

Similar approach should work for:

; A081367: E.g.f.: exp(2*x)/sqrt(1-2*x).
; Formula: a(n) = b(n-1)*(2*n-2)+2*a(n-1)+a(n-1), a(2) = 11, a(1) = 3, a(0) = 1, b(n) = b(n-1)*(2*n-2)+a(n-1), b(2) = 5, b(1) = 1, b(0) = 0

mov $2,1
lpb $0
  sub $0,1
  mul $3,$1
  add $3,$2
  add $1,2
  mul $2,2
  add $2,$3
lpe
mov $0,$2