How to resolve the algorithm Calkin-Wilf sequence step by step in the J programming language
How to resolve the algorithm Calkin-Wilf sequence step by step in the J programming language
Table of Contents
Problem Statement
The Calkin-Wilf sequence contains every nonnegative rational number exactly once. It can be calculated recursively as follows:
To avoid floating point error, you may want to use a rational number data type.
It is also possible, given a non-negative rational number, to determine where it appears in the sequence without calculating the sequence. The procedure is to get the continued fraction representation of the rational and use it as the run-length encoding of the binary representation of the term number, beginning from the end of the continued fraction. It only works if the number of terms in the continued fraction is odd- use either of the two equivalent representations to achieve this:
The fraction 9/4 has odd continued fraction representation 2; 3, 1, giving a binary representation of 100011, which means 9/4 appears as the 35th term of the sequence.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Calkin-Wilf sequence step by step in the J programming language
Source code in the j programming language
cw_next_term=: [: % +:@<. + -.
ccf =: compute_continued_fraction=: 3 :0
if. 0 -: y do.
, 0
else.
result=. i. 0
remainder=. % y
whilst. remainder do.
remainder=. % remainder
integer_part=. <. remainder
remainder=. remainder - integer_part
result=. result , integer_part
end.
end.
)
molcf =: make_odd_length_continued_fraction=: (}: , 1 ,~ <:@{:)^:(0 -: 2 | #)
NB. base 2 @ reverse @ the cf's representation copies of 1 0 1 0 ...
index_cw_term=: #.@|.@(# 1 0 $~ #)@molcf@ccf
ccf=: _1 {"1 |.@(0 1 #: %@{.)^:(0~:{.)^:a:
You may also check:How to resolve the algorithm Comments step by step in the Modula-2 programming language
You may also check:How to resolve the algorithm Averages/Pythagorean means step by step in the SQL programming language
You may also check:How to resolve the algorithm Padovan sequence step by step in the Wren programming language
You may also check:How to resolve the algorithm Stirling numbers of the first kind step by step in the Prolog programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the x86 Assembly programming language