I did it! I figured out this formula!

give any hint: F[n] = summa(a[i] * F[n-i], i=1..k) are right? (here a[i], and k - are consts).
k=?
a[]- easy generate, iff k - know.

Yes, you are right. k = 19.
Good luck! :-D

(n-19>=7)  start from 7...

Hint: solve system equation with Gauss method (19x19).

Edited by author 31.12.2019 16:33


static constexpr int results[] =
{ // 0  1  2  3  4  5
     0, 0, 0, 0, 0, 0,
/*Answer for n = 6 is*/  12,
/*Answer for n = 7 is*/  46,
/*Answer for n = 8 is*/  144,
/*Answer for n = 9 is*/  110,
/*Answer for n = 10 is*/ 312,
/*Answer for n = 11 is*/ 290,
/*Answer for n = 12 is*/ 670,
/*Answer for n = 13 is*/ 706,
/*Answer for n = 14 is*/ 1538,
/*Answer for n = 15 is*/ 1732,
/*Answer for n = 16 is*/ 3504,
/*Answer for n = 17 is*/ 4288,
/*Answer for n = 18 is*/ 8098,
/*Answer for n = 19 is*/ 10568,
/*Answer for n = 20 is*/ 19044,
/*Answer for n = 21 is*/ 26042,
/*Answer for n = 22 is*/ 45222,
/*Answer for n = 23 is*/ 64220,
/*Answer for n = 24 is*/ 108382,
/*Answer for n = 25 is*/ 158324,
/*Answer for n = 26 is*/ 261754,
/*Answer for n = 27 is*/ 390314,
/*Answer for n = 28 is*/ 635666,
/*Answer for n = 29 is*/ 962282,
/*Answer for n = 30 is*/ 1550244,
/*Answer for n = 31 is*/ 2372372,
/*Answer for n = 32 is*/ 3792560,
/*Answer for n = 33 is*/ 5848746,
/*Answer for n = 34 is*/ 9299148,
/*Answer for n = 35 is*/ 14419296,
/*Answer for n = 36 is*/ 22838014,
/*Answer for n = 37 is*/ 35548790,
/*Answer for n = 38 is*/ 56153296,
/*Answer for n = 39 is*/ 87640646,
/*Answer for n = 40 is*/ 138180196,
/*Answer for n = 41 is*/ 216065986,
/*Answer for n = 42 is*/ 340223834,
/*Answer for n = 43 is*/ 532680994,
/*Answer for n = 44 is*/ 838025410,
/*Answer for n = 45 is*/ 1313251780,
/*Answer for n = 46 is*/
};

Edited by author 31.12.2019 16:33

Thanks for the sequence! The problem is indeed solved with linear recurrence (your message from 2012). Although, it seems k=20 here, and one needs to run Gauss on 20x20 matrix. I got by solution by using Berlekamp—Massey though.

I wonder, how could you guess there is a linear recurrence and that K is small enough to brute force the sequence in finite time (I assume that's how you got it).

Edited by author 31.12.2019 18:41