Here is a solution that runs in constant space and is linear in
the number of fractions that it finds (it actually only computes
the denominators, one after another from 1/3 to 1/2).
f =: 3 : 0
i =. 0
'a b' =. 3,y-3|>:y
while. b>2 do.
'a b' =. b,a-~b*<.(y+a)%b
i =. >:i
end.
i
)
f 12000
7295372
The problem is that it is very slow for 12000: almost 2 min on my
computer. A recursive rephrasing, such as
N =: 12000
fr =. [`(>:@[$:({:,{.-~{:*<.@(N&+@{.%{:))@])@.({:@]>2:)
0 fr 3,N-3|>:N
should be somewhat faster, but it miserably runs out of stack
already at N=190 (while I was hoping fr to be treated as tail-
recursive and execute in constant space.)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
