Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
Math Forum
»
Discussions
»
sci.math.*
»
sci.math
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
|
 |
|
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?
|
|
|
|