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

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
Generating coprime pairs
Posted: Dec 2, 2012 6:06 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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?




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.