Author Topic: Generating coprime pairs  (Read 6213 times)

struktor

  • Sr. Member
  • *****
  • Posts: 342
Generating coprime pairs
« on: December 01, 2012, 10:35:25 PM »
Bights and Leads are coprime in Turk's Head Knots.

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=167; 36/23
C=9999 ; 277/168
My program:
http://narval.republika.pl/coprime.exe

Struktor


« Last Edit: April 10, 2013, 04:39:27 PM by struktor »