Calkin-Wilf Sequence Def Salkin Wilt(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.

 

Calkin-Wilf sequence def salkin 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 nith 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. Then 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/ (Rtg) and (Rtq)/q to the back of the queue, in this order. Return the fraction object that was popped in the final round. n 10 1000 Expected result 3/5 11/39 100000 127/713 (Actually, once you reach the position n//2+1, you could stop pushing in any new values and save some significant memory. The queue already contains the result you need...)