Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Generating coprime pairs
Replies: 3   Last Post: Dec 2, 2012 11:46 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ciekaw

Posts: 13
Registered: 11/24/12
Re: Generating coprime pairs
Posted: Dec 2, 2012 11:46 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Sunday, December 2, 2012 4:05:25 PM UTC+1, Leon Aigret wrote:

> Oops. Looking again, I see that the actual representation is
>
> [0; 1, 1, 1, 3, 3], so the link between the Cbit series and the
>
> continued fraction representation of the ratio of the coprime pair
>
> requires some modif1cation at both ends. Still think that the approach
>
> is basically sound.
>


This is connection to the Euclidean algorithm.

Euclidean algorithm:


i a(i) b(i) Cbit(i)
0 36 23
1 13 23 1
2 13 10 1
3 3 10 1
4 3 7 0
5 3 4 0
6 3 1 1
7 2 1 0
8 1 1 1

Table formula:
if min[a(i-1);b(i-1)] = max[a(i);b(i)] then Cbit(i)=1
if min[a(i-1);b(i-1)] = min[a(i);b(i)] then Cbit(i)=0

if a(i-1)=max[a(i-1);b(i-1)] then a(i)=a(i-1)-b(i-1) else a(i)=a(i-1);
if b(i-1)=max[a(i-1);b(i-1)] then b(i)=b(i-1)-a(i-1) else b(i)=b(i-1);






Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.