3
$\begingroup$

Given positive integers $ k $ and $ n $, I would like to generate a list of all the finite continued fractions of length $ k $ in the interval $ [0,1] $ whose partial quotients are bounded above by $ n $.

For instance, when $ k=3 $ and $ n=2 $, the list would be:

$$ \left\{ \frac{1}{1+\frac{1}{1+\frac{1}{1}}}, \frac{1}{1+\frac{1}{1+\frac{1}{2}}}, \frac{1}{1+\frac{1}{2+\frac{1}{1}}}, \frac{1}{1+\frac{1}{2+\frac{1}{2}}}, \frac{1}{2+\frac{1}{1+\frac{1}{1}}}, \frac{1}{2+\frac{1}{1+\frac{1}{2}}}, \frac{1}{2+\frac{1}{2+\frac{1}{1}}}, \frac{1}{2+\frac{1}{2+\frac{1}{2}}} \right\} = \left\{ \frac{2}{3}, \frac{3}{5}, \frac{3}{4}, \frac{5}{7}, \frac{2}{5}, \frac{3}{8}, \frac{3}{7}, \frac{5}{12} \right\}. $$

From this question, it is easy to produce a function that takes a string of integers and gives the corresponding continued fraction:

Contfrac[terms_List] := Fold[1/(#2 + #1) &, Reverse@terms]

For instance, evaluating

Contfrac[{1,1,1}]

returns $ \frac{2}{3} $, as desired. I'm guessing I can generate the list using this function and $ \texttt{Array} $ somehow, but my naive attempt

Array[Contfrac, {2, 2, 2}]

for the above example fails. Any suggestions?

$\endgroup$

3 Answers 3

5
$\begingroup$

The function "Contfra" needs to be changed to suit your description.

With the changed function you may get all fraction according to k and n by:

k = 3;
n = 2;
Contfrac[terms_List] := 
 Fold[1/(#2 + #1) &, 1/Last[terms], Reverse@Most@terms]
Contfrac /@ Tuples[Range[n], {k}]

enter image description here

$\endgroup$
2
$\begingroup$

There's also this, using the built-in CF function:

Block[{k = 3, n = 2},
 FromContinuedFraction /@ 
  PadLeft[Tuples[Range[n], {k}], {Automatic, k + 1}]
 ]
(*  {2/3, 3/5, 3/4, 5/7, 2/5, 3/8, 3/7, 5/12}  *)

You need to prepend the integer part 0 with PadLeft to get the OP's desired output.

$\endgroup$
1
$\begingroup$

Using FromContinuedFraction:

1/(FromContinuedFraction/@Tuples[Range[2], {3}])


     2  3  3  5  2  3  3   5
(* { -, -, -, -, -, -, -, -- } *)
     3  5  4  7  5  8  7  12
$\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.