Farey sequence: Difference between revisions
Added XPL0 example.
No edit summary |
(Added XPL0 example.) |
||
Line 3,977:
F( 900): 246,327
F(1000): 304,193
</pre>
=={{header|XPL0}}==
<lang XPL0>proc Farey(N); \Show Farey sequence for N
\Translation of Python program on Wikipedia:
int N, A, B, C, D, K, T;
[A:= 0; B:= 1; C:= 1; D:= N;
Text(0, "0/1");
while C <= N do
[K:= (N+B)/D;
T:= C;
C:= K*C - A;
A:= T;
T:= D;
D:= K*D - B;
B:= T;
ChOut(0, ^ ); IntOut(0, A);
ChOut(0, ^/); IntOut(0, B);
];
];
func GCD(N, D); \Return the greatest common divisor of N and D
int N, D; \numerator and denominator
int R;
[if D > N then
[R:= D; D:= N; N:= R]; \swap D and N
while D > 0 do
[R:= rem(N/D);
N:= D;
D:= R;
];
return N;
]; \GCD
func Totient(N); \Return the totient of N
int N, Phi, M;
[Phi:= 0;
for M:= 1 to N do
if GCD(M, N) = 1 then Phi:= Phi+1;
return Phi;
];
func FareyLen(N); \Return length of Farey sequence for N
int N, Sum, M;
[Sum:= 1;
for M:= 1 to N do
Sum:= Sum + Totient(M);
return Sum;
];
int N;
[for N:= 1 to 11 do
[IntOut(0, N); Text(0, ": ");
Farey(N);
CrLf(0);
];
for N:= 1 to 10 do
[IntOut(0, N); Text(0, "00: ");
IntOut(0, FareyLen(N*100));
CrLf(0);
];
RlOut(0, 3.0 * sq(1000.0) / sq(3.141592654)); CrLf(0);
]</lang>
{{out}}
<pre>
1: 0/1 1/1
2: 0/1 1/2 1/1
3: 0/1 1/3 1/2 2/3 1/1
4: 0/1 1/4 1/3 1/2 2/3 3/4 1/1
5: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
6: 0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1
7: 0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1
8: 0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1
9: 0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1
10: 0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1
11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1
100: 3045
200: 12233
300: 27399
400: 48679
500: 76117
600: 109501
700: 149019
800: 194751
900: 246327
1000: 304193
303963.55085
</pre>
| |||