Tetranacci numbers in the journal (n)

Question

I came across a problem that requires me to calculate the nth Tetranacci number in O (log n).

I saw several solutions for this for the Fibonacci Number

I tried to follow a similar procedure (Matrix Multiplication / Fast Doubling) to achieve this, but I'm not sure how to do it (take a 4 by 4 matrix and 1 by 4 matrix doesn't seem to work in the same way). With dynamic programming / general loops / any other basic idea, I cannot achieve sublinear runtime. Any help appreciated!

Answer 1

From OEIS , this is a record of (1.4) n-th degree

1 1 0 0
1 0 1 0
1 0 0 1
1 0 0 0

To calculate the nth power of this matrix in O (log n) operations, you can use squaring . There may be a slightly simpler repetition, but you should be able to implement a common technique.

Answer 2

Matrix multiplication of term papers. Here's how to get the matrix.

We want to find entries that make the equation

[a b c d] [T(n-1)]   [T(n)  ]
[e f g h] [T(n-2)]   [T(n-1)]
[i j k l] [T(n-3)] = [T(n-2)]
[m n o p] [T(n-4)]   [T(n-3)]

true for everyone n. Expand

a T(n-1) + b T(n-2) + c T(n-3) + d T(n-4) = T(n)
e T(n-1) + f T(n-2) + g T(n-3) + h T(n-4) = T(n-1)
i T(n-1) + j T(n-2) + k T(n-3) + l T(n-4) = T(n-2)
m T(n-1) + n T(n-2) + o T(n-3) + p T(n-4) = T(n-3)

The obvious parameters are a = b = c = d = 1(using repetition) and e = j = o = 1and f = g = h = i = k = l = m = n = p = 0(basic algebra).

Starting vector

[T(3)]   [1]
[T(2)]   [0]
[T(1)] = [0]
[T(0)]   [0]

a-priory.

Answer 3

, . :

T(2n)   = T(n+1)*(2*T(n+2) - T(n+1)) + T(n)*(2*T(n+3) - 2*T(n+2) - 2*T(n+1) - T(n))
T(2n+1) = T(n)^2 + T(n+2)^2 + T(n+1)*(2*T(n+3) - 2*T(n+2) - T(n+1))
T(2n+2) = T(n+1)*(2*T(n) + T(n+1)) + T(n+2)*(2*T(n+3) - T(n+2))
T(2n+3) = T(n+1)^2 + T(n+3)^2 + T(n+2)*(2*T(n) + 2*T(n+1) + T(n+2))

" ". Python, :

def tetranacci_by_doubling(n):
    if n >= 0:
        a, b, c, d = 0, 0, 0, 1 # T(0), T(1), T(2), T(3)
    else: # n < 0
        a, b, c, d = 1, 0, 0, 0 # T(-1), T(0), T(1), T(2)

    # unroll the last iteration to avoid computing unnecessary values.
    for i in reversed(range(1, abs(n).bit_length())):
        w = b*(2*c - b) + a*(2*(d - c - b) - a)
        x = a*a + c*c + b*(2*(d - c) - b)
        y = b*(2*a + b) + c*(2*d - c)
        z = b*b + d*d + c*(2*(a + b) + c)

        a, b, c, d = w, x, y, z

        if (n >> i) & 1 == 1:
            a, b, c, d = b, c, d, a + b + c + d

    if n & 1 == 0:
        return b*(2*c - b) + a*(2*(d - c - b) - a)  # w
    else: # n & 1 == 1
        return a*a + c*c + b*(2*(d - c) - b)        # x

def tetranacci(n):
    a, b, c, d = 0, 0, 0, 1 # T(0), T(1), T(2), T(3)
    # offset by 3 to reduce excess computation for large positive `n`
    n -= 3 

    if n >= 0:
        for _ in range(+n):
            a, b, c, d = b, c, d, a + b + c + d
    else: # n < 0
        for _ in range(-n):
            a, b, c, d = d - c - b - a, a, b, c

    return d

# sanity check
print(all(tetranacci_by_doubling(n) == tetranacci(n) for n in range(-1000, 1001)))

T(2n-3),T(2n-2),T(2n-1),T(2n) T(n-3),T(n-2),T(n-1),T(n), n, .

Update

• , , n . .
• , , - , . ~ 40% -50% n (>= 10^6)! .

- . , . , T(n) (, , ) , n , , 2^n ~= 2^0 + 2^1 + ... + 2^(n-1). Fibonacci/Lucas ~ 40% - , Fibonacci/etc. 64- M, , .