12
\$\begingroup\$

Background

The recurrence of the Fibonacci sequence is defined as

$$ f(n+2) = f(n+1) + f(n) $$

From this recurrence alone, the following gap formulae (recurrences relating three terms with certain amount of gaps) can be derived:

$$ f(n+4) = 3f(n+2) - f(n) \\ f(n+6) = 4f(n+3) + f(n) \\ f(n+8) = 7f(n+4) - f(n) $$

You might have seen the \$n+6\$ formula if you have worked on Project Euler #2 hard enough :)

In general, for any \$a \in \mathbb{Z}^+\$ (positive integers), there exist unique integer coefficients \$\alpha, \beta\$ of the generalized gap formula

$$ f(n+2a) = \alpha f(n+a) + \beta f(n) $$

which holds for all \$n\$.

We can generalize the Fibonacci recurrence itself too:

$$ f'(n+2) = uf'(n+1) + vf'(n) $$

Then it can be shown that, for any \$a \in \mathbb{Z}^+\$ and \$u,v \in \mathbb{Z}\$, there exists a fully general gap formula with integer coefficients:

$$ f'(n+2a) = \alpha f'(n+a) + \beta f'(n) \tag{1}\label{eq1} $$

Note that such a formula is not unique for some values of \$u, v, a\$.

Challenge

Given the values of \$a, u, v\$, calculate the pair of values of \$\alpha\$ and \$\beta\$ in the equation \$\eqref{eq1}\$. You don't need to handle cases where the answer is not unique.

All three inputs are guaranteed to be integers. \$a\$ is strictly positive.

Standard rules apply. The shortest code in bytes wins.

Test cases

For u = 1, v = 1
a = 1 -> alpha = 1, beta = 1
a = 2 -> alpha = 3, beta = -1
a = 3 -> alpha = 4, beta = 1
a = 4 -> alpha = 7, beta = -1

For u = -2, v = 3
a = 1 -> alpha = -2, beta = 3
a = 2 -> alpha = 10, beta = -9
a = 3 -> alpha = -26, beta = 27
a = 4 -> alpha = 82, beta = -81

For u = 3, v = -9
a = 1 -> alpha = 3, beta = -9
a = 2 -> alpha = -9, beta = -81
a = 3 -> undefined (not unique)
a = 4 -> alpha = -81, beta = -6561
a = 5 -> alpha = 243, beta = -59049
a = 6 -> undefined (not unique)
\$\endgroup\$
7
  • 5
    \$\begingroup\$ If I did my math right, \$\beta\$ is \$-(-v)^a\$, and \$\alpha\$ is the \$a\$'th element \$f(a)\$ of the sequence if we initialize \$f(0)=2, f(1)=u\$. \$\endgroup\$
    – xnor
    Oct 28, 2021 at 3:17
  • 1
    \$\begingroup\$ Suggested testcase: \$u=3,v=-9,a=6\$ \$\endgroup\$
    – tsh
    Oct 28, 2021 at 3:44
  • 1
    \$\begingroup\$ @UnrelatedString Right, it's n. Fixed. \$\endgroup\$
    – Bubbler
    Oct 28, 2021 at 5:00
  • 3
    \$\begingroup\$ If \$f(0) = x, f(1) = y, f(n + 2) = 3 f(n + 1) - 9 f(n])\$, then \$f(6) = 729 x, f(12) = 531441 x\$. Try it online. There isn't a unique formular between \$f(0), f(6), f(12)\$. \$\endgroup\$
    – alephalpha
    Oct 28, 2021 at 5:55
  • 3
    \$\begingroup\$ @alephalpha Oh, didn't realize that. I changed the challenge to allow solutions like yours (failing when the answer is not unique). \$\endgroup\$
    – Bubbler
    Oct 28, 2021 at 6:26

7 Answers 7

9
\$\begingroup\$

Pari/GP, 37 bytes

Saved 13 bytes thanks to @xnor.

(u,v,n)->[-(-v)^n,trace([0,1;v,u]^n)]

Try it online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I don't know this Pari/GP, but I think it might be shorter to express the output as the trace and the negative determinant of m \$\endgroup\$
    – xnor
    Oct 28, 2021 at 6:34
  • 2
    \$\begingroup\$ 37 bytes \$\endgroup\$
    – xnor
    Oct 28, 2021 at 6:37
6
\$\begingroup\$

Python 3.8 (pre-release), 60 58 bytes

lambda u,v,a:[(p:=u/2-(u*u/4+v)**.5)**a+(u-p)**a,-(-v)**a]

Try it online!

¯2 thanks to @tsh

Originally based on @tsh's answer (now removed due to no complex number support)

\$\endgroup\$
0
6
\$\begingroup\$

Jelly, 13 12 bytes

Ø.,æ*ÆḊN,ÆṭƲ

Try it online!

Takes input as [v, u] on the left, and a on the right. Outputs as [β, α]

