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