Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
Ciekaw
Posts:
19
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?
|
|
|
|
