Rosetta Code: Hofstadter Figure-Figure sequences

[WJ]

> These two sequences of positive integers are defined as:
>
> R ( 1 ) = 1 ; S ( 1 ) = 2
> R ( n ) = R ( n - 1 ) + S ( n - 1 ) , n > 1
>
> The sequence S(n) is further defined as the sequence of
> positive integers not present in R(n).
>
> Sequence R starts: 1, 3, 7, 12, 18, ...
> Sequence S starts: 2, 4, 5, 6, 8, ...
>
> Task
>
> Create two functions named ffr and ffs that when given n
> return R(n) or S(n) respectively. (Note that R(1) = 1 and S(1)
> = 2 to avoid off-by-one errors).
>
> No maximum value for n should be assumed.
>
> Calculate and show that the first ten values of R are: 1, 3,
> 7, 12, 18, 26, 35, 45, 56, and 69
>
> Calculate and show that the first 40 values of ffr plus the
> first 960 values of ffs include all the integers from 1 to
> 1000 exactly once.

Ruby:

$r = [nil,1,3]
$s = [nil,2,4]

def extend
if $r.size == $s.size
$r << $r.last + $s.last
else
$s << ($s.last + 1 .. $s.last+3).find{|n| not $r.include?(n)}
end
end

def ffr(n)
extend until $r[n]
$r[n]
end

def ffs(n)
extend until $s[n]
$s[n]
end

(1..10).map{|i| ffr(i)}
==>[1, 3, 7, 12, 18, 26, 35, 45, 56, 69]

((1..40).map{|i| ffr(i)} + (1..960).map{|i| ffs(i)}).sort ==
(1..1000).to_a
==>true

In Forth?

--
From the New York Times of October 11, 1991, ... we learn that ... researchers
at Boston University admitted that, "There is no question but that Dr. King
plagiarized in the dissertation." ... "Dr. Martin Luther King, Jr." [Michael
King] spent his last night on Earth having sexual intercourse with two women at
the motel and physically beating and abusing a third.
www.revilo-oliver.com/Kevin-Strom-personal/Beast_as_Saint.html

[Paul Rubin]

"WJ" <w_a_...@yahoo.com> writes:
> Ruby: [dozens of lines of bureaucracy]
> In Forth?

http://dilbert.com/strip/1995-06-24

0 value p
: @p+ ( -- n ) p @ p cell + to p ;
: init clearstack here to p 2 , 4 , 5 , 6 , 1 3 7 ;
: hof ( a b c -- a b c r s )
rot >r dup 2 cells p + @ + 2dup swap 1+ do i , loop r> @p+ ;
: 15r init 15 0 do hof drop . loop ;
: 15s init 15 0 do hof nip . loop ;
\ test for [1..1000] by checksum - close enough for government work.
: checksum ( -- flag ) 0 0 { sx sy } init 960 0
do hof sy + to sy i 40 < if sx + to sx else drop then loop
2drop drop sx sy + 1000 1001 * 2 / = ;
: go 15r cr 15s cr checksum . ;

=>

go 1 3 7 12 18 26 35 45 56 69 83 98 114 131 150
2 4 5 6 8 9 10 11 13 14 15 16 17 19 20
-1 ok

Does someone want to put this on Rosetta? It was kind of a cute problem.