Find the pattern v2 [on hold]

Related

I feel tired to do “find the pattern” exercise such as

1 2 3 4 (5)
1 2 4 8 (16)
1 2 3 5 8 (13)

Please write a program that finds the pattern for me.

Here, we define the pattern as a recurrence relation that fits the given input, with the smallest score. If there are multiple answers with the same smallest score, using any one is fine.

Let the $k$ first terms be initial terms for the recurrence relation, and the $i$‘th term be $f(i)$ ($i>k,iinmathbb N$).

  • A non-negative integer $x$ adds$1$ to the score
  • The current index $i$ adds $1$ to the score
  • +, -, *, / (round down or towards zero, as you decide) and mod (a mod b always equal to a-b*(a/b)) each add $1$ to the score
  • For each initial term $x$, add $1$ to the score
  • $f(i-n)$ (with $nle k$) adds $1$ to the score. E.g. Using the latest value $f(i-1)$ add $1$ to the score, and there must be at least 1 initial term.
  • Changing the calculation order doesn’t add anything to the score.

Samples:

input   -> [score]    expression(not optimized)
1 2 3 4     -> [1]    f(i) = i
1 2 4 8     -> [3]    f(1) = 1, f(i) = 2*f(i-1)
1 2 3 5 8   -> [5]    f(1) = 1, f(2) = 2, f(i) = f(i-1)+f(i-2)
1 3 -5      -> [3]    f(1) = 1, f(2) = 3, f(3) = -5

Lowest score for worse case; Fastest algorithm with binary(or base 88, or anything) input using multi-tape turing machine model; shortest program in each language wins.

Lowest score for worse case; Fastest algorithm using multi-tape turing machine model; First submission will be accepted. (differ from winning criticia)

Hint and proof are here:

Leave a Reply

Your email address will not be published. Required fields are marked *