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
Generating coprime pairs
Posted: Dec 2, 2012 6:06 AM

Generating coprime pairs:

Step 1

Select any number of natural.
For example, C = 167

Step 2

Write binary form C = 10100111

Step 3

Prepare a table to fill:

i Cbit(i) a(i) b(i)
1 1 1 1
2 0 ? ?
3 1 ? ?
4 0 ? ?
5 0 ? ?
6 1 ? ?
7 1 ? ?
8 1 ? ?
? ?

Step 4

Table formula:

a(i)=a(i-1)+b(i-1) ;

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

Complete the table, replace the question marks.

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

Summary:

Number natural C=167 generates a pair of relatively prime (coprime) 36/23 .

Analogously:

C=1 ; 2/1
C=2 ; 3/1
C=15 ; 8/5
C=55 ; 19/12
C=9999 ; 277/168
More of my program:
http://narval.republika.pl/coprime.exe

My questions:
Is this algorithm generates all coprime pairs?
Are two different numbers can correspond to the same coprime pair?

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