Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Ciekaw Posts: 28 Registered: 11/24/12
Re: Generating coprime pairs
Posted: Dec 2, 2012 11:46 AM

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);

Date Subject Author
12/2/12 Ciekaw
12/2/12 Leon Aigret
12/2/12 Leon Aigret
12/2/12 Ciekaw