lucas_sequences_U_V.sf

#!/usr/bin/ruby

# Algorithm due to Aleksey Koval for computing the Lucas U and V sequences.

# See also:
#   https://en.wikipedia.org/wiki/Lucas_sequence

func lucasUV(n, P, Q) {

    var(V1 = 2, V2 = P)
    var(Q1 = 1, Q2 = 1)

    for j in (n.ilog2 `downto` 0) {

        Q1 *= Q2

        if (n.getbit(j)) {
            Q2 = (Q1 * Q)
            V1 = (V2*V1 - P*Q1)
            V2 = (V2*V2 - 2*Q2)
        }
        else {
            Q2 = Q1
            V2 = (V2*V1 - P*Q1)
            V1 = (V1*V1 - 2*Q2)
        }
    }

    var Uk = (2*V2 - P*V1)/(P*P - 4*Q)

    return [Uk, V1]
}

for n in (1..20) {
    say lucasUV(n, 1, -1)
}

__END__
[1, 1]
[1, 3]
[2, 4]
[3, 7]
[5, 11]
[8, 18]
[13, 29]
[21, 47]
[34, 76]
[55, 123]
[89, 199]
[144, 322]
[233, 521]
[377, 843]
[610, 1364]
[987, 2207]
[1597, 3571]
[2584, 5778]
[4181, 9349]
[6765, 15127]