-1 byte thanks to ovs!

Uses xnor's formula that

$$\alpha = \operatorname{tr} \left( \begin{bmatrix} 0 & 1 \\ v & u \end{bmatrix}^a \right) \\ \beta = -(-v)^a = - \det \left( \begin{bmatrix} 0 & 1 \\ v & u \end{bmatrix}^a \right)$$

How it works

Ø.,æ*ÆḊN,ÆṭƲ - Main link. Takes [v, u] on the left, a on the right
Ø.           - Yield [0, 1]
  ,          - Pair; [[0, 1], [v, u]]
   æ*        - Matrix power to a; Call this M
           Ʋ - Last 4 links as a monad f(M):
     ÆḊ      -   Determinant of M
       N     -   Negated
         Æṭ  -   Trace of M
        ,    -   Pair; [-det(M), tr(M)]
\$\endgroup\$
2
  • \$\begingroup\$ \$(-v)^a\$ is the determinant of the matrix (from xnor's comment on the PARI answer), which allows for 12: Ø.,æ*ÆḊN,ÆṭƲ \$\endgroup\$
    – ovs
    Oct 28, 2021 at 15:43
  • \$\begingroup\$ @ovs Nice catch, thanks! \$\endgroup\$ Oct 28, 2021 at 16:21
4
\$\begingroup\$

JavaScript (Node.js), 77 bytes

(u,v,a)=>[A=(F=n=>n<2?n^m:u*F(n-1)+v*F(n-2))(a+a,m=0)/F(a),F(a+a,m=1)-A*F(a)]

Try it online!

Let

$$ f_1\left(0\right)=0 \\ f_1\left(1\right)=1 \\ f_1\left(n+2\right)=u\cdot f_1\left(n+1\right)+v\cdot f_1\left(n\right) $$

Calculate

$$ p=f_1(2a) \\ q=f_1(a) $$

Let

$$ f_2\left(0\right)=1 \\ f_2\left(1\right)=0 \\ f_2\left(n+2\right)=u\cdot f_2\left(n+1\right)+v\cdot f_2\left(n\right) $$

Calculate

$$ r=f_2(2a) \\ s=f_2(a) $$

We have

$$ p=\alpha\cdot q \\ r = \alpha \cdot s + \beta $$

Solve

$$ \alpha=\frac{p}{q} \\ \beta=r-\alpha \cdot s $$


Try to undelete this question since all failed testcases currently known had been been excluded from the question. Maybe this one is correct, but I'm not quite sure.

\$\endgroup\$
4
\$\begingroup\$

R, 59 bytes

Or R>=4.1, 52 bytes by replacing the word function with \.

function(u,v,a)c((p=u/2-(u^2/4+v+0i)^.5)^a+(u-p)^a,-(-v)^a)

Try it online!

Based on @xnor's formula and @PyGamer0's answer.

Outputs complex numbers - for pretty integers add 4 bytes for wrapping result in Re.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 23 22 bytes

0L‚©IF®øδ*O}Å\O¹θ(Im(‚

Port of @cairdCoinheringaahing's Jelly answer, but without matrix power/multiplication, trace, nor determinant builtins. It uses a slight modification of @xnor's formula:

\$\alpha = \operatorname{tr} \left( \begin{bmatrix} u&v\\1&0 \end{bmatrix}^a \right) \\ \beta = -(-v)^a\$

Inputs as [u,v] and a.

Try it online or verify all test cases.

Explanation:

0L          # Push [1,0]
  ‚         # Pair it with the (implicit) input-pair: [[u,v],[1,0]]
   ©        # Store it in variable `®` (without popping)
    IG      # Loop the second input `a` - 1 amount of times:
      ®     #  Push the matrix from variable `®`
       ø    #  Zip/transpose it; swapping rows/columns
        δ   #  Apply double-vectorized over the two matrices:
         *  #   Multiply them together
          O #  And then sum each inner-most list
     }Å\    # After the loop: pop the matrix and push its main diagonal
        O   # Sum it together
¹           # Push the first input-pair again
 θ          # Pop and only leave the last item (`v`)
  (         # Negate it
   Im       # Take it to the power of the second input `a`
     (      # Negate that again
‚           # Pair the two integers together
            # (after which this pair [α,β] is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 38 bytes

NθNη⊞υ²⊞υθF⊖N⊞υ⁺×θ§υ±¹×η§υ±²I⟦⊟υ±X±ηLυ

Try it online! Link is to verbose version of code. Explanation: Uses @xnor's formula.

NθNη

Input u and v.

⊞υ²⊞υθ

Push 2 and u to the predefined empty list.

F⊖N⊞υ⁺×θ§υ±¹×η§υ±²

Calculate a-1 more terms so that the last term is now the ath term.

I⟦⊟υ±X±ηLυ

Remove and output the ath term, then calculate the power using the remaining length which is now a.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.