1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 |
- #!/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]
|