How to find simple function representing sequence?

55 Views Asked by At

I know a recurrent formula of generating sequence of numbers:

$$ T(n, h) = \begin{cases} 1) & [ n ], \textrm{if}\ h = 1 \\ 2) & T(n - h / 2, h / 2) +\\& T(n + h / 2, h / 2) +\\& B(n, h / 2) +\\& T(n, h / 2),\ \textrm{otherwise} \end{cases} $$

$$ B(n, h) = { \begin{cases} 1) & [ n ], \textrm{if}\ h = 1 \\ 2) & B(n, h / 2) + \\& T(n, h / 2) + \\& B(n - h / 2, h / 2) + \\& B(n + h / 2, h / 2), \textrm{otherwise} \end{cases} } $$

where $n$, $h$ are integer numbers. [ 1 2 3 ] denotes sequence of three numbers, sign $+$ denotes concatenation of two sequences (i.e. [ 2 3 4 ] + [ 1 5 0 ] = [ 2 3 4 1 5 0 ]).

How I can simplify its evaluation? Is it possible to represent sequence by a formula f(i) = ...? Maybe there is a way to find next number in the sequence given starting parameters of recursion and previous number (with some information about previous state to distinguish between elements with the same value)?

Important note, that recursion starts from invocation of $T$ with $h = 2^m$, $n=h-1 > 0$, where $m > 0$ is integer.

For example, first 100 values for T(63, 64):

0, 2, 1, 1, 4, 6, 5, 5, 3, 3, 2, 4, 2, 4, 3, 3, 8, 10, 9, 9, 12, 14, 13, 13, 11, 11, 10, 12, 10, 12, 11, 11, 7, 7, 6, 8, 6, 8, 7, 7, 5, 5, 4, 6, 9, 9, 8, 10, 4, 6, 5, 5, 8, 10, 9, 9, 7, 7, 6, 8, 6, 8, 7, 7, 16, 18, 17, 17, 20, 22, 21, 21, 19, 19, 18, 20, 18, 20, 19, 19, 24, 26, 25, 25, 28, 30, 29, 29, 27, 27, 26, 28, 26, 28, 27, 27, 23, 23, 22, 24 

It this case I am looking for function f(63,64,5) = 4 or f(63,64,11) = 2