Calkin-Wilf sequence def calkin_wilf(n) The nodes of the Calkin-Wilf tree, when read in level order so that the elements in each level are read from left to right, produce the linear sequence of all possible positive rational numbers. Almost as if by magic, this construction guarantees every positive integer fraction to appear exactly once in this sequence. Even more wonderfully, this construction makes every rational number to appear in its lowest reduced form! To perform the following calculations, you should import the data types Fraction and deque from the fractions and collections modules. Your function should return the n:th element of this sequence. First, create a new instance of deque and append the first fraction 1/1 to prime the pump, so to speak, to initiate the production of the values of this sequence. Repeat the following procedure n times; pop the fraction currently in front of the queue using the deque method popleft, extract its numerator and denominator p and q, and push the two new fractions p/(p+q) and (p+q)/q to the back of the queue, in this order. Return the fraction object that was popped in the final round. n Expected result 10 3/5 10000 11/39 100000 127/713
Calkin-Wilf sequence
def calkin_wilf(n)
The nodes of the Calkin-Wilf tree, when read in level order so that the elements in each level are read from left to right, produce the linear sequence of all possible positive rational numbers. Almost as if by magic, this construction guarantees every positive integer fraction to appear exactly once in this sequence. Even more wonderfully, this construction makes every rational number to appear in its lowest reduced form! To perform the following calculations, you should import the data types Fraction and deque from the fractions and collections modules.
Your function should return the n:th element of this sequence. First, create a new instance of deque and append the first fraction 1/1 to prime the pump, so to speak, to initiate the production of the values of this sequence. Repeat the following procedure n times; pop the fraction currently in front of the queue using the deque method popleft, extract its numerator and denominator p and q, and push the two new fractions p/(p+q) and (p+q)/q to the back of the queue, in this order. Return the fraction object that was popped in the final round.
| n | Expected result |
| 10 | 3/5 |
| 10000 | 11/39 |
| 100000 | 127/713 |
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
